6

私はaho-corasickアルゴリズムを試して、F＃を少し改善しようとしていますが、Trieの実装で問題が発生しました。これらはすべて変更可能であるか、末尾呼び出しを最適化できません。

私が見ることができる基本的な問題は、不変のデータ構造は、それらが指すものを変更できないため、「ボトムアップ」で構築する必要があるということです。したがって、オプションは、それらを可変にするか、進行中にノードを見つけるかのいずれかです。 （つまり、建設中の再帰）。

構造の末尾呼び出しを最適化して不変のトライデータ構造を作成する方法はありますか？（コピーによって効率が低下しないようにします）。

4

2 に答える 2

8

末尾呼び出しの最適化は、継続を使用することで排除できます。これは、キーと値がそれぞれstringとであるサンプルです。int

type Trie = 
 | Data of string * int * Trie * Trie 
 | Leaf 

let Insert start key value = 
  let rec inner current withNode = 
    match current with
    | Data (currentKey, currentValue, left, right) ->
      if key < currentKey then
        inner left (fun left -> Data (currentKey, currentValue, left, right))
      else 
        inner right (fun right -> Data (currentKey, currentValue, left, right))
    | Leaf -> withNode (Data (key, value, Leaf, Leaf))
  inner start (fun x -> x)

不変の構造に固執したい場合、コピーを削除するのは少し難しいです

于 2011-03-22T18:14:39.447 に答える
1

不変のトライで実装したコードレビューの投稿を調査しているときに、この投稿に出くわしました。

二分木ではなく、リンクにマップを使用するパフォーマンスがあります。

于 2016-11-05T00:30:06.553 に答える