Левенштейн расстояние стоимость

Question

Я новичок в haskell и столкнулся с проблемой производительности, которая настолько серьезна, что это должен быть мой код, а не платформа haskell.

У меня есть 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 и более имеет различные степени 10 между python и haskell.Также с некоторыми грубыми измерениями времени (настенные часы, так как я пока не нашел команду clock () в haskell), кажется, что моя реализация на 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

Любой другой вход будет высоко оценен, если он подтолкнет меня к трудному пути к овладению haskell.

Хотя написание материала с нуля может быть увлекательным и познавательным, важно научиться использовать множество замечательных библиотек в Hackage при выполнении подобных вещей.

Например, существует реализация расстояния Левенштейна в пакете edit-distance .

---

Я перевел ваш код на 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 указал в своем ответе , при компиляции это работает медленнее, чем версия на Haskell:

$ 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:

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). Вероятно, было бы лучше преобразовать в вектор.