LCS and python Working on some python silly code. The LCS solution using dynamic programming.
So i timed this algo against a recursive and another dynamic implementation in python. Interestingly I changed a string concatenation done with the + operator to a ‘’.join function. That made the algo faster. I found a page on concatenation times in python. The link at the end of the post. Now since i am retarded, i wrote the algo very fast and then i tested it with two strings. I got an unexpected result. I spent time looking for errors in the algo, but i could not find anything. Turned out that i mistyped one of the input strings. I really need to use my glasses.



import sys
str1 = `sys.argv[1]`
str2 = `sys.argv[2]`
rows = len(str1)
cols = len(str2)

xA = [[(0,'') for col in range(cols+1)] for row in range(rows+1)]

#create table

for row in range(1,rows+1):
        for col in range(1,cols+1):
                if(str1[row-1]==str2[col-1]):
                        xA[row][col] = (xA[row-1][col-1][0]+1, ''.join([xA[row-1][col-1][1],str1[row-1]]))
                elif(xA[row-1][col][0]>=xA[row][col-1][0]):
                        xA[row][col] = (xA[row-1][col][0],xA[row-1][col][1])
                else:
                        xA[row][col] = (xA[row][col-1][0],xA[row][col-1][1])

print xA[row][col][1]


my algo

real        0m0.032s
user        0m0.014s
sys        0m0.014s

a recursive algo(found on (http://wordaligned.org/articles/longest-common-subsequence))
real        0m1.250s
user        0m1.161s
sys        0m0.022s

another dynamic algo (found on(http://wordaligned.org/articles/longest-common-subsequence))
real        0m0.038s
user        0m0.017s
sys        0m0.015s




Useful links on the subject:
http://wordaligned.org/articles/longest-common-subsequence
http://www.skymind.com/~ocrow/python_string/


code to run the test:
str1="iewweewjjowfh"
str2="pfiueewewewr"

time python lcs.py "$str1" "$str2"
time python lcs2.py "$str1" "$str2"
time python lcs3.py "$str1" "$str2"

Labels: algorythm, lcs, python

  ¶ 10:49 PM