|Perl: the Markov chain saw|
Re^9: Fast common substring matchingby bioMan (Beadle)
|on Aug 26, 2005 at 15:52 UTC||Need Help??|
I have done a quick test. Quick because of your blazing fast algorithm. My runtimes for 3 to 200 strings is given below. The times come from the Time::HiRes::gettimeofday function in your program. I set $subStrSize = 256.
These results are from a second copy of your program that I created. It appears my first copy still has a bug.
Yes, there must be a bug in my original copy. Running my full data set with my backup copy of your program gave a runtime of 14.759568. I'd say that's a little better than three years! I'll check the results to see how they compare with some of my old results from limited data sets. That check could take a little time :-)
The problem could be with the way PerlIDE runs scripts. All the times above are from the command line (Win2000).
I ran the full data set with the second copy of the program from PerlIDE and got a runtime of 15.147881. So the problem is with my first copy of your program.
I really like your algorithm. It's speed will allow me to modify my original data and test a couple of theories. You've got a real winner.update
I checked the results from the program and the algorithm isn't finding all the matches. I made a modification which seems to do better.
I added a new variable called $filterSize. This is used to exclude matches below a minimum length for output. It replaces $subStrSize. $subStrSize is now used to set the minimum string search size. The statement used to output the results is also modified.
The last statement replaces:
I hoped this would give me better results. I used $filterSize = 256. I set $subStrSize to 16, 32, 64, or 128. The runtimes for $subStrSize were 250.505445, 124.928021, 57.274645, and 32.787612, respectively. I got the best results with $subStrSize = 128, $filterSize = 256. I don't know why $subStrSize = 128 gave better results than shorter lengths. Also $subStrSize = 256 gave significantly poorer results than any of the shorter lengths.