3

unordered_mapいくつかのフェーズで動作する、パフォーマンスが最適化されたバリアントを実装したいと考えています。

  1. 初期化：約100個の要素をstd::map
  2. 準備：いくつかの魔法std::mapをかけて、のバリアントに変換しますstd::unordered_map
  3. 作業: 大量の (無制限の) ルックアップを実行します。挿入・削除禁止

「作業」フェーズをできるだけ速くするために、指定されたキーのセット (初期化フェーズで収集) に対して衝突のないハッシュ関数を選択したいと思います。

このトリックでどれだけパフォーマンスが向上するかを測定したいと思います。したがって、これは実験であり、製品コードに入る可能性があります。

標準ライブラリには、この実装のためのunordered_map機能がありますか? または、代わりに独自の実装を作成する必要がありますか?

4

3 に答える 3

6

「衝突管理」API は次のとおりです。

size_type bucket_count() const;
size_type max_bucket_count() const;

size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;

local_iterator       begin(size_type n);
local_iterator       end(size_type n);
const_local_iterator begin(size_type n) const;
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;

簡単に言えば、bucket_size(n)n 番目のバケットの衝突数を示します。キーでバケットを検索でき、local_iterator でバケットを反復処理できます。

ハッシュ関数を変更するには、古いハッシュ関数から新しいコンテナーに新しいコンテナーを割り当て/構築します。

于 2011-04-11T15:13:54.880 に答える
2

読み取りが多く、書き込みが少ない場合は、ベクトルをマップとして使用できます。lower_boundよりも効果的でmapあり、メモリからのスペースをあまり使用しないため、非常に一般的です。

bool your_less_function( const your_type &a, const your_type &b )
{
  // based on keys
  return ( a < b );
}
...
std::vector<your_type> ordered-vector;

値を追加する場合:

...
// First 100 values
ordered-vector.push_back(value)
...
// Finally. The vector must be sorted before read.
std::sort( ordered-vector.begin(), ordered-vector.end(), your_less_function );

データを求める場合:

std::vector<your_type>::iterator iter = std::lower_bound( ordered-vector.begin(), ordered-vector.end(), value, your_less_function );
if ( ( iter == ordered-vector.end() ) || your_less_function( *iter, value ) )
  // you did not find the value
else
  // iter contains the value

残念ながら注文ですが、本当に速いです。

于 2011-04-11T14:44:58.060 に答える
0

衝突の数は、バケットの数によって異なります。ブーストのドキュメントに従って、再ハッシュ関数を使用してバケット数を 100 に設定すると便利ですか?

于 2011-04-11T14:39:27.947 に答える