Data.Memocombinators를 사용하여 편집 거리 알고리즘 구현

Question

Levensthein distance (거리 편집)에 일반적인 동적 프로그래밍 알고리즘을 구현하고 싶다고합시다. 이 지수 실행 시간을 앓고

editDistance [] ys = length ys 
editDistance xs [] = length xs 
editDistance (x:xs) (y:ys) 
    | x == y = editDistance xs ys 
    | otherwise = minimum [ 
     1 + editDistance xs (y:ys), 
     1 + editDistance (x:xs) ys, 
     1 + editDistance xs ys] 

, 그래서 기능을 memoize 할 필요가있다 : 재귀을 마련하는 것은 매우 쉽습니다. Data.Memocombinators를 사용하여 그렇게하고 싶습니다. 여러 가지 방법을 시도했습니다. 나는 그것이 적어도 다항식 것 때문에 어떤 메모이 제이션이 실행 시간에 눈에 띄는 개선을 기대하지만

import qualified Data.MemoCombinators as M 

memLength str = 
    M.wrap 
    (\i -> drop i str) 
    (\xs -> length str - length xs) 
    (M.arrayRange (0,length str)) 

elm xs ys = (M.memo2 memListx memListy editDistance) xs ys 
    where 
    memListx = memLength xs 
    memListy = memLength ys 

그러나, 메모이 제이션은, 어떤 효과가없는 것 같다 여기에 내 현재 시도이다. 내 구현에 어떤 문제가 있습니까? 편집 거리의 가능한 한 높은 수준의 정의를 유지하면서 실행 시간을 얻으려면 어떻게해야합니까?

Answer 1

게시 한 코드가 실제로 수행중인 내용 인 경우 잘못 쓰셨습니다. :-). 재귀 함수를 메모하는 경우 재귀 버전 호출에 대한 호출을 메모 화 된 버전으로 다시 가져와야합니다. 예 : 예 :

editDistance (x:xs) (y:ys) 
    | x == y = elm xs ys 
    | ... 

그렇지 않으면 전체 반복 계산을 수행하고 최종 결과 만 저장합니다. 중간 결과를 저장해야합니다.

여기에도 또 다른 문제가 있습니다. 느릅 나무에 대한 메모 표는 인수에 의존해서는 안됩니다 (이상적으로 인수를 언급하지 않아도되므로 컴파일러가 종속성을 파악할만큼 충분히 똑똑하다는 것에 의존하지 않아야합니다). 메모 테이블이 인수에 의존하면 각기 다른 인수에 대해 새 테이블을 작성해야하며 모든 인수에 대해 테이블을 공유해야합니다. 그게 속도 경우

elm = M.memo2 (M.list M.char) (M.list M.char) 

가 (이전 트릭을 포함)를 참조하십시오 : 당신은 인수의 전체 구조에 memoizing 같은 바보 같은 뭔가를 시도 할 수 있습니다. 그런 다음 전체 목록 구조 대신 길이를 사용하여 추가 부스트를 사용할 수 있습니다.

희망을 얻었습니다.