In einem Optimierungsproblem halte ich viele Kandidatenlösungen in einer Warteschlange, die ich entsprechend ihrer Priorität untersuche.
Jedes Mal, wenn ich einen Kandidaten behandle, wird er aus der Warteschlange entfernt, aber es erzeugt mehrere neue Kandidaten, die die Anzahl der Kandidaten exponentiell wachsen lassen. Um dies zu berücksichtigen, lege ich jedem Kandidaten eine Relevanz zu, wenn ein Kandidat zur Warteschlange hinzugefügt wird, wenn kein Platz mehr verfügbar ist, ersetze ich (falls zutreffend) das letzte relevante Kandidat, der sich gerade in der Warteschlange befindet, mit dem neuen.
Um dies effizient zu tun, behalte ich ein großes (festgelegtes) Array mit den Kandidaten und zwei verknüpften indirekten binären Anhäufungen: eine behandelt die Kandidaten in absteigender Reihenfolge und die andere in aufsteigender Reihenfolge.
Dies ist effizient genug für meine Zwecke und der zusätzliche Platzbedarf ist ungefähr 4 ints / candidate, was auch vernünftig ist. Es ist jedoch kompliziert zu programmieren und es scheint nicht optimal zu sein.
Meine Frage ist, ob Sie eine angemessenere Datenstruktur oder eine natürliche Möglichkeit kennen, um diese Aufgabe auszuführen, ohne an Effizienz zu verlieren.
Hier ist eine effiziente Lösung, die die Komplexität von Zeit oder Platz gegenüber einem normalen Heap nicht ändert:
In einem Min-Heap ist jeder Knoten kleiner als seine beiden untergeordneten Knoten. In einem Max-Heap ist jeder Knoten größer als seine Kinder. Lassen Sie uns für jede Stufe zwischen einer min- und einer max-Eigenschaft wechseln: Jede ungerade Reihe ist kleiner als ihre Kinder und Enkel, und die Umkehrung für gerade Reihen. Dann ist das Finden des kleinsten Knotens der gleiche wie gewöhnlich, und um den größten Knoten zu finden, müssen wir die Kinder der Wurzel betrachten und die größten nehmen. Sprudelnde Knoten (zur Einfügung) werden zu einem Bit-Tricker, aber es ist immer noch die gleiche O (logN) -Komplexität.
Das Überwachen der Kapazität und das Aufrufen des kleinsten (am wenigsten relevanten) Knotens ist der einfache Teil.
EDIT: Dies scheint ein Standard-Min-Max-Heap zu sein! Eine Beschreibung finden Sie hier . Es gibt eine C-Implementierung: Kopfzeile , Quelle und Beispiel . Hier ist ein Beispieldiagramm:
"Optimal" ist schwer zu beurteilen (fast unmöglich) ohne Profiling.
Manchmal kann ein "dummer" Algorithmus der schnellste sein, weil Intel-CPUs bei dummen Array-Scans auf zusammenhängenden Speicherblöcken unglaublich schnell sind, besonders wenn die Schleife und die Daten auf den Chip passen. Im Gegensatz dazu kann das Springen um Zeiger in einem größeren Speicherblock, der nicht auf den Chip passt, um ein Zehntel oder Hunderte oder um ein Vielfaches langsamer sein.
Sie haben möglicherweise auch Probleme, wenn Sie versuchen, Ihren Code zu parallelisieren, wenn die 'clevere' Datenstruktur das Sperren einführt und so verhindert, dass mehrere Threads gleichzeitig fortfahren.
Ich würde empfehlen, sowohl Ihren aktuellen, den Min-Max-Ansatz als auch einen einfachen Array-Scan (keine verketteten Listen = weniger Speicher) zu erstellen, um zu sehen, welche die beste Performance liefert. So seltsam es auch erscheinen mag, ich habe "clevere" Algorithmen mit verketteten Listen gesehen, die in der Praxis durch einfache Array-Scans geschlagen wurden, weil der einfachere Ansatz weniger Speicher benötigt, eine engere Schleife hat und mehr von CPU-Optimierungen profitiert. Sie vermeiden möglicherweise auch Speicherzuordnungen und Speicherbereinigungsprobleme mit einem Array fester Größe, das die Kandidaten enthält.
Eine Option, die Sie vielleicht in Erwägung ziehen sollten, ist die Lösung, weniger häufig zu entfernen und jedes Mal mehr Elemente zu entfernen. Wenn Sie beispielsweise bei jeder Bereinigungsoperation 100 Elemente entfernen, müssen Sie nur das 100. Mal löschen. Dies ermöglicht möglicherweise einen asymmetrischeren Ansatz zum Hinzufügen und Entfernen von Elementen.
Aber denken Sie im Allgemeinen daran, dass der computerwissenschaftliche Ansatz zur Optimierung nicht immer der praktische Ansatz für höchste Leistung auf der heutigen und der zukünftigen Hardware ist.
Wenn Sie anstelle von Heaps Skip-Listen verwenden, haben Sie noch eine (1) Zeit, Elemente aus der Warteschlange zu nehmen Suchen in O (logn).
Auf der anderen Seite ist eine Skip-Liste schwieriger zu implementieren und benötigt mehr Platz als ein binärer Heap.
Tags und Links algorithm c++ data-structures
