3

レーベンシュタイン距離(編集距離)の通常の動的計画法のアルゴリズムを実装したいとしましょう。再帰を考え出すのはとても簡単です:

editDistance [] ys = length ys
editDistance xs [] = length xs
editDistance (x:xs) (y:ys) 
  | x == y = editDistance xs ys
  | otherwise = minimum [
      1 + editDistance xs (y:ys),
      1 + editDistance (x:xs) ys,
      1 + editDistance xs ys]

これは指数関数的な実行時間の影響を受けるため、関数をメモする必要があります。私は Data.Memocombinators を使用してこれを行いたいと考えており、いくつかの方法を試しました。これが私の現在の試みです：

import qualified Data.MemoCombinators as M

memLength str = 
  M.wrap 
    (\i -> drop i str) 
    (\xs -> length str - length xs)
    (M.arrayRange (0,length str))

elm xs ys = (M.memo2 memListx memListy editDistance) xs ys
  where
    memListx = memLength xs
    memListy = memLength ys

ただし、少なくとも多項式であるため、メモ化によって実行時間が大幅に改善されると予想されますが、メモ化には何の効果もないようです。実装の何が問題になっていますか? 編集距離の高レベルの定義を可能な限り維持しながら、適切な実行時間を取得するにはどうすればよいですか?

4

1 に答える 1

3

あなたが投稿したコードが実際にあなたがやっていることであるなら、あなたはそれを間違っています! :-)。再帰関数をメモ化する場合は、再帰バージョンの呼び出しをメモ化バージョンに戻す必要があります。例：

editDistance (x:xs) (y:ys)
  | x == y = elm xs ys
  | ...

それ以外の場合は、完全な再帰計算を行い、最終結果のみを保存します。中間結果を保存する必要があります。

ここで別の問題があります。elm のメモ テーブルは、その引数に依存するべきではありません (理想的には、引数に言及することさえすべきではないため、依存関係を把握するのに十分なほどスマートなコンパイラーに依存しないでください)。メモ テーブルが引数に依存する場合、異なる引数ごとに新しいテーブルを作成する必要があり、すべての引数に対してテーブルを共有する必要があります。引数の構造全体をメモするようなばかげたことを試すことができます。

elm = M.memo2 (M.list M.char) (M.list M.char)

それがスピードアップするかどうかを確認してください（前のトリックを組み込んでいます）。次に、リスト構造全体の代わりに長さだけを使用して、さらにブーストすることができます。

それが役に立ったことを願っています。

于 2011-03-27T04:07:20.493 に答える