5

キーが修正され（初期化中に修正され）、ルックアップが高速になるマップを探しています。後で要素を追加/更新することはサポートされない場合があります。キーのリストを検索し、後で検索するのが高速になるように関数を定式化するアルゴリズムはありますか？私の場合、キーは文字列です。

アップデート：

キーはコンパイル時に不明です。ただし、アプリケーションの初期化時に。後でそれ以上の挿入はありませんが、たくさんのルックアップがあります。したがって、ルックアップを最適化する必要があります。

4

4 に答える 4

2

CMPHはあなたが探しているものかもしれません。基本的に、これはコンパイル時にセットを必要としgperf ません。

もちろんstd::unordered_map、C ++ 11の場合と同様に、いくつかの衝突が発生する可能性はありますが、それでもかまいません。

文字列を検索するので、文字列の場合、特にそれらが多数ある場合は、トライ（さまざまなトライフレーバー、クリティカルビット、またはそれらが持つファンキーな名前のいずれか）も調べる価値があります。自由に利用できる無料のトライ実装がたくさんあります。
試行の利点は、文字列をインデックス圧縮できるため、使用するメモリが少なくなり、データがキャッシュにある可能性が高くなることです。また、アクセスパターンはランダム性が低く、キャッシュにも適しています。ハッシュテーブルは、値とハッシュを格納する必要があり、多かれ少なかれランダムに（ランダムではなく、予測できない形で）メモリにインデックスを付けます。トライ/トライのような構造は、理想的には、各ノードの共通のプレフィックスからキーを区別する1つの追加ビットのみを必要とします。

（ちなみに、このような場合、big-Oはそのようなことを考慮しないため、O（log（N））はO（1）よりも高速である可能性があります。）

于 2011-12-08T10:21:06.403 に答える
1

これらは明確なものであることに注意してください。上限が必要ですか、高速の標準レートが必要ですか、それともこれまでで最速のルックアップが必要ですか、質問はありませんか？最後のものはあなたに費用がかかります、最初の2つは相反する目標かもしれません。

入力に基づいて完全なハッシュ関数（つまり、入力セットの衝突がないもの）を作成することを試みることができます。これはどういうわけか解決された問題です（例えば、 this、this）。ただし、通常はソースコードを生成し、ハッシュ関数の生成にかなりの時間を費やす場合があります。

これを変更するには、一般的なハッシュ関数（shift-multiply-addなど）を使用して、適切なパラメーターを総当たりで検索します。

これは、いくつかの文字列比較のコストとトレードオフする必要があります（照合する必要がない場合はそれほど高価ではありません）。

もう1つのオプションは、2つの異なるハッシュ関数を使用することです。これにより、1回のルックアップのコストが増加しますが、エイリアンが時計の針を盗むよりも劣化する可能性がわずかに低くなります。これが典型的な文字列とまともなハッシュ関数で問題になる可能性はかなり低いです。

于 2011-12-08T10:36:29.880 に答える
0

google-sparsehashをお試しください：http ：//code.google.com/p/google-sparsehash/

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed.
于 2011-12-08T10:21:01.740 に答える
0

同様のトピック（コンパイル時に既知の（数）アイテム）で、私はこれを作成しました：既知の整数キーのセットのルックアップ。オーバーヘッドが低く、完全なハッシュは必要ありません。幸いなことに、それはCにあります;-)

于 2011-12-08T14:46:26.247 に答える