Ответ 1
Игнорируя, что это плохой алгоритм (должен быть memoizing, я добираюсь до этой секунды)...
Использовать O (1) Примитивы, а не O (n)
Одна из проблем заключается в том, что вы используете целые вызовы связью, которые являются O (n) для списков (списки haskell - это списки, связанные по отдельности). Лучшая структура данных даст вам O (1) операции, я использовал Vector:
import qualified Data.Vector as V
-- standard levenshtein distance between two lists
editDistance :: Eq a => [a] -> [a] -> Int
editDistance s1 s2 = editDistance' 1 1 1 (V.fromList s1) (V.fromList s2)
-- weighted levenshtein distance
-- ins, sub and del are the costs for the various operations
editDistance' :: Eq a => Int -> Int -> Int -> V.Vector a -> V.Vector a -> Int
editDistance' del sub ins s1 s2
| V.null s2 = ins * V.length s1
| V.null s1 = ins * V.length s2
| V.last s1 == V.last s2 = editDistance' del sub ins (V.init s1) (V.init s2)
| otherwise = minimum [ editDistance' del sub ins s1 (V.init s2) + del -- deletion
, editDistance' del sub ins (V.init s1) (V.init s2) + sub -- substitution
, editDistance' del sub ins (V.init s1) s2 + ins -- insertion
]
Операции O (n) для списков включают init, length и last (хотя init может быть ленивым, по крайней мере). Все эти операции - O (1) с использованием Vector.
В то время как настоящий бенчмаркинг должен использовать Criterion, быстрый и грязный тест:
str2 = replicate 15 'a' ++ replicate 25 'b'
str1 = replicate 20 'a' ++ replicate 20 'b'
main = print $ editDistance str1 str2
показывает, что векторная версия занимает 0,09 секунды, а строки - 1,6 секунды, поэтому мы спасли примерно на порядок, даже не глядя на ваш алгоритм editDistance.
А как насчет мемуаризации результатов?
Большей проблемой, очевидно, является необходимость в memoization. Я воспринял это как возможность изучить пакет monad-memo - мой бог - это здорово! За одно дополнительное ограничение (вам нужно Ord a), вы получаете мемонирование в основном без усилий. Код:
import qualified Data.Vector as V
import Control.Monad.Memo
-- standard levenshtein distance between two lists
editDistance :: (Eq a, Ord a) => [a] -> [a] -> Int
editDistance s1 s2 = startEvalMemo $ editDistance' (1, 1, 1, (V.fromList s1), (V.fromList s2))
-- weighted levenshtein distance
-- ins, sub and del are the costs for the various operations
editDistance' :: (MonadMemo (Int, Int, Int, V.Vector a, V.Vector a) Int m, Eq a) => (Int, Int, Int, V.Vector a, V.Vector a) -> m Int
editDistance' (del, sub, ins, s1, s2)
| V.null s2 = return $ ins * V.length s1
| V.null s1 = return $ ins * V.length s2
| V.last s1 == V.last s2 = memo editDistance' (del, sub, ins, (V.init s1), (V.init s2))
| otherwise = do
r1 <- memo editDistance' (del, sub, ins, s1, (V.init s2))
r2 <- memo editDistance' (del, sub, ins, (V.init s1), (V.init s2))
r3 <- memo editDistance' (del, sub, ins, (V.init s1), s2)
return $ minimum [ r1 + del -- deletion
, r2 + sub -- substitution
, r3 + ins -- insertion
]
Вы видите, как для memoization нужен один "ключ" (см. класс MonadMemo)? Я упаковал все аргументы как большой уродливый кортеж. Он также нуждается в одном "значении", которое является вашим результатом Int. Затем он просто подключи и играй, используя функцию "memo" для значений, которые вы хотите сохранить в память.
Для бенчмаркинга я использовал более короткую, но большую длину, строку:
$ time ./so # the memoized vector version
12
real 0m0.003s
$ time ./so3 # the non-memoized vector version
12
real 1m33.122s
Даже не думайте о том, чтобы запустить версию, не напоминающую memoized, я полагаю, что это займет около 15 минут. Что касается меня, я теперь люблю монад-памятку - спасибо за пакет Эдуарда!
EDIT: разница между String и Vector не так много в мемуаризованной версии, но все же растет до коэффициента 2, когда расстояние доходит до 200, поэтому все равно стоит.
EDIT: Возможно, я должен объяснить, почему большая проблема - это "очевидно" мемуаризирующие результаты. Ну, если вы посмотрите на сердце оригинального алгоритма:
[ editDistance' ... s1 (V.init s2) + del
, editDistance' ... (V.init s1) (V.init s2) + sub
, editDistance' ... (V.init s1) s2 + ins]
Совершенно ясно, что вызов editDistance' s1 s2 приводит к 3 вызовам editDistance'... каждый из которых вызывает editDistance' еще три раза... и еще три раза... и AHHH! Экспоненциальный взрыв! К счастью, большинство звонков одинаковы! например (используя --> для "вызовов" и eD для editDistance'):
eD s1 s2 --> eD s1 (init s2) -- The parent
, eD (init s1) s2
, eD (init s1) (init s2)
eD (init s1) s2 --> eD (init s1) (init s2) -- The first "child"
, eD (init (init s1)) s2
, eD (init (init s1)) (init s2)
eD s1 (init s2) --> eD s1 (init (init s2))
, eD (init s1) (init s2)
, eD (init s1) (init (init s2))
Просто рассмотрев родительский и двух непосредственных детей, мы видим, что вызов ed (init s1) (init s2) выполняется три раза. Другой дочерний ресурс вызывает с родителем тоже, и все дети делятся многими вызовами друг с другом (и их детьми, кий на песню Monty Python).
Было бы забавным, возможно, поучительным упражнением сделать функцию runMemo, которая возвращает количество используемых кешированных результатов.