data-structures - 文字列の数を追加/検索/保持するデータ構造は?

Question

次の操作をすばやくサポートするデータ構造を見つけようとしています。

• 文字列を追加します (存在しない場合は追加し、存在する場合は単語のカウンターをインクリメントします)
• 指定された文字列をカウントします (文字列で検索してからカウンターを読み取ります)

ハッシュテーブルとトライの間で議論しています。私の理解では、衝突を回避する限り、ハッシュ テーブルの検索と追加は高速です。事前に自分の入力がわからない場合は、試してみたほうがよいでしょうか?

Answer 1

それは、「キー」として使用する文字列のタイプに大きく依存します。可変性の高い文字列を使用していて、文字列に適切なハッシュ アルゴリズムがない場合は、トライがハッシュよりも優れている可能性があります。

ただし、適切なハッシュがあれば、ルックアップはトライよりも高速になります。(ただし、非常に悪いハッシュが与えられた場合は、その逆になります。) 入力がわからないが、適切なハッシュ アルゴリズムがある場合は、個人的にはハッシュを使用することを好みます。

また、最新の言語/フレームワークのほとんどは非常に優れたハッシュ アルゴリズムを備えているため、ほとんど作業を行わずにハッシュを使用して優れたルックアップを実装できる可能性があります。これは非常にうまく機能します。

Answer 2

トライしても大したことはありません。プレフィックスが重要な場合にのみ興味深いものです。ハッシュ テーブルはより単純で、言語自体 (Ruby、Python など) の直接の一部ではないにしても、通常は言語の標準ライブラリの一部です。Ruby でこれを行う非常に簡単な方法を次に示します。

strings = %w(some words that may be repeated repeated)
counts = Hash.new(0)
strings.each { |s| counts[s] += 1 }
#counts => {"words"=>1, "be"=>1, "repeated"=>2, "may"=>1, "that"=>1, "some"=>1}

補遺: C++ の場合、おそらくBoost のハッシュ実装を使用できます。

Answer 3

どちらかがかなり高速です。

衝突を完全に回避する必要はありません。

パフォーマンスをもう少し詳しく見てみると、通常、ハッシュ テーブルはツリーよりも高速ですが、HT の代わりにツリーを使用したという理由だけで実際のプログラムの実行が遅すぎるかどうかは疑問であり、一部のツリーは一部のハッシュ テーブルよりも高速です。

他に言えることは、ハッシュ テーブルはツリーよりも一般的です。

複雑なツリーの利点の 1 つは、アクセス時間を予測できることです。ハッシュ テーブルと単純なバイナリ ツリーを使用すると、表示されるパフォーマンスはデータに依存し、HT のパフォーマンスは、実装の品質とデータ セット サイズに関するその構成に強く依存します。