Levenshtein距離成本

Question

我是新來的haskell，我遇到了一個非常嚴重的性能問題，它必須是我的代碼而不是haskell平臺。

我有一個levenshtein距離（自己的代碼）的python實現，我通過（或試圖這樣做）這個給haskell。結果是如下：現在

bool2int :: Bool -> Int 
bool2int True = 1 
bool2int False = 0 

levenshtein :: Eq a => [a] -> [a] -> Int -> Int -> Int 
levenshtein u v 0 0 = 0 
levenshtein u v i 0 = i 
levenshtein u v 0 j = j 
levenshtein u v i j = minimum [1 + levenshtein u v i (j - 1), 
    1 + levenshtein u v (i - 1) j, 
    bool2int (u !! (i - 1) /= v !! (j - 1)) + levenshtein u v (i - 1) (j - 1) ] 

distance :: Eq a => [a] -> [a] -> Int 
distance u v = levenshtein u v (length u) (length v) 

，對於長度爲10或更多的串中執行時間的差的蟒和Haskell之間的10各種權力。還有一些粗糙的時間測量（掛鐘，因爲我還沒有在haskell中發現一個clock（）命令），似乎我的haskell實現並沒有花費O（mn），而是其他一些其他的高速增長的成本。

注意：我不希望我的haskell實現與Python腳本競爭速度。我只是希望它運行在一個「明智」的時間，而不是整個宇宙存在的時間的倍數。

問題：

• 我在做什麼錯了，我的實現是這麼混賬的慢？
• 如何解決？
• 談到「懶惰評價」：我認爲如果levenshtein "cat" "kit" 2 2被稱爲三次，它只計算一次。這是正確的嗎？
• 我的bool2int必須有內置的東西，對不對？
• 任何其他意見，如果它推動我在粗略的道路上掌握Haskell前進高度讚賞。

編輯：這裏去的Python代碼進行比較：

#! /usr/bin/python3.2 
# -*- coding, utf-8 -*- 

class Levenshtein: 
     def __init__ (self, u, v): 
       self.__u = ' ' + u 
       self.__v = ' ' + v 
       self.__D = [ [None for x in self.__u] for x in self.__v] 
       for x, _ in enumerate (self.__u): self.__D [0] [x] = x 
       for x, _ in enumerate (self.__v): self.__D [x] [0] = x 

     @property 
     def distance (self): 
       return self.__getD (len (self.__v) - 1, len (self.__u) - 1) 

     def __getD (self, i, j): 
       if self.__D [i] [j] != None: return self.__D [i] [j] 
       self.__D [i] [j] = min ([self.__getD (i - 1, j - 1) + (0 if self.__v [i] == self.__u [j] else 1), 
            self.__getD (i, j - 1) + 1, 
            self.__getD (i - 1, j) + 1]) 
       return self.__D [i] [j] 

print (Levenshtein ('first string', 'second string').distance) 

Answer 1

我在做什麼錯，我的執行是如此緩慢？

你的算法具有指數複雜性。你似乎認爲這些電話正在爲你記憶，但事實並非如此。

如何解決？

您需要添加顯式記憶，可能使用數組或其他方法。

淺談「懶評」：我收集說如果levenshtein "cat" "kit" 2 2被稱爲三次，它只計算一次。這是正確的嗎？

不，Haskell不會自動記憶。懶惰意味着如果你做let y = f x in y + y，那麼f x只會被求值（一次），如果求和的結果是要求的。它確實是而不是的意思是f x + f x只會在f x的一個調用中評估。當你想分享子表達式的結果時，你必須明確。

我的bool2int必須有內置的東西，對吧？

是的，有一個instance Enum Bool，所以你可以使用fromEnum。

*Main> fromEnum True 
1 
*Main> fromEnum False 
0 

任何其他輸入，如果它塞到我未來的坎坷不平的小路，以掌握哈斯克爾上高度讚賞。

雖然從頭開始編寫的東西可能是有趣和教育，它要學會做這樣的共同的東西，當Hackage採取的許多大圖書館的優勢是非常重要的。

例如，在edit-distance package中存在Levenshtein距離的實現。

---

我翻譯你的Haskell代碼在Python進行比較：

def levenshtein(u, v, i, j): 
    if i == 0: return j 
    if j == 0: return i 

    return min(1 + levenshtein(u, v, i, (j-1)), 
       1 + levenshtein(u, v, (i-1), j), 
       (u[i-1] != v[j-1]) + levenshtein(u, v, (i-1), (j-1))) 

def distance(u, v): 
    return levenshtein(u, v, len(u), len(v)) 

if __name__ == "__main__": 
    print distance("abbacabaab", "abaddafaca") 

即使沒有固定O（n）的索引問題是chrisdb pointed out in his answer，這個性能比哈斯克爾版本慢編譯時：

$ time python levenshtein.py 
6 

real 0m4.793s 
user 0m4.690s 
sys 0m0.020s 

$ time ./Levenshtein 
6 

real 0m0.524s 
user 0m0.520s 
sys 0m0.000s 

當然，它們都輸出到編輯距離包中正確記憶的版本：

$ time ./LevenshteinEditDistance 
6 

real 0m0.015s 
user 0m0.010s 
sys 0m0.000s 

---

下面是使用Data.Array簡單memoized實現：

import Data.Array 

distance u v = table ! (m, n) 
    where table = listArray ((0, 0), (m, n)) [levenshtein i j | i <- [0..m], j <- [0..n]] 

     levenshtein 0 j = j 
     levenshtein i 0 = i 
     levenshtein i j = minimum [ 1 + table!(i, j-1) 
            , 1 + table!(i-1, j) 
            , fromEnum (u'!(i-1) /= v'!(j-1)) + table!(i-1, j-1) ] 

     u' = listArray (0, m-1) u 
     v' = listArray (0, n-1) v 

     m = length u 
     n = length v 

main = print $ distance "abbacabaab" "abaddafaca" 

它也執行你原來的Python代碼：

$ time python levenshtein-original.py 
6 

real 0m0.037s 
user 0m0.030s 
sys 0m0.000s 
$ time ./LevenshteinArray 
6 

real 0m0.017s 
user 0m0.010s 
sys 0m0.000s 

Answer 2

它看起來對我來說，可能的原因是使用的！隨機訪問。 Haskell列表是鏈表，不太適合需要隨機訪問而不是順序訪問的算法。

你可能想嘗試用更適合隨機訪問的東西替換列表。如果您對字符串感興趣，可以使用Data.Text或ByteStrings，它們是基礎數組，並且應該很快。或者你可以使用類似Data.Vector的東西。

編輯：實際上，它看起來像Data.Text將具有相同的問題，因爲文檔說索引是O（n）。可能轉換爲矢量將是最好的。