12

State 型のキー (7 つの short int を持つクラス) と type の値Score(3 つの double 型のクラス) で構成される検索結果のキャッシュを実装しました。なんで？

編集：くそー！私のハッシュ関数は

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  // 1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

するのを忘れていたreturn retvalので、すべて衝突していました！unordered_map に、衝突の平均数を報告する hash_function_quality() 関数があればいいのにと思います。

4

4 に答える 4

17

unordered_map の速度は、ハッシュ関数の速度に正比例します。決してまっすぐな関係ではありません。たとえば、最も単純なハッシュ関数を使用する場合:

std::size_t myHash(MyObjectType _object){ return 1; }

最終的には、ハッシュされたコンテナーではなく、リストのように動作するコレクションになります。すべてのアイテムが 1 つのバケットにマップされ、目的のアイテムに到達するまでバケット全体をトラバースする必要があります (O(N) 時間かかる可能性があります)。

あなたがする必要があるのは、2つのことを見ることです：

  1. どのハッシュ関数を使用していますか? 処理にとんでもない時間がかかりますか?
  2. それは何回の衝突を生み出していますか？つまり、いくつの一意の要素が同じハッシュ値にマップされているでしょうか?

それらのいずれか自体がパフォーマンスを殺す可能性があり、殺します。

于 2011-01-31T01:25:27.603 に答える
10

std::unordered_mapハッシュ関数のため、要素数が少ない場合は一般的に低速です。一定の（-っぽい）時間がかかりますが、それでもかなりの時間がかかる場合があります。

std::map一方、より単純ですstd::unordered_map。そこにある要素にアクセスするのにかかる時間は要素の数に依存しますが、要素の数が増えるにつれてますます少なくなります。また、 std::map の大きな要因cも、 に比べて一般的に非常に小さいstd::unordered_mapです。

一般に、を使用する特別な理由がない限り、 よりも使用std::mapすることをお勧めします。これは、多数の要素がない場合に特に当てはまります。std::unordered_mapstd::unordered_map

于 2011-01-31T01:16:36.553 に答える
8

unordered_mapフードの下でハッシュテーブルを使用するため、ハッシュのパフォーマンスが低下する最も明白な理由は、衝突が多すぎるためです。キーのタイプに対してより良い結果が得られる、別のデフォルト以外のハッシュ関数の使用を検討することもできます。

于 2011-01-31T01:24:55.043 に答える
0

為に

unordered_map に、衝突の平均数を報告する hash_function_quality() 関数があればいいのにと思います。

以下の機能が参考になるかと思います。

unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.

を下げるload_factorと、ハッシュ関数が良くなります。

于 2011-01-31T03:38:26.747 に答える