如何改善这种算法（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))))))** 

我不希望它一遍又一遍地跑..

问候， Superguay

Answer 1

我看，这是应该采取的最长公共子的两个列表。正如你所说，这很慢。如果你想让它更快地工作，你需要采取更复杂的方法，而不是像这样强悍的方式;规范的解决方案是在this Wikipedia article中描述的动态规划算法。

通过memoization的结果，您可以大幅加速解决方案的一种方式，而无需完全切换到不同的算法，因为您可以一次又一次计算相同的中间结果，列表的结尾。

编辑：好了，一个简单的方法来使它有点没有太多的工作速度是使用一个let条款，以避免在底部额外的工作，即

(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)))) 

希望这是正确的 - 我不没有口译员的便利 - 但你得到的照片。