Вопрос производительности хвостовой рекурсии Haskell для расстояний Левенштейна

Я еще не слежу за всей вашей второй попыткой, но, насколько я помню, идея алгоритма Левенштейна состоит в том, чтобы сохранить повторные вычисления с помощью матрицы. В первом фрагменте кода вы не делитесь какими-либо вычислениями, и поэтому вы будете повторять множество вычислений. Например, при вычислении ldist s1 s2 (5,5) вы будете производить расчет для ldist s1 s2 (4,4) как минимум три раза (один раз напрямую, один раз через ldist s1 s2 (4,5), один раз через ldist s1 s2 (5,4)).

Что вам нужно сделать, так это определить алгоритм для генерации матрицы (как список списков, если хотите). Я думаю, что это то, что делает ваш второй фрагмент кода, но, похоже, он сосредоточен на вычислении матрицы сверху вниз, а не на чистом построении матрицы в индуктивном стиле (рекурсивные вызовы в базовом случае довольно необычны) на мой взгляд). К сожалению, у меня нет времени, чтобы написать все это, но, к счастью, у кого-то есть: посмотрите первую версию по этому адресу: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#Haskell

Еще две вещи: во-первых, я не уверен, что алгоритм Левенштейна когда-либо сможет использовать только часть матрицы, поскольку каждая запись зависит от диагонального, вертикального и горизонтального соседей. Когда вам нужно значение для одного угла, вам неизбежно придется оценивать матрицу до другого угла. Во-вторых, эту строку match | foo = True | otherwise = False можно заменить просто на match = foo.

Раньше я использовал эту очень краткую версию с foldl и scanl из Викиучебников:

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)]

Я только что провел этот простой тест, используя 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
  ]

И версия Викиучебника значительно превосходит ваши обе:

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 все еще работает через пару минут.

Чтобы вычислить length, вам нужно оценить весь список. Это дорогая, O(n) операция. И что более важно, после этого список будет храниться в памяти до тех пор, пока вы не перестанете ссылаться на список (=> больший объем памяти). Эмпирическое правило заключается в том, чтобы не использовать length в списках, если ожидается, что списки будут длинными. То же самое относится и к (!!), он каждый раз идет с самого начала списка, так что это тоже O(n). Списки не разработаны как структура данных с произвольным доступом.

Лучший подход к спискам Haskell — использовать их частично. Сгибы обычно подходят для решения подобных задач. И расстояние Левенштейна можно рассчитать таким образом (см. ссылку ниже). Я не знаю, есть ли лучшие алгоритмы.

Другой подход заключается в использовании другой структуры данных, а не списков. Например, если вам нужен произвольный доступ, известная длина и т. д., взгляните на Data.Sequence.Seq.

Существующие реализации

Второй подход использовался в этой реализации метода Левенштейна. расстояние в Haskell (с использованием массивов). Вы можете найти реализацию на основе foldl в первом комментарии. Кстати, foldl' обычно лучше, чем foldl.

Можно использовать алгоритм O(N*d), где d — расстояние Левенштейна. Вот реализация в Lazy ML от Lloyd. Allison, который использует лень для повышения сложности. Это работает, вычисляя только часть матрицы, то есть область вокруг главной диагонали, ширина которой пропорциональна расстоянию Левенштейна.

Изменить: я только что заметил, что это было переведено to haskell с красивым изображением, показывающим, какие элементы матрицы вычисляются. Это должно быть значительно быстрее, чем приведенные выше реализации, когда последовательности очень похожи. Используя приведенный выше тест:

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

Более интуитивно понятное решение с использованием пакета data-memocombinators. Кредит принадлежит этому ответу. Тесты приветствуются, так как все решения, представленные здесь, кажутся намного медленнее, чем python-Levenshtein, который предположительно был написан на C. Обратите внимание, что я пытался заменить строки массивами символов, но безрезультатно.

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) ]