C++でunordered_map/setのハッシュ関数が高速になっていますか？

デフォルト関数はstd :: hashです。私は計算時間を節約するためのより良いハッシュ関数があるのだろうか？整数キーと文字列キーの場合C++でunordered_map/setのハッシュ関数が高速になっていますか？

GoogleからCity Hashを整数と文字列キーの両方で試しましたが、そのパフォーマンスはstd :: hashより少し悪いです。

2017-02-20 SuperBald

一般的に言えば、ハッシングしているデータに関する特定のことがわかっている場合は、より高速なハッシュ関数を書くことができます。愚かな例として、17と535の2つの整数値しか扱っていない場合、それらを0と1に単純にハッシュすることができ、それは整数値の全範囲を扱う任意のハッシュ関数より速くなります。では、あなたがハッシュしている価値について特別なものは何ですか？ –

あなたが問題が解決した場合、質問を閉じることは常に良い考えです:) –

あなたは「より良い」という意味で説明する必要がありますか？最速のハッシュ関数は単に値を使用するだけですが、それは役に立たないです。より具体的な答えは、あなたの記憶の制約と、衝突の可能性のあるものを受け入れるかどうかによって決まります。

また、埋め込まれたハッシュ関数はさまざまな種類ごとに異なるように構築されているため、intおよびstringのハッシュ関数は、時間の複雑さと衝突の可能性について一般的な意味で最適化されています。

出典

2017-02-20 05:04:33 therainmaker

私の目標は全体のCPUを減らすことです。だから、私は（1）ハッシュ計算自体が速いと思う。（2）衝突が少ない。私が正しい軌道にいるかどうかはわかりません。 – SuperBald

@superbald：質問はなぜあなたがより良くできると思いますか？標準的なライブラリ関数は、可能な限り最良のライブラリ関数を生成することを目的とした非常に賢いプログラマによって書かれました。もしあなたがよりうまくいくのであれば、そのデータセットのパフォーマンスを向上させるためにあなたのデータについて知っているからでしょう。しかし、あなたの鍵をハッシュするのが容易になるかもしれないということについて何の手がかりも与えていません。標準的なライブラリの実装は、幅広いデータでうまく動作しなければならず、何も特別なものを作っていなければ、あなたのものとうまくいくでしょう。 – rici

STLにいるということは、それが最高であるとは限りません。たとえば、Googleオープンソースのハッシュマップやツリーマップなど、多くの場合、標準よりも優れています。私はハッシュ関数についてはわかりません。だから、この質問をしました。 – SuperBald

std :: hash関数はすでにパフォーマンスが優れています。オープンソースのハッシュ関数を試してみるべきだと思います。

これをチェックしてくださいhttps://github.com/Cyan4973/xxHash。「xxHashは非常に高速のハッシュアルゴリズムで、RAMの速度制限で動作しています。ハッシュ関数の衝突、分散、ランダム性の評価を行うSMHasherテストスイートを正常に完成しました。すべてのプラットフォーム（little/bigエンディアン）」

また、このサイトの別の質問からのこのスレッド：Fast Cross-Platform C/C++ Hashing Library。 FNV、Jenkins、MurmurHashは高速であることが知られています。

出典

2017-02-20 05:07:49

C++でunordered_map/setのハッシュ関数が高速になっていますか？

答えて

関連する問題