2

ブーストバケットは内部的にいいねリストとして実装されていることを理解していますよね？少なくともhttp://www.boost.org/doc/libs/1_50_0/doc/html/unordered/buckets.htmlによると、そのようです。

私の質問は、これらのバケット内の要素の順序は何ですか？順序付けされていない場合、これらのバケット内のアイテムの順序付けにMRU（最近使用された）またはその他の前に移動するヒューリスティックを適用する方法はありますか？

編集：バケット内にMRUを強制することに反対する議論を理解しています。しかし、私の特定のケースでは、MRUを強制すること（または最後に最初にサービスを提供することさえ）は、負荷率が小さい場合よりもパフォーマンスが優れていることを知っています。質問は、注文は何ですか？少なくとも最後に挿入された最初に提供されたものを強制する簡単な方法はありますか？

4

2 に答える 2

1

バケットは並べ替えられていません。バケットが分類されていないのには説得力のある理由があります。あなたがこれを知っていると確信している間、私はサイトの将来の訪問者を助けるためにいくつかを列挙します。

  1. ハッシュマップタイプのデータ構造は、挿入によって再ハッシュが発生しない限り、イテレータを無効にしないでください。
  2. 高速ルックアップを維持するには、バケットを小さくする必要があります。理想的には、各バケットには1つの要素のみが含まれている必要があります。

バケットのMRU順序付けを強制することは、そもそもハッシュマップタイプの構造の全体的な考え方に反しているように思われます。アイデアは、バケットを小さくして、平均して、バケットの最初のアイテムが実際に探しているものになるようにすることです。

このため、バケット内でMRUの順序付けを強制する組み込みの方法があるとは思えません。代わりに、ハッシュアルゴリズムを調整することをお勧めします。おそらく、最大負荷率を下げます。

于 2012-10-09T20:40:12.617 に答える
0

いくつかのハッキングの後、私自身の質問に答えます。

ブーストバケットの実装は、http ：//www.boost.org/doc/libs/1_51_0/boost/unordered/detail/buckets.hppにあります。

これは実装固有であり、いつでも変更される可能性がありますが、現在、侵入的なunordered_setの場合、バケットトラバーサル[.find（）内]は最後に挿入されたアイテムから開始されます。

たとえば、1000個のバケットでunordered_setを宣言する場合：

class A : public unordered_set_base_hook<> { ... }
unordered_set<A>::bucket_type buckets[1000];
unordered_set<A> a(unordered_set<A>::bucket_traits(buckets, 1000));

そして、ランダムにサンプリングされた10000個のアイテムを挿入します[途方もなく高い負荷率10]。最後に挿入されたアイテムは、[桁違いに]アクセス[検索]時間が速くなります。

于 2012-10-10T00:12:02.143 に答える