10

大学時代のお気に入りのデータ構造の 1 つはTrieでした。プレフィックスが共有されている場合、大量の文字列セットを保持するための優れたデータ構造です。セット内の文字列の数に関係なく、文字列の O(|length|) で検索が行われるため、ルックアップも優れています。

比較すると、バランスの取れたツリーは、セット項目の数に O(log N) と、比較のために支払う金額を加えたものになります。ハッシュテーブルには、ハッシュ計算、比較などが含まれます。

したがって、ほとんどの言語の標準ライブラリに Trie の実装がないことは、私にとって驚くべきことです。

私が思いついた唯一の理由は、メモリアクセスコストが高すぎる可能性があるということでした. ツリー ルックアップを実行する場合に O(log N) の場所を調査するのではなく、O(|length|) の異なる場所を実行していないため、すべての結果が得られます。文字列が長い場合、これはやりすぎになる可能性があります。

だから私は疑問に思っています：私が今説明した懸念はいくらですか？文字列の大規模なセットまたはマップを格納する必要がある場合はどうしますか?

4

5 に答える 5

7

これまで気にしたことはなかったのですが、そういわれると、標準の Trie 実装が便利な場合があります。一方、私の知る限り、Tries は Python や Perl など、現在使用している文字列に精通した言語で使用されています。

私が最後に確認したのはかなり前のことですが、BSD カーネル コードはコード内で Tries (Patricia Tries) を使用して、パケットを送信するための最適なインターフェイスを選択していました。ウィキペディアに情報があるようです。

于 2009-03-09T00:16:04.150 に答える
4

2 つのサンプル アプリを作成して、どちらのパフォーマンスが優れているかを確認できます。ページ フォールトが発生しないと仮定すると、メモリ アクセスは安価です。それからそれは非常に高価です。クライアント アプリケーションの開発では、ほとんどの場合、メモリにアクセスするよりも処理する方が適切です。まさにこの理由からです。最新のプロセッサはとてつもなく高速ですが、キャッシュ ミスは依然として悪影響を及ぼします。

于 2009-03-09T00:13:59.913 に答える