Welchen bucket_count Wert sollte ich verwenden, wenn ich die beabsichtigte Anzahl von Map Keys kenne?

Question

Ich erstelle eine std::unordered_map, die ich sofort mit n Schlüssel-Wert-Paaren füllen werde - und ich kenne n. Danach werden keine weiteren Elemente hinzugefügt - ich werde nur Nachschlagevorgänge durchführen.

Was sollte ich daher als bucket_count an den Konstruktor übergeben?

Hinweise:

• Ich weiß, dass es nicht sehr kritisch ist und ich kann einfach nichts angeben und es wird funktionieren.
• Dies bezieht sich auf, aber kein Narr, What should I pass to unordered_map's bucket count argument if I just want to specify a hash function?)
• Wenn Ihre Antwort hilft, kann annehmen, dass Sie ich im Voraus einen Lastfaktor zwischen f_1 und f_2 (bekannt haben wollen).
• Ich verwende die Standard-Hash-Funktion, und ich weiß nicht, was die Eingabe ist wie, aber es ist unwahrscheinlich, dass das Hashing kontradiktorischer sein ..

Answer 1

Nach n4296 in 23.5.4.2 [unord .map.cnstr] (dies ist der endgültige Entwurf von C++ 14) Standardmäßig ist die max_load_factor für eine unordered_map 1.0, also könnten Sie einfach den bucket_count auf n setzen.

Es gibt offensichtlich einen Raum-Zeit-Kompromiss zwischen Erhöhen der Bucket-Anzahl für verbesserte Geschwindigkeit und Verringern (und Erhöhen des maximalen Lastfaktors) für verbesserten Platz.

Ich würde mich entweder nicht darum kümmern, oder wenn es eine große Karte ist, setzen Sie die Bucket-Anzahl auf n. Dann können Sie sich Gedanken über die Optimierung machen, wenn das Profiling zeigt, dass Sie ein Problem haben.

Wenn Sie den Bereich der gewünschten Lastfaktoren kennen, legen Sie die Bucket-Anzahl auf std::ceil(n/(std::max(f_1,f_2)) fest (und legen Sie den Lastfaktor fest, bevor Sie die Karte ausfüllen).

Answer 2

Angesichts der Tatsache, dass Sie einen Bereich für Ihren Lastfaktor haben, ist die einzige fehlende Information die Kollisionsrate. Sie können einfach nb_buckets = n/f_2 verwenden und Sie werden sicher sein, einen Ladefaktor von weniger als oder gleich f_2 zu erhalten. Um Korrektheit über f_1 sicherzustellen, sind Daten über die Kollisionsrate erforderlich.