6

テーブル ルックアップを行う必要がある C 言語アプリがあります。

エントリは文字列です。すべてはランタイムの開始時に認識されます。テーブルは一度初期化され、その後何度も検索されます。テーブルは変更される可能性がありますが、基本的にはアプリが最初からやり直すのと同じです。これは、完全なハッシュを使用できることを意味すると思いますか? ハッシュテーブルの初期化は 1 回だけなので、多少時間がかかっても問題ありません。

エントリ数は 3 ～ 100,000 で、それぞれが一意であり、80% のケースではエントリ数が 100 未満であると推定されます。そのような場合、単純な単純なルックアップは「十分に高速」です。(==誰も文句を言っていない)

ただし、10,000 以上のエントリがある場合、素朴なアプローチのルックアップ速度は受け入れられません。C で文字列のハッシュテーブル ベースの優れたルックアップ パフォーマンスを提供するための適切なアプローチは何ですか? Boost/etc のようなサードパーティの商用ライブラリを持っていないとします。どのハッシュ アルゴリズムを使用すればよいですか? どうやって決めるの？

4

3 に答える 3

4

単純な（線形を意味すると思います）アプローチが100エントリで問題ない場合（したがって、平均で50回の比較が行われます）、バイナリ検索は100,000エントリに対して十分です（最大17回の比較が必要です）。

したがって、私はハッシュをまったく気にしませんが、起動時に文字列テーブルをソートし (例: を使用qsort)、後でバイナリ検索を使用して (例: を使用bsearch)、エントリを検索することに頼ります。

于 2011-09-07T06:30:32.410 に答える
4

完全なハッシュを生成することは単純な問題ではありません。タスク専用のライブラリがあります。この場合、最も人気のあるものはおそらくCMPHです。私はそれを使用していないので、それ以上のことはできません。gperfは別のツールですが、コンパイル時に文字列を認識している必要があります (.so をコンパイルしてロードすることで回避できますが、やり過ぎです)。

しかし、率直に言って、少なくとも最初は二分探索を試みたいと思います。を使用して配列を並べ替えてqsortから、 で検索するbsearch(または自分でロールする) だけです。どちらもstdlib.hC89以降の一部です。

于 2011-09-07T06:19:47.547 に答える
0

(最大) テーブル サイズがわかっている場合、チェーンを使用した単純なハッシュテーブルの実装は非常に簡単です。サイズのオーバーヘッドは、アイテムごとにわずか 2 int です。適切なハッシュ関数を使用すると、ルックアップごとに平均で 1.5 個のプローブしか必要ありません。これは、100% ロードされたテーブルの場合です。

完全なハッシュの構築は、データが変更されない場合にのみ実現可能です。変更すると、再計算して再ハッシュする必要があります。これは、いくつかの追加の比較を行うよりもはるかにコストがかかります。

于 2011-09-07T09:56:55.800 に答える