Как я могу улучшить этот алгоритм (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

Я вижу, что это должно занять самую длинную общую подпоследовательность из двух списков. Как вы заметили, это довольно медленно. Вам нужно будет использовать более сложный подход, чем просто перебор, если вы хотите, чтобы он работал быстрее; каноническим решением является алгоритм динамического программирования, описанный в этой статье Википедии .

Один из способов значительно ускорить решение без полного перехода на другой алгоритм - это запоминание результатов, поскольку в нынешнем виде вы будете снова и снова вычислять одни и те же промежуточные результаты, Записывать и удалять элементы из концов списков.

РЕДАКТИРОВАТЬ: Ну, простой способ сделать это немного быстрее без большой работы - это использовать предложение 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))))

Надеюсь, это правильно - у меня нет переводчика под рукой - но вы получите картину.