Splaytree-Animation

[Delphi-Laie]

Hallo Leute!

Bei der Suche nach neuen Sortieralgorithmen für mein Sortieranimationsprogramm stieß ich auf Splaysort, dessen orginalen C(++?)-Quelltext nach Delphi zu übersetzen ich letztlich scheiterte (an einer Stelle nicht beseitigbares unterschiedliches Verhalten, auch beim Debuggen).

Später jedoch stieß ich dann aber doch noch auf Delphi-Quelltext, und zwar für die Animation von Splaytrees (Einfügen, Löschen, Suchen....):

http://splaytree.sourceforge.net
http://sourceforge.net/p/splaytree/code/HEAD/tree

Um mich nicht mit fremden Federn zu schmücken: Der weitaus allergrößte Teil des hier vorgestellten Programmes entspricht dem (wahrscheinlich von slowakischen Programmautoren stammenden) Original. Von mir kommen im wesentlichen nur alle deutschsprachigen Bedienelemente, die dazu dienen sollen, das Animationspotential des Originalprogrammes stärker auszureizen und die Leistungsfähigkeit, aber auch Grenzen (Entartung bei bestimmten Dateneingabereihenfolgen) der Splaytrees besser aufzuzeigen.

Anhand der Funktionen "kleinstes Element löschen" und "größtes Element löschen" in Kombination mit "Anzahl zu löschender Elemente -> alle" sollte zudem klarsein, wie diese baumförmige Datenstruktur auch als Grundlage des Sortierens benutzt werden kann.


Viel Spaß und viele Grüße

Delphi-Laie

Edit 1: Kleine Verbesserung mit weniger Steuerelementen, Wurzel jetzt direkt löschbar.

[Furtbichler]

Nett, aber vom Suchverhalten eher ein binärer Baum, oder?

[Delphi-Laie]

Zitat von Furtbichler:

Nett,

Meine ich auch, deshalb hier - nach meinen dezenten Erweiterungen - und im Delphiforum (Entwicklerecke) veröffentlicht.

Zitat von Furtbichler:

aber vom Suchverhalten eher ein binärer Baum, oder?

Frag mich was leichteres, ich bin kein Informatiker. Jetzt mit flüchtig angelesenem (Internet-, vor allem Wikipedia-)Wissen aufzuschneiden, ist nun wirklich nicht mein Ding (dort wird das jedenfalls als binär bezeichnet). Interessant finde ich allerdings, daß diese Bäume entarten können, das ist hier wunderbar zu sehen - dafür eben keine automatische Balancierung.

Für mich ist das nur ein (steiniger) Weg zu einem weiteren Sortieralgorithmus (der allerdings nicht so schön animiert sein wird). Ich bin als Hobbyprogrammierer schon "stolz wie Oskar", weil ich die Graphikausgabefunktionen "abschälen" und den Quelltext nunmehr sogar Delphi-2.0-kompatibel machen konnte (statt overload einfach nur verschiedene Routinebezeichnungen verwenden).

Insofern wäre es sogar ganz lässig, dieses Programm um andere Baumstruktur(algorithm)en zu erweitern. Doch momentan bin ich mit meinem Sortierkino noch gut beschäftigt, und danach wartet eigentlich etwas anderes.

[himitsu]

Bin nicht so firm, beim Sortieren und wenn ich ehrlich bin, dann bau ich meistens einfach nur 'nen Bubbletea-Sort ein. (ist einfach, man kann nichts falsch machen und war mit bisher meistens schnell genug)

Ein paar Anchors könnten nicht schaden.

Und daß die GUI bei den Animationen einfriert ist nicht sonderlich gut.
- 10 Zufallswerte und Windows meint schon, daß die Anwendung nicht reagiere ... ich hatte beim ersten Mal allerdings 50 einfügen wollen und hab dann den Taskmanager benutzt, als mich die Lust verließ.

[Delphi-Laie]

Zitat von himitsu:

Und daß die GUI bei den Animationen einfriert ist nicht sonderlich gut.
- 10 Zufallswerte und Windows meint schon, daß die Anwendung nicht reagiere ... ich hatte beim ersten Mal allerdings 50 einfügen wollen und hab dann den Taskmanager benutzt, als mich die Lust verließ.

Ja, das dürfte jenseits des Windows XP (aufsteigend) der Fall sein. Das Programm ist wohl graphikseits nicht optimiert worden (synchronize & Co.), das werde aber ich nicht tun bzw. schaffen. So ist die Ausgabe der laufenden Zählvariable nunmehr in ein "disgeabeltes" Editfeld verpackt, nicht sehr elegant. Grund: Vorher war es ein Label mit Refresh. Das führte zum "Weißzeichnen" des Formulares, vermutlich, weil Label direkt auf das Formular schreibt.

[Namenloser]

Irgendwie finde ich, es sieht leicht unheimlich aus, wie der Baum sich bewegt .

Aber sonst ganz cool, auch wenn ich nicht weiß, was genau die Vorteile eines Splay-Baums sind.

Ich hatte so ein ähnliches Programm vor ein paar Monaten für (a,b)-Bäume gemacht (welche, wenn ich das richtig verstanden habe, eine Verallgemeinerung von B+-Bäumen sind). War allerdings nur für mich zum Debuggen und nicht so schön animiert

Edit @himitsu: Falschen Blog verlinkt? Sehe weder zu Bubblesort noch noch zu Bubbletea einen Zusammenhang.

[himitsu]

PS: Bis Delphi 2 ist mir dann doch zuviel, da ich auf einige Fearures nicht verzichten mag.
Bis Delphi 4 hatte ich mal gemacht, auch wenn ich mir vor knapp 3 Jahren das fehlende D3 gekauft hatte, was mir noch fehlte, aber auch D4 war schon hart genug.

Bis Delphi 7 schon länger das Maximum (und nur wenn es unbdingt sein muß, dann auf Anfrage mehr), aber meistens ist wird als Minimum D2006/TDE supportet.
> vorallem Conditional-Expressions und paar Record-Spielereien

[Furtbichler]

Zitat von Delphi-Laie:

Frag mich was leichteres

Wie gehts?

Zitat:

ich bin kein Informatiker.

Nur das Ergebnis zählt (ja, der Weg auch).

Das ist ein Binärbaum, der 'einfach' das zuletzt gesuchte Element als neue Wurzel bzw. Top-Element speichert und dadurch den Baum umformt. Das führt dazu, das oft benötigte Elemente tendentiell weiter oben liegen, was zu einer 'Suchoptimierung' führt.

Als Sortieralgorithmus dürfte sich das imho nicht lohnen, denn beim Sortieren wird zwar oft verglichen, aber selten direkt gesucht. Aber ich lasse mich gerne eines Besseren belehren.

[Delphi-Laie]

Zitat von Furtbichler:

Zitat von Delphi-Laie:

Frag mich was leichteres

Wie gehts?

Blendend, nachdem ich bei der "Extraktion" des eigentlichen Algorithmus und Quellcodevereinfachung weit vorangeschritten bin.

Zitat von Furtbichler:

Als Sortieralgorithmus dürfte sich das imho nicht lohnen, denn beim Sortieren wird zwar oft verglichen, aber selten direkt gesucht. Aber ich lasse mich gerne eines Besseren belehren.

Lohnen? Für mein Sortieranimationsprogramm lohnt sich jeder Algorithmus. Und wenn die Arbeitsweise dabei nicht offensichtlich wird, dann erlaubt das zumindest doch eine erste Abschätzung der Geschwindigkeit (wenn auch keine sichere "gefühlte" Zuordnung zur Komplexitätsklasse, s. z.B. Select(ion)sort (das läuft bei mir schnell, ist aber dennoch O(n^2)).

Splaysort benötigt, wie die anderen, auf dynamischen Speicherstrukturen beruhenden Algorithmen (in die eingeordnet und aus denen gelesen wird), reichlich zusätzlichen Speicher, ist also ex situ, allerdings von der Geschwindigkeit her O(n*log(n)). Erste "ungraphische" Ergebnisse scheinen das zu bestätigen.