15

Guava'sImmutableSetは、に関する私のベンチマークではかなりパフォーマンスが悪いようcontainsです。一部のサイズでは、以下よりもはるかに遅くなりますList。

  size            benchmark         ns linear runtime
100000         ListContains  110279.54 ==
100000          SetContains       7.15 =
100000 ImmutableSetContains   76716.47 =
200000         ListContains  275367.66 =====
200000          SetContains       7.34 =
200000 ImmutableSetContains  322185.50 ======
500000         ListContains  935210.10 ====================
500000          SetContains       7.79 =
500000 ImmutableSetContains 1382765.76 ==============================

基本的に、私は数千の負の整数でセットを埋め、テストには非負の整数が含まれます。コードは簡単ですが、小さなテキスト領域に貼り付けるには少し長すぎるので、こちらをご覧ください。

ここで何が起こっているのだろうか。おそらく、私は明らかにそうしようとはしなかったが、いくつかの退化したケースにぶつかった。あるいは、ベンチマークを吹き飛ばしたばかりかもしれません。そうでなければ、私はそれが修正できるかどうか、そして修正されるべきかどうか疑問に思います。

解決策は、スミアリング機能を置き換えることで変更することでした

hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);

に

return C2 * Integer.rotateLeft(hashCode * C1, 15);

これにはほぼ同じ時間がかかり、いくつかの欠点があるかもしれませんが、ハッシュをうまく広げることで現在の問題を解決します。

4

1 に答える 1

9

説明は実はとても簡単です。整数が2の累乗であるM = {0, 1, ..., N-1}いくつかのセットにあると想像してください。そして、どのように定義されNているのかという理由で、ハッシュもそうです。Integer.hashCodeハッシュは、いくつかの一般的なケースで最下位ビットでの衝突を最小限に抑えるために、これsmearと同じ関数を介して処理されます。

サイズのテーブル2*Nが割り当てられ、のメンバーがそのテーブルにM入れられます。smear右シフトのみが含まれるため、それ自体にマップさMれます。つまり、テーブルの連続範囲がいっぱいになります。したがって、テーブルの左半分のすべてのスロットが使用され、残りの半分は未使用であるとしましょう。

がcontains(o)呼び出されると、検索はスロットで開始されます。スロットの位置は。によって決定されo.hashCode()ます。o見つかった場合、結果はです。true空のスロットがヒットした場合、結果はfalseです。それ以外の場合、検索は別のスロットに進みます。キャッシュミスを最小限に抑えるために、線形プロービングが使用されます。

最初に使用したスロットから検索を開始するのに不運な場合は、すべてをトラバースする必要があります。これはNステップを意味します。ランダムな位置から開始することはN/4、平均してステップを意味します。

私のベンチマークで起こったことは上記とまったく同じではありませんが、パフォーマンスが悪い理由は同じです。サイズを2の累乗にすると、問題が悪化します。

于 2012-09-25T18:14:18.780 に答える