heaps und swaps



  • Hallo,
    sagt mal, (fast?) überall wo Heaps als Datenstruktur vorgestellt werden, wird das Reparieren der Heaps ja irgendwie so bewerkstelligt, dass das freiwerdende Element mit einem anderen Element geswapt wird, und dann nach oben oder unten durchgeswapt wird, entsprechend der Vergleiche. Durch dieses geswappe wird der Algorithmus natürlich fürchterlich übersichtlich.
    Aber alle bis auf den allerletzten swap wären doch eigentlich gar nicht nötig? Vorher würde doch einfaches Kopieren ausreichen, aber dafür finde ich nirgendwo simplifizierten Code.
    Bei mir sieht das jetzt so aus, und irgendwie sieht das jetzt arg unglücklich aus, hier im Beispiel von sift-down:

    void sift_down(size_type index, T&& val)
    	{
    		const auto s = data_.size();
    		while (index <= s) {
    			auto largest = index;
    
    			if (lhs(index) < s && !compare(val, data_[lhs(index)])) {
    				if (rhs(index) < s && !compare(data_[lhs(index)], data_[rhs(index)])) {
    					largest = rhs(index);
    				} else {
    					largest = lhs(index);
    				}
    			} else {
    				if (rhs(index) < s && !compare(val, data_[rhs(index)])) {
    					largest = rhs(index);
    				}
    			}
    
    			if (largest != index) {
    				data_[index] = std::move(data_[largest]);
    				index = largest;
    			} else {
    				data_[index] = std::move(val);
    				return;
    			}
    		}
    	}
    

    Also die Idee ist, dass man das Element, das man richtig einsortieren möchte nicht runterswapt, sondern sich nebenher merkt.
    Eventuell ist da gerade noch ein Fehler drin (dort wird ein 1-basiertes Feld benutzt, deshalb <=), aber elegant sieht das ja nun wirklich nicht mehr aus... Fällt euch eine Vereinfachung ein?
    Sift-Up sieht auch nicht sonderlich schön aus...

    Und letztlich bleibt natürlich die Frage, ob solch eine "Optimierung" überhaupt etwas bringt, wenn man sie in der Wildnis nicht antrifft...



  • decimad schrieb:

    Und letztlich bleibt natürlich die Frage, ob solch eine "Optimierung" überhaupt etwas bringt, wenn man sie in der Wildnis nicht antrifft...

    Klar.

    1. Merken und Copy und am Ende mit einem Copy den Kreis schließen wenn POD.
    2. Swap sonst, weil quasi alle anderen Typen zum Beispiel (versteckte) Zeiger drin haben und die viel schneller swappen als kopieren.
    3. Außer Move wird angeboten, dann wie bei 1) nur mit Move.
      1. entfällt und wird von 3) geschluckt.
        Türlich ist sie in der Wildnis.

    Du wirst in std::-Implemetierungen seit Jahren nur noch Move finden. Swap bräuchte man ja nur noch, wenn der Typ kein Copy könnte und dafür sind die container nicht spezifiziert.



  • Na gut, die std:: Implementierung habe ich mir so nicht angeschaut, da kriege ich immer quadratische Augen wegen der Bezeichner, die sie da verwenden müssen.
    Ich meine eher so den Code den man auf Wikipedia oder den ganzen Uni-Folien findet. Aber ist wohl halt immer nur Einführung, und nicht wirklich zum produktiven Einsatz gedacht.

    Ich würde das alles auch gar nicht selber implementieren wollen, wenn ich nicht noch ein paar zusätzliche Operationen bräuchte (für die ich dann sowieso das Reparieren implementieren muss) und das ganze nicht auf "statischen" Vektoren funktionieren müsste (also die sich nur in aligned_storage abspielen)... Immer das gleiche 😉



  • Ich bin nicht sicher, ob dein Code korrekt ist.

    • Wenn die while-Schleife abbricht, hast du val noch nie ins Array reingeschrieben. Also z.B. für ein val, bei denen compare(val, 😵 immer wahr ist.
    • Ist compare bei dir ein Grösser-als-Operator? Das ist so ziemlich das Gegenteil vom Gewohnten. Andernfalls müsstest du largest in smallest umbenennen.
    • 1-based hin oder her, warum vergleichst du einmal mit <= s und einmal mit < s?
    • Ich weiss nicht, wie du sift_down verwendest, aber für ein In-place-Sort wäre es geschickter, wenn val by value übergeben wird, da dann &data_[hole]==&val gilt.

    So hätte ich das gemacht:

    void sift_down(size_type hole, T&& val)
    {
      const auto s = data_.size();
      while (lhs(hole) < s) {
        auto largest_child = lhs(hole);
        if (rhs(hole) < s && compare(data_[lhs(hole)], data_[rhs(hole)]))
          largest_child = rhs(hole);
        if (!compare(val, data_[largest_child]))
          break; // hole gefunden, in das val reinpasst
        data_[hole] = std::move(data_[largest_child]);
        hole = largest_child;
      }
      data_[hole] = std::move(val);
    }
    

    Ein Grund, wieso swap angewendet wird, ist u.A., weil dann die Analyse und der Korrektheitsbeweis einfacher wird. Der Heap hat dann immer alle gewünschten Werte und die Heapbedingung ist nur in index nicht erfüllt, wird dort aber im Schleifendurchlauf gefixt. Bei deiner Version muss man erst noch zeigen, dass val auch immer reingeschrieben wurde (was du offensichtlich falsch gemacht hast).

    Deine Begründung, wieso du nicht auf make_heap/push_heap zurückgreifen kannst, verstehe ich nicht.



  • Ja, der Code war falsch, aber dann schnell gefixt... Mir ging es hauptsächlich um die Hässlichkeit, die korrekt auch nicht geringer würde...
    Also ich hab' den Teil inzwischen verbessert, die Fallunterscheidung weitaus zu vereinfachen, aber auf Deine while-Invariante bin ich einfach nicht gekommen, sondern musste Zeiger verwenden... 😞 Schon schön blöd... Danke Dir!



  • Wie meinst Du das mit der Zeiger-Vergleich im letzten Punkt des ersten Abschnitts?
    Mein Anliegen war erstmal nicht, ein fertiges Array zu sortieren, sondern das eben dynamisch zu befüllen. Die R-Value-Ref zeigt entweder auf etwas das von außen reinkommt, oder auf eine Kopie, die angefertigt wird, wenn durch Veränderung eines Elements die Heap-Invariante lokal kaputt gemacht wird.

    Also das ist auch der Grund warum ich das jetzt alles selber mache: Ich möchte Elemente einzeln updaten können und dann einzeln fixen. Oder Elemente in der Mitte entfernen. Mir fiel da nicht ein, wie man die std::-Funktionen in diesem Fall gewinnbringend benutzen kann...



  • decimad schrieb:

    Ich meine eher so den Code den man auf Wikipedia oder den ganzen Uni-Folien findet.

    Wikipedia-Quellcodelieferer haben da die Tendenz, nach Pascal zu stinken und bei Java aus ideologischen Gründen stehengeblieben zu sein. Die sind überhaupt kein Maß.

    Uni-Folien haben schon Swap??? Cool! Dachte, die Gemeinde hat bei Heaps Swap erst in den frühen 90-er-Jahren eingeführt. Damit würdest Du Uni-Folien haben mit einem Stand der nicht viel älter als 20 Jahre ist. Gute Uni.

    decimad schrieb:

    Aber ist wohl halt immer nur Einführung, und nicht wirklich zum produktiven Einsatz gedacht.

    Jo, um genau zu sein ist es ein unwichtiges Implementierungsdetail.

    decimad schrieb:

    Ich würde das alles auch gar nicht selber implementieren wollen, wenn ich nicht noch ein paar zusätzliche Operationen bräuchte (für die ich dann sowieso das Reparieren implementieren muss) und das ganze nicht auf "statischen" Vektoren funktionieren müsste (also die sich nur in aligned_storage abspielen)... Immer das gleiche 😉

    Hmm.
    Hab da mal einen alten von mir gefunden, entsanden zwischen 1995 und 2000.
    https://www.c-plusplus.net/forum/163518-full
    Irgendwie fand ich es nie eine Qual, sowas selber zu implementieren.

    Uih, ist der alte Code häßlich.



  • Hrmmm, wenn ich das jetzt so sehe, wie Du dort sozusagen die ersten beiden Elemente als Queue verwendest, wobei das zweite Element eigentlich erst die Wurzel des Heaps ist, frage ich mich jetzt, warum dann überall impliziert wird, man müsste für 0-basierte Heaps (pos*2+1) und (pos-1)/2 verwenden...
    Aber Du hast somit eigentlich immer einen Vergleich mehr als ein echter Heap, oder nicht, außer in dem einen Fall, in dem die letzte Reihe des "echten" Heaps nur ein Element hat, natürlich. Hrmm. Und dann in seltenen Fällen beim Pushen natürlich zusätzlich noch einen Vergleich mehr, weil Du geschickt die Abbruchbedingung durch x<x umsetzt... Hrmmm.

    Ich benutze ja wie gesagt Storage um Move-Only-Objekte da drin speichern zu können, und habe jetzt das 0te Element für den size-Member benutzt (zumindest wenn es sich mit den Größen ausgeht).

    Jetzt noch eine zusätzliche Option... hrmm. Kommt ja drauf, ob die Vergleiche teuer sind oder nicht... wenn ich das jetzt richtig seh'.

    Naja, ich wollte eigentlich ein einfaches Problem damit lösen, und schon kommen wieder Abwägungen über Abwägungen 😉 Das meine ich halt! Ich mein ja nicht, dass es nicht Spaß machen würde sowas umzusetzen, aber nicht, wenn man dabei die Zeit verrinnen sieht 😉



  • Ja, jetzt wo Du es sagst…
    Das Rumschieben in der kleinen queue ist jedesmal ein move, der nicht die Schlüsselmenge halbiert. Hatte sich angeboten, weil der Code so hübsch wurde. Müsste echt man die Alternative ausprobieren.



  • Moah, so ein bisschen bin ich schon enttäuscht. Ich habe noch einen interval_heap implementiert, weil es so schön war... Und da ist der Break-Even-Punkt gegenüber einem sortierten Vektor, der insertion-sort benutzt, im pathologisch simpelsten Fall von "int, std::less" erst bei einer Größe von 4096 Elementen erreicht... Ich hatte da echt etwas kleinere Werte erwartet...
    Ich gehe mal davon aus, dass Prozessoren mit weniger Branch-Prediction und Pipelines da früher ankommen, oder größere Typen und/oder kompliziertere Vergleiche, aber trotzdem erst ab einer unrealistischen Größe...

    Gibt's eigentlich Bestrebungen, der STL mal realistische Container hinzuzufügen? Map, Set & Co. sind ja asymptotisch vielleicht toll, aber gehen ja scheinbar auch so ein bisschen an der Realität vorbei. Da wär's doch toll, wenn man für seine kleinen Problem die entsprechenden linear sortierten Pendants zur Hand hätte.


Log in to reply