Haskell Schwanz-Rekursion Leistung Frage für Levenshtein Entfernungen

Question

Ich spiele um mit der Berechnung Levenshtein Entfernungen in Haskell, und ist ein wenig frustriert mit das folgende Leistungsproblem. Wenn Sie es am meisten ‚normalen‘ Weg für Haskell, wie unter (dist) implementieren, alles funktioniert gut:

dist :: (Ord a) => [a] -> [a] -> Int
dist s1 s2 = ldist s1 s2 (L.length s1, L.length s2)

ldist :: (Ord a) => [a] -> [a] -> (Int, Int) -> Int
ldist _ _ (0, 0) = 0
ldist _ _ (i, 0) = i
ldist _ _ (0, j) = j
ldist s1 s2 (i+1, j+1) = output
  where output | (s1!!(i)) == (s2!!(j)) = ldist s1 s2 (i, j)
               | otherwise = 1 + L.minimum [ldist s1 s2 (i, j)
                                          , ldist s1 s2 (i+1, j)
                                          , ldist s1 s2 (i, j+1)]

Aber, wenn Sie Ihr Gehirn ein wenig biegen und implementieren sie als dist‘, führt er VIEL schneller (ca. 10x).

dist' :: (Ord a) => [a] -> [a] -> Int
dist' o1 o2 = (levenDist o1 o2 [[]])!!0!!0 

levenDist :: (Ord a) => [a] -> [a] -> [[Int]] -> [[Int]]
levenDist s1 s2 arr@([[]]) = levenDist s1 s2 [[0]]
levenDist s1 s2 arr@([]:xs) = levenDist s1 s2 ([(L.length arr) -1]:xs)
levenDist s1 s2 arr@(x:xs) = let
    n1 = L.length s1
    n2 = L.length s2
    n_i = L.length arr
    n_j = L.length x
    match | (s2!!(n_j-1) == s1!!(n_i-2)) = True | otherwise = False
    minCost = if match      then (xs!!0)!!(n2 - n_j + 1) 
                            else L.minimum [(1 + (xs!!0)!!(n2 - n_j + 1))
                                          , (1 + (xs!!0)!!(n2 - n_j + 0))
                                          , (1 + (x!!0))
                                          ]
    dist | (n_i > n1) && (n_j > n2)  = arr 
         | n_j > n2  = []:arr `seq` levenDist s1 s2 $ []:arr
         | n_i == 1 = (n_j:x):xs `seq` levenDist s1 s2 $ (n_j:x):xs
         | otherwise = (minCost:x):xs `seq` levenDist s1 s2 $ (minCost:x):xs
    in dist 

Ich habe alle üblichen seq Tricks in der ersten Version versucht, aber nichts scheint es zu beschleunigen. Dies ist ein wenig unbefriedigend für mich, weil ich die erste Version zu erwarten sein schneller , weil es nicht die gesamte Matrix bewerten muss, nur die Teile die es braucht.

Wer weiß, wenn es möglich ist, diese beiden Implementierungen erhalten in ähnlicher Weise durchzuführen, oder bin ich ernte nur die Vorteile der Schwanz-Rekursion Optimierungen im letzteren, und muß daher mit seiner Unlesbarkeit leben, wenn ich Leistung will?

Danke, Orion

Answer 1

Ich habe nicht alle Ihre zweiten Versuch folgen nur noch, aber soweit ich mich erinnere die Idee hinter dem Levenshtein Algorithmus wiederholt Berechnung ist durch die Verwendung einer Matrix zu speichern. Im ersten Teil des Codes, teilen Sie keine Berechnung und so werden Sie viele Berechnungen wiederholen. Wenn zum Beispiel ldist s1 s2 (5,5) Berechnen Sie die Berechnung für ldist s1 s2 (4,4) mindestens drei getrennte Male (einmal direkt, einmal über ldist s1 s2 (4,5), einmal über ldist s1 s2 (5,4)) machen.

Was Sie tun sollten, ist, einen Algorithmus definieren die Matrix zum Erzeugen (als Liste von Listen, wenn Sie mögen). Ich denke, das ist, was Ihr zweites Stück Code tut, aber es scheint auf der Berechnung die Matrix in einem top-down zu konzentrieren, anstatt die Matrix sauber in einem induktiven Stil Aufbau (die rekursiven Aufrufe in dem Basisfall sind recht ungewöhnlich zu meinem Auge). Leider habe ich keine Zeit, die ganze Sache zu schreiben, aber zum Glück hat jemand anderes: Blick auf die erste Version an dieser Adresse: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#Haskell

Noch zwei Dinge: Erstens, ich bin nicht sicher, dass der Levenshtein Algorithmus immer nur einen Teil der Matrix ohnehin verwenden kann, da jeder Eintrag auf den Diagonalen, vertikale und horizontale Nachbarn abhängen. Wenn Sie den Wert für eine Ecke benötigen, werden Sie unweigerlich die Matrix den ganzen Weg auf die andere Ecke bewerten müssen. Zweitens kann, dass match | foo = True | otherwise = False Linie durch einfaches match = foo ersetzt werden.

Answer 2

In der Vergangenheit habe ich diese sehr kurze Version mit foldl und scanl verwendet von Wikibooks :

distScan :: (Ord a) => [a] -> [a] -> Int
distScan sa sb = last $ foldl transform [0 .. length sa] sb
  where
    transform xs@(x:xs') c = scanl compute (x + 1) (zip3 sa xs xs')
       where
         compute z (c', x, y) = minimum [y + 1, z + 1, x + fromEnum (c' /= c)]

Ich lief diese einfache Benchmark mit Criterion :

test :: ([Int] -> [Int] -> Int) -> Int -> Int
test f n = f up up + f up down + f up half + f down half
  where
    up = [1..n]
    half = [1..div n 2]
    down = reverse up

main = let n = 20 in defaultMain
  [ bench "Scan" $ nf (test distScan) n
  , bench "Fast" $ nf (test dist') n
  , bench "Slow" $ nf (test dist) n
  ]

Und die Wikibooks Version schlägt beide von Ihnen ziemlich dramatisch:

benchmarking Scan
collecting 100 samples, 51 iterations each, in estimated 683.7163 ms...
mean: 137.1582 us, lb 136.9858 us, ub 137.3391 us, ci 0.950

benchmarking Fast
collecting 100 samples, 11 iterations each, in estimated 732.5262 ms...
mean: 660.6217 us, lb 659.3847 us, ub 661.8530 us, ci 0.950...

Slow noch nach ein paar Minuten.

Answer 3

zu berechnen length müssen Sie die ganze Liste bewerten. Es ist ein teurer, O (n), den Betrieb. Und was noch wichtiger ist, danach wird die Liste im Speicher gehalten werden, bis Sie die Liste stoppen Referenzierung (=> größerer Speicherbedarf). Als Faustregel ist nicht zu verwenden length auf Listen, wenn Listen lange erwartet werden. Dasselbe bezieht sich auf (!!), schon aus dem Kopf der Liste jedes Mal geht, so ist es O (n) zu. Listen werden nicht als Schreib-Lese-Datenstruktur entworfen.

Besserer Ansatz mit Haskell-Listen ist sie teilweise zu konsumieren. Folds sind in der Regel die Art und Weise ähnliche Probleme zu gehen. Und Levenshtein Abstand kann auf diese Weise berechnet werden (siehe Link unten). Ich weiß nicht, ob es bessere Algorithmen.

Ein weiterer Ansatz ist es, eine andere Datenstruktur zu verwenden, keine Listen. Zum Beispiel, wenn Sie benötigen Direktzugriff, bekannte Länge usw. einen Blick auf Data.Sequence.Seq .

Vorhandene Implementierungen

Der zweite Ansatz hat sich in dieser Implementierung verwendet der Abstand in Levenschtein Haskell (unter Verwendung von Arrays). Sie können dort foldl-basierte Implementierung in den ersten Kommentar finden. BTW, foldl' ist in der Regel besser als foldl.

Answer 4

Es ist möglich, eine O (N * d) Algorithmus zu haben, wobei D der Abstand Levenshtein ist. Hier ist ein Implementierung in Faul ML von Lloyd Allison, die die verbesserte Komplexität zu erreichen Faulheit ausnutzt. Dies funktioniert, indem nur ein Teil der Matrix-Berechnung, die ein Bereich um die Hauptdiagonale ist, die in der Breite zum Levenshtein Abstand proportional ist.

Edit: Ich habe gerade bemerkt, dies wurde Haskell mit einem schönen Bild anzeigt, welche Elemente der Matrix berechnet werden. Dies sollte deutlich schneller als die obigen Implementierungen sein, wenn die Sequenzen sehr ähnlich sind. Unter Verwendung der obigen Benchmark:

benchmarking Scan
collecting 100 samples, 100 iterations each, in estimated 1.410004 s
mean: 141.8836 us, lb 141.4112 us, ub 142.5126 us, ci 0.950

benchmarking LAllison.d
collecting 100 samples, 169 iterations each, in estimated 1.399984 s
mean: 82.93505 us, lb 82.75058 us, ub 83.19535 us, ci 0.950

Answer 5

Eine intuitive Lösung mit dem daten memocombinators Paket. Kredit geht an href="https://stackoverflow.com/a/5554082/1243926">. Benchmarks sind willkommen, da alle Lösungen, die hier vorgestellt erscheinen viel, viel langsamer als python-Levenshtein , die vermutlich in C. Hinweis geschrieben wurde, dass ich versuchte Arrays von Zeichen anstelle von Strings ohne Wirkung zu ersetzen.

import Data.MemoCombinators (memo2, integral)

levenshtein :: String -> String -> Int
levenshtein a b = levenshtein' (length a) (length b) where
  levenshtein' = memo2 integral integral levenshtein'' where
    levenshtein'' x y -- take x characters from a and y characters from b
      | x==0 = y
      | y==0 = x
      | a !! (x-1) == b !! (y-1) = levenshtein' (x-1) (y-1)
      | otherwise = 1 + minimum [ levenshtein' (x-1) y, 
        levenshtein' x (y-1), levenshtein' (x-1) (y-1) ]