Atabey Kaygun has another great post. This time it deals with finding the longest common subsequence of two sequences. First Atabey describes a simple algorithm for finding the longest common subsequence and then implements it in Common Lisp. The surprise is that it took over 4.4 seconds to calculate the longest common subsequence of the two sequences
(6 9 5 1 3 5 4 0 7 4 9 1 1 3) (7 10 2 8 9 11 1 10 7 9 11 8 10 0 5 6 11)
The algorithm is recursive but this seems like a lot of time for a such short input. What’s going on?
Atabey gives us the answer. He memoizes his code using the code that I discussed previously. When he does this—simply using mem-defun instead to defun to define his function—the time drops to 0.006 seconds. Take a look at his lcs function and see if this surprises you. It did me. You have to think carefully about what’s going on to see why the memoization made any difference at all let alone such a dramatic one. Atabey’s post is definitely worth a read.
Speaking of memoization, if you missed PuercoPop’s comment to my previous post on the subject, be sure to follow his link to Fare Rideau’s beautiful article exploring Common Lisp implementations of the Fibonacci sequence. You’ll be glad you did.