How Can I Improve This Algorithm (LCS)

Question

  (define (lcs lst1 lst2)
   (define (except-last-pair list)
   (if (pair? (cdr list))
   (cons (car list) (except-last-pair (cdr list)))
   '()))
  (define (car-last-pair list)
   (if (pair? (cdr list))
   (car-last-pair (cdr list))
   (car list)))
  (if (or (null? lst1) (null? lst2)) null
   (if (= (car-last-pair lst1) (car-last-pair lst2))
      (append (lcs (except-last-pair lst1) (except-last-pair lst2)) (cons (car-last-pair lst1) '()))
      (**if (> (length (lcs lst1 (except-last-pair lst2))) (length (lcs lst2 (except-last-pair lst1)))) 
          (lcs lst1 (except-last-pair lst2))
          (lcs lst2 (except-last-pair lst1))))))**

I dont want it to run over and over..

Regards, Superguay

Answer 1

I see that this is supposed to take the longest common subsequence of two lists. As you noted, it's pretty slow. You will need to take a more complicated approach than just brute-forcing it like this if you want it to work more quickly; the canonical solution is the dynamic programming algorithm described in this Wikipedia article.

One way you could vastly speed up your solution without totally switching to a different algorithm is through memoization of the results, since as it stands you'll be computing the same intermediate results over and over as you recurse and drop elements from the ends of the lists.

EDIT: Well, an easy way to make it a bit faster without much work would be to use a let clause to avoid extra work at the bottom, i.e.

(if (or (null? lst1) (null? lst2)) null
  (let ((front1 (except-last-pair lst1)) (front2 (except-last-pair lst2)))
    (if (= (car-last-pair lst1) (car-last-pair lst2))       
      (append (lcs front1 front2) (cons (car-last-pair lst1) '()))
      (let ((sub-lcs1 (lcs lst1 front2)) (sub-lcs2 (lcs lst2 front1)))
        (if (> (length sub-lcs1) (length sub-lcs2)) 
          sub-lcs1
          sub-lcs2))))

Hope it's correct - I don't have an interpreter handy - but you get the picture.