4

おそらく多数のファイルとディレクトリ (通常は数十万個まで) に関するいくつかのデータをメモリに保持する必要があります。明らかなアプローチはDictionary<string, Something>、パスをキーとして a を使用することですが、これには 2 つの問題があります。

  • ファイルの多くは共通のパスの大部分を持っているため、各ファイルのフルパスを保存するのはおそらくメモリの無駄です
  • ディレクトリのすべての子孫に関するデータにすばやくアクセスできる必要があります。ディクショナリでは、これを行う唯一の方法は、各キーをテストし、指定されたパスで始まるかどうかを確認することですが、これは非常に非効率的です

この問題は、パスのセグメントを「文字」として、プレフィックス ツリー (またはtrie )を使用するための良い候補のようです。私はそれを実装しようとしましたが、プレフィックスによる検索のパフォーマンスはそれほど悪くありません (辞書よりも約 4 倍高速です) が、2 つの問題があります。

  • おそらく各ノードの子のリストのオーバーヘッドが原因で、メモリ消費量は削減されません
  • 構築時間は辞書よりもはるかに悪いです (コレクションを埋めるのに約 4 倍遅くなります)

それは非常に一般的な問題であるに違いないと確信しているので、私が気付いていないよく知られた解決策があるのではないでしょうか?

4

2 に答える 2

2

いくつかの一般的なアイデア:

まず、パトリシア トライは、トライのメモリ消費を改善するためのおそらく最もよく知られているアプローチです。これは、すべてのノードが 1 つの子を持つパスを 1 つのノードに圧縮し、パスに沿って文字を連結します。また、データを 2 進数のシーケンスとして見るバージョンもあります。これには、常に最大 2 つの子ノードがあるという利点があり、実装も簡単です。

次に、メモリ消費量は、特定のノードの子をどのように格納するかによって異なります。256 個のノードの配列を維持していますか? これは通常、直接ルックアップの最も効率的な方法ですが、メモリを最も消費し、すべての子を反復処理する必要がある場合は遅くなります。その他のオプションは次のとおりです。

  • ペアの配列を(letter, child node)保存する - これは、実際に関心のあるオブジェクトのみを保存するため、おそらく最もメモリ効率が高く、すべての子を反復処理するパフォーマンスも優れています。ただし、直接検索のためにすべてのペアをチェックする必要があります。これは通常、ルートから離れた場所では問題ありませんが、ルートの近くで問題になる可能性があります。

  • 文字を子ノードにマップする、ある種の辞書を各ノード内に格納します。これは、パフォーマンスに関して最もバランスが取れています。これにより、すべての操作で適度な速度が得られ、メモリ効率が多少向上します。

また、事前にコレクション全体を構築してクエリを実行するだけの場合、 Tarjan テーブルに基づいて子リンクを格納する方法があります。これにより、おそらく構築時間が長くなりますが、後でメモリとクエリ時間を節約できます。

于 2012-11-05T11:12:17.570 に答える
-1

プレフィックスツリーのようなアプローチはどうですか。つまり、保存したい場合

/root/x
/root/a/b
/root/a/c
/root/a/d
/root/a/e
/root/a/c/e
/root/a/c/f
Here is how your tree will look like. 
                       root
                     /    \
                    x   __ a __ 
                       /  / \   \ 
                     b   c    d   e
                        / \
                       e   f

すべてのディレクトリ名が一度だけ保存されるため、スペース効率が高くなります。また、挿入だけでなく検索も O(log(n)) になります

于 2012-11-07T09:18:34.503 に答える