Использование Data.Memocombinators для реализации алгоритма редактирования расстояния

Question

Допустим, я хотел реализовать обычный алгоритм динамического программирования для Расстояние Левенштейна (редактировать расстояние). Довольно просто придумать рекурсию:

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]

Это страдает от экспоненциального времени работы, поэтому необходимо запомнить функцию. Я хочу сделать это с помощью 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
  | ...

В противном случае вы выполняете полностью рекурсивные вычисления и сохраняете только конечный результат. Вам нужно хранить промежуточные результаты.

Здесь есть еще одна проблема. Таблица memo для elm не должна зависеть от ее аргументов (в идеале вы не должны даже упоминать аргументы, поэтому вы не зависите от того, насколько компилятор достаточно умен, чтобы выяснить зависимости). Если таблица памятки зависит от аргументов, то вам нужно создать новую таблицу для каждого отдельного аргумента, и нам нужно совместно использовать таблицу для всех аргументов. Вы можете попробовать что-то глупое, например, запоминать всю структуру аргументов:

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

Посмотрите, ускоряет ли это его (включая прежний трюк) Затем вы можете перейти к попытке использовать только длины вместо всей структуры списка для дополнительного увеличения.

Надеюсь, это помогло.