1

皆さん、問題を解決するために動的計画法のアプローチを使用しています。アプローチの簡単な概要は次のとおりです。

  1. 生成された各値は、25 個の一意のキーを使用して識別されます。
  2. これらの 25 個のキーを使用して、boost::hash_combineを使用してハッシュ テーブルのシードを生成します。

  3. として宣言されたハッシュテーブルに値を保存します

    boost::unordered_map<Key_Object, Data_Object, HashFunction> hashState;

  4. アルゴリズムの時間プロファイリングを行ったところ、実行時間のほぼ95%がデータの取得/ハッシュ テーブルへの挿入に費やされていることがわかりました。

  5. これらは私のハッシュテーブルの詳細でした

    hashState.size() 1880

    hashState.load_factor() 0.610588

    hashState.bucket_count() 3079

    hashState.max_size() 805306456

    hashState.max_load_factor() 1

    hashState.max_bucket_count() 805306457

次の2つの質問があります

  1. ハッシュ テーブルの挿入/取得操作のパフォーマンスを向上させるためにできることはありますか?

  2. C++ STL には、私の要件にも合う hash_multimap があります。ライブラリunordered_mapは、挿入/取得のパフォーマンスに関してhash_multimapとどのように比較されますか。

4

2 に答える 2

0

使用しているハッシュ関数がボトルネックではないことを確認しますか？ハッシュ関数を使用する時間の割合はどれですか？同じテストを実行して、挿入/取得をハッシュへの単純な呼び出しに置き換えることはできますか？

于 2010-05-03T21:47:03.893 に答える
0

ハッシュ関数が原因でない場合、最善の方法はおそらく別のマップ実装を使用することです。キーが非常に大きいため、Boost.Intrusive ライブラリunordered_mapから使用するのが最適なオプションかもしれません。または、クローズド ハッシュを試すこともできます: Google SparseHashまたはMCT。ただし、要素が十分に小さい場合はクローズド ハッシュが推奨されるため、プロファイリングは確かに必要です。(SparseHash はより確立されており、十分にテストされていますが、MCT はそれら/メソッドを必要としません)。set_empty()set_deleted()

編集：

私が言及したBoostライブラリには侵入マップがなく、セットとマルチセットのみがあることに気付きました。それでも、2 つのクローズド ハッシュ ライブラリを試すことができます。

編集2：

STLhash_mapは標準ではありません。おそらく何らかの拡張であり、コンパイラ間で移植できません。

于 2010-05-02T21:50:37.260 に答える