OK then: since your concern is speed, let's track our progress with actual timing data. The first step is to run the code through the Python profiler. With the addition of a bit of driver code that just calls LongestCommonSubstr().longest_common_substr
10000 times, I get the following results:
$ python3.4 -m profile lcs_profile.py abcdeffghiklnopqr bdefghijklmnopmnop
1130008 function calls in 3.083 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(__build_class__)
1 0.000 0.000 3.082 3.082 :0(exec)
1 0.000 0.000 0.000 0.000 :0(hasattr)
280000 0.257 0.000 0.257 0.000 :0(len)
260000 0.330 0.000 0.330 0.000 :0(max)
260000 0.350 0.000 0.350 0.000 :0(min)
1 0.000 0.000 0.000 0.000 :0(setprofile)
10000 0.042 0.000 0.042 0.000 :0(sorted)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:2264(_handle_fromlist)
260000 1.067 0.000 1.746 0.000 genericpath.py:69(commonprefix)
1 0.022 0.022 3.082 3.082 lcs_profile.py:1(<module>)
20000 0.069 0.000 0.157 0.000 lcs_profile.py:11(_get_suffix_str)
20000 0.071 0.000 0.071 0.000 lcs_profile.py:13(<listcomp>)
10000 0.807 0.000 2.794 0.000 lcs_profile.py:15(_get_lcsubstr)
1 0.000 0.000 0.000 0.000 lcs_profile.py:3(LongestCommonSubstr)
10000 0.067 0.000 3.060 0.000 lcs_profile.py:4(__init__)
1 0.000 0.000 3.083 3.083 profile:0(<code object <module> at 0x10996f030, file "lcs_profile.py", line 1>)
0 0.000 0.000 profile:0(profiler)
The most important column is the second one, tottime
, marking the total amount of time consumed by each function (but not the functions it calls). The largest entries in that column are for the commonprefix
function and the _get_lc_substr
function, so those are the spots you should focus on optimizing.
To keep track of our progress, I coupled your class with the following driver program which prints the execution time for 10000 runs:
def lcs_longest_match(a, b):
return LongestCommonSubstr(a, b).longest_common_substr
if __name__ == '__main__':
import timeit, sys
print('lcs ', timeit.timeit('lcs_longest_match(sys.argv[1], sys.argv[2])',
setup='from __main__ import lcs_longest_match',
number=10000))
(this is for Python 3). A first run on my computer gives
$ python3.4 lcs.py abcdeffghiklnopqr bdefghijklmnopmnop
lcs 0.49046793299203273
I'll start with _get_lc_substr
, since you wrote that code and it'll be easier to work through. The algorithm you use is to go through each pair of consecutive strings in the sorted suffix array, find the common prefix, and save that prefix only if it's longer than any common prefix already found. I can suggest a few improvements:
- Iterating over pairs of consecutive elements is a common task that has a fairly standard recipe,
pairwise(iterable)
, given in the documentation for the itertools module. You can use the implementation from the more-itertools package if you want. This also lets you get rid of the try
/except
block (which probably didn't affect runtime much, but it helps code clarity).
- Python has a built-in function,
max
, to find the maximum value of an iterable. If you use it, then the nuts and bolts of the loop as well as the compare-and-store-if-greater process get handled internally by the interpreter, which should be faster than doing them manually in pure Python.
- Repeatedly accessing an attribute of an object, namely the method
self._suffix_str_array
, is slower than accessing it once and storing it locally as a new variable.
Let's check the effect of these changes on the runtime of the driver program:
lcs 0.49046793299203273
optlcs1 0.4739605739887338
optlcs2 0.4895538759883493
optlcs3 0.4828952929965453
Not much of a change. Actually, using max
is slower here, so let's discard that change.
Time now to take a closer look at commonprefix
.
If you look at the source code of this function,
def commonprefix(m):
"Given a list of pathnames, returns the longest common leading component"
if not m: return ''
s1 = min(m)
s2 = max(m)
for i, c in enumerate(s1):
if c != s2[i]:
return s1[:i]
return s1
you see that it goes through some preliminary steps relating to the fact that it needs to handle a list of potentially several paths. You only ever have two strings to compare, so you can skip that - and in fact, if you look back at the profiling data, you'll see that these calls to max
and min
do take up a significant amount of time. Therefore, it makes sense to implement your own version of commonprefix
without the max
and min
calls.
This makes a big difference in the runtime, cutting it down by over 30%:
lcs 0.49046793299203273
optlcs3 0.4828952929965453
optlcs4 0.3215277789859101
If you think about it, you don't even really need the common prefix itself, except for the one string you actually return from _get_lcsubstr
. You only need its length, so you can decide which substring is the longest. So instead of using a function that finds the full common prefix, just write one that will give you its length. You store the length, along with one of the strings, and at the end of _get_lcsubstr
, use the length to trim the stored string.
def _get_lcsubstr(self):
# initialize
for s1, s2 in mt.pairwise(suffix_str_array):
if s1[-1] != s2[-1]:
substr_len = get_common_prefix_length(s1, s2)
if substr_len > max_len:
max_len = substr_len
max_substr = s1
return max_substr[:max_len]
This shaves another few percent off the runtime:
lcs 0.49046793299203273
optlcs4 0.3215277789859101
optlcs5 0.30241094100347254
If it's faster to avoid computing a substring in your commonprefix
replacement, you might think of doing the same thing when you're finding the suffixes in the first place. In other words, instead of calculating all the suffixes of a string in _get_suffix_str
, just make a list of (index, which_string)
tuples to represent the suffixes. Then whenever you need to actually compare two suffixes, instead of taking a substring of the original string, you just start comparing characters at the required indices.
There are two problems with this in practice: first, Python isn't well suited to iterating from an arbitrary point in the middle of a string. In a language like C, where strings are character pointers, this would work out quite well, because you can jump into the middle of the string by advancing a pointer. But in Python, iterating from the middle of a string requires you to either start from the beginning and just skip the first several characters, or bypass the whole iteration mechanism and use a for
loop with an integer index to access characters inside the string by their indices (which typically involves more Python code that is relatively inefficient). And besides, the other reason is you need to create the substrings anyway to sort them. If you try to do it so that you use the substrings as comparison keys without actually storing them, the program spends a lot of time converting between a substring and its index.
All told, the changes you need to make to the code to use indices everywhere wind up hurting, not helping. Here's the timing result:
lcs 0.49046793299203273
optlcs5 0.30241094100347254
optlcs6 0.3683815289987251
At this point, you can spend a lot of time making little tweaks to try to squeeze some extra performance out of the program, but I don't think there are any major performance gains left. It's already something like 40% faster than the original, which is not bad.
Of course, as dawg wrote in a comment, you can accomplish this task using Python's standard module difflib
.
def difflib_longest_match(a, b):
i, j, k = difflib.SequenceMatcher(a=a, b=b
).find_longest_match(0, len(a), 0, len(b))
return a[i:i+k]
I have no idea what's in the difflib
code (well, I could look, but I'll leave that as an exercise), but it's clearly heavily optimized for this kind of task. It's another 25% faster than my best version of your program:
lcs 0.49046793299203273
optlcs5 0.30241094100347254
difflib 0.2154458940058248
So if you really want to do this not for educational purposes, just use difflib
.
Here is the content of the test script I used.
import difflib
import itertools as it
import more_itertools as mt
from os.path import commonprefix
class LongestCommonSubstr(object):
def __init__(self, lstring, rstring):
self.lstring = lstring+'0'
self.rstring = rstring+'1'
self._suffix_str_array = sorted(self._get_suffix_str(self.lstring)
+ self._get_suffix_str(self.rstring))
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_suffix_str(string):
return [string[i:] for i in range(len(string))]
def _get_lcsubstr(self):
try:
substr_len =0
max_len = 0
lcs = None
for i,n in enumerate(self._suffix_str_array):
if n[-1] != self._suffix_str_array[i+1][-1]:
substr = commonprefix([n,self._suffix_str_array[i+1]])
substr_len = len(substr)
if substr_len > max_len:
max_len = substr_len
lcs = substr
except IndexError:
pass
return lcs
class OptimizedLongestCommonSubstr1(object):
def __init__(self, lstring, rstring):
self.lstring = lstring+'0'
self.rstring = rstring+'1'
self._suffix_str_array = sorted(self._get_suffix_str(self.lstring)
+ self._get_suffix_str(self.rstring))
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_suffix_str(string):
return [string[i:] for i in range(len(string))]
def _get_lcsubstr(self):
substr_len =0
max_len = 0
lcs = None
for s1, s2 in mt.pairwise(self._suffix_str_array):
if s1[-1] != s2[-1]:
substr = commonprefix([s1,s2])
substr_len = len(substr)
if substr_len > max_len:
max_len = substr_len
lcs = substr
return lcs
class OptimizedLongestCommonSubstr2(object):
def __init__(self, lstring, rstring):
self.lstring = lstring+'0'
self.rstring = rstring+'1'
self._suffix_str_array = sorted(self._get_suffix_str(self.lstring)
+ self._get_suffix_str(self.rstring))
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_suffix_str(string):
return [string[i:] for i in range(len(string))]
def _get_lcsubstr(self):
return max((commonprefix([s1,s2]) for s1, s2 in mt.pairwise(self._suffix_str_array) if s1[-1] != s2[-1]), key=len)
class OptimizedLongestCommonSubstr3(object):
def __init__(self, lstring, rstring):
self.lstring = lstring+'0'
self.rstring = rstring+'1'
self._suffix_str_array = sorted(self._get_suffix_str(self.lstring)
+ self._get_suffix_str(self.rstring))
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_suffix_str(string):
return [string[i:] for i in range(len(string))]
def _get_lcsubstr(self):
s_array = self._suffix_str_array
return max((commonprefix([s1,s2]) for s1, s2 in mt.pairwise(s_array) if s1[-1] != s2[-1]), key=len)
class OptimizedLongestCommonSubstr4(object):
def __init__(self, lstring, rstring):
self.lstring = lstring+'0'
self.rstring = rstring+'1'
self._suffix_str_array = sorted(self._get_suffix_str(self.lstring)
+ self._get_suffix_str(self.rstring))
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_suffix_str(string):
return [string[i:] for i in range(len(string))]
@staticmethod
def _get_common_prefix(s1, s2):
for i, c in enumerate(s1):
if c != s2[i]:
return s1[:i]
return s1
def _get_lcsubstr(self):
s_array = self._suffix_str_array
gcp = self._get_common_prefix
substr_len =0
max_len = 0
lcs = None
for s1, s2 in mt.pairwise(s_array):
if s1[-1] != s2[-1]:
substr = gcp(s1, s2)
substr_len = len(substr)
if substr_len > max_len:
max_len = substr_len
lcs = substr
return lcs
class OptimizedLongestCommonSubstr5(object):
def __init__(self, lstring, rstring):
self.lstring = lstring+'0'
self.rstring = rstring+'1'
self._suffix_str_array = sorted(self._get_suffix_str(self.lstring)
+ self._get_suffix_str(self.rstring))
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_suffix_str(string):
return [string[i:] for i in range(len(string))]
@staticmethod
def _get_common_prefix_length(s1, s2):
for i, c in enumerate(s1):
if c != s2[i]:
return i
return len(s1)
def _get_lcsubstr(self):
s_array = self._suffix_str_array
gcpl = self._get_common_prefix_length
max_len = 0
max_substr = ''
for s1, s2 in mt.pairwise(s_array):
if s1[-1] != s2[-1]:
substr_len = gcpl(s1, s2)
if substr_len > max_len:
max_len = substr_len
max_substr = s1
return max_substr[:max_len]
class OptimizedLongestCommonSubstr6(object):
def __init__(self, lstring, rstring):
self.lstring = lstring
self.rstring = rstring
self._suffix_str_array = sorted(
[(i, True) for i, _ in enumerate(lstring)]
+ [(i, False) for i, _ in enumerate(rstring)],
key=lambda t: (lstring if t[1] else rstring)[t[0]:])
self.longest_common_substr = self._get_lcsubstr()
@staticmethod
def _get_common_prefix_length(s1, start1, s2, start2):
for i, c in enumerate(it.islice(s1, start1, None)):
if c != s2[i + start2]:
return i
return i
def _get_lcsubstr(self):
s_array = self._suffix_str_array
gcpl = self._get_common_prefix_length
max_len = 0
max_start = 0
max_substr = ''
for (i1, b1), (i2, b2) in mt.pairwise(s_array):
if b1 != b2:
if b1:
s1 = self.lstring
s2 = self.rstring
else:
s1 = self.rstring
s2 = self.lstring
substr_len = gcpl(s1, i1, s2, i2)
if substr_len > max_len:
max_len = substr_len
max_start = i1
max_substr = s1
return max_substr[max_start:max_start+max_len]
def lcs_longest_match(a, b):
return LongestCommonSubstr(a, b).longest_common_substr
for n in it.count(1):
if 'OptimizedLongestCommonSubstr{}'.format(n) in globals():
exec('''def optimized_lcs_longest_match_{}(a, b):
return OptimizedLongestCommonSubstr{}(a, b).longest_common_substr
'''.format(n, n))
else:
break
def optimized_lcs_longest_match(a, b):
return OptimizedLongestCommonSubstr(a, b).longest_common_substr
def difflib_longest_match(a, b):
i, j, k = difflib.SequenceMatcher(a=a, b=b).find_longest_match(0, len(a), 0, len(b))
return a[i:i+k]
if __name__ == '__main__':
import timeit, sys
n_runs = 10000
print('lcs ', timeit.timeit('lcs_longest_match(sys.argv[1], sys.argv[2])', setup='from __main__ import lcs_longest_match', number=n_runs))
for k in range(1, n):
print('optlcs{}'.format(k), timeit.timeit(
'optimized_lcs_longest_match_{}(sys.argv[1], sys.argv[2])'.format(k),
setup='from __main__ import optimized_lcs_longest_match_{}'.format(k),
number=n_runs))
print('difflib', timeit.timeit('difflib_longest_match(sys.argv[1], sys.argv[2])', setup='from __main__ import difflib_longest_match', number=n_runs))
print('control results:', difflib_longest_match(sys.argv[1], sys.argv[2]))
for k in range(1, n):
print('test results {}: '.format(k), eval('optimized_lcs_longest_match_{}(sys.argv[1], sys.argv[2])'.format(k)))