Boost :: Heap :: Arity, was ist das?

Question

Ich säubere einen Legacy-Code. Drinnen habe ich eine Prioritätswarteschlange von 1986^_ ^. Nach der Schnittstelle mit einer C++ - Schnittstelle mehr und weniger kompatibel mit der Std. Ich habe einen Benchmark zwischen allen priority_queues auf dem "Markt" (Std + Boost) gemacht.

Boost bietet einen priority_queue-Namen boost::d_ary::heap. Diese Warteschlange erfordert einen Parameter mit dem Namen boost::heap::arity<int>, die Dokumentation von Boost bietet keine klare Erklärung, nur einen Link zur Implementierung des Heap.

Jetzt setze ich boost::heap::arity<128> Ich bin wirklich zufrieden, aber ich weiß nicht, was es bedeutet. Einer von euch, habt ein bisschen Erklärung?

Answer 1

Oft sind Prioritätswarteschlangen als heaps implementiert. Haufen sind volle Bäume mit einer Teilreihenfolge von oben. Solche vollen Bäume werden im Allgemeinen in einem Array gespeichert. Die Arität beschreibt, wie viele Kinder jeder Knoten des Baumes höchstens hat. Für eine Zweiheit ist der Baum ein Binärbaum und so weiter. Aus einem abstrakten Standpunkt hat der Baum, der einem Haufen entspricht, eine Tiefe von ungefähr log(n)/log(d) (wobei d die Arität des Heaps ist).

Die Leistung eines Heap hängt (theoretisch) von der Arity ab, in der Praxis kommt es vor allem auf die Cache-Effizienz an. Sie sollten einige Benchmarks ausführen, um die Leistung zu testen. Ich denke, dass ein Wert von 128 ziemlich hoch ist, ich benutze persönlich den Bereich von 2 bis 16.