1

私は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以上の文字列の実行時間の違いは、pythonとhaskellの間でさまざまな10の累乗です。また、大まかな時間測定（これまでhaskellでclock（）コマンドを見つけられなかったので壁掛け時計）を使用すると、私のhaskell実装のコストはO（mn）ではないようですが、他の途方もなく急速に増加するコストです。

注意： haskellの実装がPythonスクリプトと速度的に競合することは望ましくありません。宇宙全体が存在する時間の倍数ではなく、「賢明な」時間で実行したいだけです。

質問：

  • 私の実装がとても遅いので、私は何を間違っていますか？
  • それを修正する方法は？
  • 「遅延評価」と言えばlevenshtein "cat" "kit" 2 2、3回呼ばれると1回しか計算されないということです。これは正しいですか？
  • 私の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)
4

2 に答える 2

5

私の実装がとても遅いので、私は何を間違っていますか？

アルゴリズムは指数関数的に複雑です。呼び出しがメモ化されていると想定しているようですが、そうではありません。

それを修正する方法は？

おそらく配列または他の方法を使用して、明示的なメモ化を追加する必要があります。

「遅延評価」と言えばlevenshtein "cat" "kit" 2 2、3回呼ばれると1回しか計算されないということです。これは正しいですか？

いいえ、Haskellは自動メモ化を行いません。怠惰とはlet y = f x in y + y、そうするとf x、合計の結果が要求された場合にのみ（1回）評価されることを意味します。への1回の呼び出しで評価されるという意味ではありません。部分式の結果を共有する場合は、明示的にする必要があります。f x + f xf x

私には何かが組み込まれているに違いありませんbool2intよね？

はい、がありinstance Enum Boolますので、を使用できますfromEnum。

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

Haskellをマスターするための大まかな道を私に突きつければ、他のどんな入力も高く評価されます。

ゼロからものを書くことは楽しくて教育的かもしれませんが、このような一般的なことをするときは、 Hackageの多くの素晴らしいライブラリを利用することを学ぶことが重要です。

たとえば、edit-distanceパッケージに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")

chrisdbが彼の答えで指摘したO（n）インデックスの問題を修正しなくても、これはコンパイル時に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

もちろん、どちらもedit-distanceパッケージで適切にメモ化されたバージョンに負けます。

$ 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
于 2011-07-16T17:04:10.243 に答える
2

考えられる原因はの使用であるように私には見えます!! ランダムアクセス用。Haskellリストはリンクリストであり、シーケンシャルアクセスではなくランダムアクセスを必要とするアルゴリズムにはあまり適していません。

リストをランダムアクセスにより適したものに置き換えてみてください。文字列に関心がある場合は、Data.TextまたはByteStringsを使用できます。これらは基本的に配列であり、高速である必要があります。または、Data.Vectorのようなものを使用することもできます。

編集：実際には、ドキュメントにはインデックス作成がO（n）であると記載されているため、Data.Textでも同じ問題が発生するようです。おそらくベクトルに変換するのが最善でしょう。

于 2011-07-16T16:59:53.777 に答える