忽略，這是一個糟糕的算法（應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）的列表包括初始化，length的操作，和last（雖然INIT能夠偷懶的最小）。所有這些操作都是使用Vector的O（1）。
雖然真正的標杆應該使用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算法。
現在怎麼樣記憶結果？
更大的問題顯然是需要記憶。我將此作爲了解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。然後，只需使用「備忘錄」功能即可即插即用您想要記憶的值。
對於基準我用較短，但較大的距離，字符串：
$ time ./so # the memoized vector version
12
real 0m0.003s
$ time ./so3 # the non-memoized vector version
12
real 1m33.122s
千萬別想運行非memoized字符串版本，我想，這將需要大約15分鐘在最低限度。至於我，我現在喜歡monad-memo - 感謝Eduard的包裝！
編輯：String和Vector之間的差異在memoized版本中沒有那麼多，但當距離達到200左右時仍然增長到2倍，所以仍然值得。
編輯：也許我應該解釋爲什麼更大的問題是「明顯」記憶結果。好吧，如果你看一下原始算法的心臟：
[ 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 skit）共享許多呼叫。
這將是一個有趣的，也許有啓發性的練習，使runMemo類似的函數返回所使用的緩存結果的數量。
哇，這是偉大的。我以前聽說過莫諾化，但我從來沒有想到這很容易！當你說「忽略這是一個不好的算法（應該記憶，我到那一秒）......」，你是指算法的整體結構還是僅僅是應該使用記憶的事實？對我來說，算法本身看起來不錯。 :) – bzn 2011-04-01 21:14:57
bzn：我只是認爲這不是記憶的事實。如果您之前沒有看過記憶，那麼請參閱[Haskell wiki]（http://www.haskell.org/haskellwiki/Memoization），CS算法手冊，或兩者。如果沒有記憶，你可以多次計算大部分值，但是記憶只能計算一次，否則就會查找以前計算的結果。例如，要計算列表的第一個元素（'editDist s1（init s2）'），函數最終將計算'editDist（init s1）（init s2）'。這是調用者列表中的第二個元素，並且是被調用者列表中的第三個元素！ – 2011-04-01 22:09:07
@bzn我添加了一個編輯，談論爲什麼這個問題是「顯然」memoization。 – 2011-04-01 22:39:07