Stack, Verkettete Listen, Queue & Co.

[Uwe Merckens]

Hallo Gemeinde,

ich habe mich in letzter Zeit intensiv mit OOP beschäftigt und da hauptsächlich mit ADT's. Verstehen tu ich es mittlerweile und bauen kann ich das auch alles. Nur - wozu das Ganze??

Nicht nur, dass es ziemlich aufwändig zu coden ist (tipp, tipp, tipp), mir fehlt auch der Sinn wofür ich diese, sicherlich "edle", Programmierung einsetzen kann. Ich beschäftige mich in der Hauptsache mit kaufmännischen Datenbankapplikationen und dort liegen die Daten ja schon alle in wunderbarer Form - sprich Tabellen - vor. Ein paar geschickte SQL Befehle und alles ist wunderbar.

Neulich habe ich versucht nur den SQL Befehl "SELECT Sum(Feld) HAVING Feld=Criteria ORDER BY Feld" objektorientiert nachzubauen. Der Aufwand hierfür war gigantisch, verglichen zu SQL.

Wenn mir jemand "vernünftige" Einsatzgebiete aufzeigen kann, wäre mir schon sehr geholfen und ich verspreche auch fleissig weiterzulernen.

Gruss und schönes Wochenende

Uwe

[Robert Marquardt]

Die Welt besteht nicht nur aus Tabellen.<br>
Ohne einen Stack kannst du z. B. kein HTML parsen.<br><br>
Ich mache C Header Konversionen nach Pascal. Oft hoert man da "Warum gibt es da kein richtiges Tool dafuer?"<br>
Die Antwort ist das man dafuer eigentlich einen kompletten C Compiler braucht, der Pascal statt EXEs erzeugt. Kein einfacheres Tool kann das Problem auch nur einigermassen fehlerfrei loesen.<br>
Es gibt also Problemklassen und daher auch Loesungsklassen. Ein Algorithmus ist also eine Loesung fuer ein Problem bzw Problemklasse

[Uwe Merckens]

Hallo Robert,

kann ich Deiner Antwort entnehmen, dass ich erst ein Problem brauche, um daraufhin eine Lösung zu erarbeiten?

Mit meiner Frage habe ich versucht herauszufinden, ob es irgendwelche "klassischen" Einsatzgebiete für ADT's gibt. Mich würde auch interessieren, ob es Sinn macht, z.B. Daten aus einer DB Tabelle in solche Strukturen zu übernehmen (einzulesen) und dann zu verarbeiten - insbesondere ob sich u.U. dadurch Performancegewinne erzeilen lassen. Ich denke jetzt nicht an die "Türme von Hanoi" oder das "Josephusproblem" sondern eher daran, ob es den Aufwand lohnt, Objekte wie z.B. auch Binärbäume selbst zu kreieren und in kaufmännischen DB Applikationen einzusetzen.

Gruß
Uw

[Robert Marquardt]

Eigentlich nicht, solange es nur um Datenbank-Tabellen geht. Da sollte man die Verarbeitung moeglichst der Datenbank ueberlassen. Die ist schliesslich darauf optimiert.<br>
Aber schon bei der schnellen Verwaltung sortierter Daten kann ein B-Baum hilfreich sein

[Hagen Reddmann]

<i>
kann ich Deiner Antwort entnehmen, dass ich erst ein Problem brauche, um daraufhin eine Lösung zu erarbeiten? </i>

Sollte eigentlich immer so sein !<br>
Zuerst entsteht ein zu lösendes Problem und erst dann der passende Weg zur Lösung.

Ist das Problem zB. die enorm schnelle und effiziente Abarbeitung von großen Datenmengen die durch ihre Komplexität eben nicht mehr über SQL zu lösen sind, benötigt man andere Algorithmen und meisten dazu auch andere Datenstrukturen.

zB. programmiere ich schon jahrelang an einem Personalmanagament System. Dabei geht es darum viel Hausbesuche bei Patienten (ca. 500-1500 pro Tag) auf mehrere Mitarbeiter zu verteilen. Wichtig dabei ist es zu berücksichten das der Mitarbeiter dir richtige Qualifikation für den Einsatz beim Patienten hat, das das System die benötigten Fahrzeiten von Patient zu Patient optimiert, das bestimmte Einsatzzeiten eingehalten werden usw. usw. In diesem System könte man auch alles per SQL lösen, nur wäre das ungleich ineffizienter und komplizierter als eigene Datenstrukturen zu benutzen die zur Benutzung in den spezialisierten Algorithmen angepasst sind. Denn alle diese Daten müssen ja auch noch optisch anpassende im GUI angezeigt und editiert werden. Einfache SQL + Datencontrols sind für ein solches Problem nicht mehr ausreichend.<br>

ABER ! ich gebe dir im Grunde Recht, den selbst wenn ADT schon solche vorgefertigten Verfahren anbietet, so gibt es ein wichtiges Merkmal aller hochoptimierten Algorithmen + Datenstrukturen --> sie sind hoshspezialisierte Lösungsansätze für ganz spezielle Probleme. Somit widerspricht sich ADT in sich selber, denn man kann keine hochspezialisierte Probleme effiziient durch allgemeingültige Bibliotheken lösen.

Gruß Hage

[Uwe Merckens]

Hallo,

vielen Dank für Eure Meinungen!

So wie ich das sehe, kann die OOP - zumindest wenn man mit Datenbanken arbeitet - eigentlich nur unterstützend eingesetzt werden. Der Vorteil von ADT's ist allerdings, dass man sich seine Strukturen "bauen" kann wie man will und nicht an die starre Tabellenstruktur gebunden ist.

Die Performance ist allerdings in einem BTree gegenüber einem Recordset mit den selben Inhalten, dass sich ja auch zu 100% im Arbeitsspeicher befindet, bei Suchvorgängen nicht besser - eher schlechter.

Gruß
Uw

[Robert Marquardt]

Wenn es in den Speicher passt, dann ist es sowieso eine mickrige Datenmenge. Ansonsten rate mal wie so ein Index einer Tabelle gemacht wird

[Jochen Reichenberg]

Und wenn der eigene BTree langsamer ist, liegt da wohl ein 'Implementierungsfehler' vor. Oder die Reihenfolge des Einfügens der Daten in den BTree erfolgt im sortierten Zustand. Dann nützt einem der auch der beste BTree nix...

Grüße Joche

[Uwe Merckens]

Hallo,

ups, jetzt setzt's aber was...

@Robert:
soweit ich weiss, ist ein Index nix anderes wie eine zweite Tabelle, in dessen Records die den Indexwerte und die DS-Nummern der Haupttabelle stehen. Sollte ich da falsch liegen, bitte ich um Aufklärung - man lernt ja nie aus :-)

@Jochen
kannst Du mir das mal näher bringen?

Gruss
Uw

[Hagen Reddmann]

Warum sollte ein BTree langsammer werden wenn man die Elemente sortiert einfügt ? Wenn man den Tree korrekt implementiert hat dann sollte er bei sortiertem Einfügen sogar besser gewichtet sein als mit unsortierten Daten.<br>

Ich glaube Du verwechselst da was mit dem QuickSort Algorithmus. Dieser ist asymptotisch O(n*Ln(n)) schnell, aber beim Einfügen sortierter Elemente, bzw. beim Sortieren schon sortierter Elemente sinkt dies auf O(n^2). Dies ist dann nicht besser als die meisten Sortiertalgos.

Der Index wie per binärer Suche arbeiten, was langsammer als ein Binärer Baum sein wird. Es hängt von der Implementation der Datenbank ab. Die meisten DB's arbeiten per binärer Suche, da dies keine zusätzlichen Speicherstrukturen benötigt. D.h. es ist somit enorm einfach über die Index-Dateien zu suchen und live auf Multiuser-Ändrungen zu reagieren. Sollte die DB über Speicherstrukturen arbeiten, so müsste die DB jede Änderung am Index in diese Strukturen live abbilden. Ziemlich unwahrscheinlich.

Gruß Hage

[Hagen Reddmann]

<i>Die Performance ist allerdings in einem BTree gegenüber einem Recordset mit den selben Inhalten, dass sich ja auch zu 100% im Arbeitsspeicher befindet, bei Suchvorgängen nicht besser - eher schlechter</i>

Diese Aussage ist falsch. Wenn man sich die Mühe macht seine Datenbanken einzulesen um diese in Binären Bäumen oder anderen Strukturen zu verwalten dann sollte das seine Gründe haben. Am häufigsten wird es eben so sein das dadurch viel komplexe Suchanfragen/Änderungen/Querberechnungen beschleunigt werden sollen. Aus meiner Erfahrung heraus kann ich nur sagen das selbst FoxPro (der schnellste Index) um 1000'ende Male ineffizienter sein wird als seine eigene an das Problem angepasste Datebstrukturen.<br>

Schau mal hier ins Forum. Da gibt es einen Thread der sehr gut dazu passst. Aufgabe ist es aus ca. 600.000 Datensätzen bestimmte Informationen zu extrahieren. Eine Datenbank-ansatz hätte 10-12 Stunden benötigt, eine naive Delphi Impelemntain benötigte in ewta 3-4 Stunden, eine optimierte version 1 Stunde und meine Lösung mit Tries 1.5 Sekunden. Diese LÖsung ist also 2200 mal schneller als eine durchschnittliche Delphi Implementation die auf Speicherstrukturen arbeitet. Eine Datenbank kann garnicht solche Spezialfälle berücksichtigen in ihrem Design.

Gruß Hage

[Hagen Reddmann]

ADT's mit OOP zu vergleichen ist eh Schwachsinnig. Denn beide Konzepte haben nichts miteinander zu tun. Das eine ist ein Art und Weise zu Programmieren und das andere ein Hilfsmittel der Datenverwaltung. OOP also solches hat im ersten Moment nichts mit Datenverwaltung zu tun, auch wenn dies eines der finale Ziele sein soll.<br>

Ich verstehe auch nicht so richtig worauf deine Frage eigentlich hinauslaufen soll ?!<br>
Werbung für ADT's, Frust an der OOP ?

Gruß Hage

[Jochen Reichenberg]

Hallo Leute,

der Fehler den ich ein meinem ersten Tree gemacht habe, war eben der, die Daten aufsteigend sortiert einzufügen. Da keine weitere Logik im Tree hinterlegt war, hatte ich also nur Zweige in eine Richtung, da der folgende Eintrag immer größer war als der vorherige. Im Prinzip also eine verkette Liste.

Man sollte entweder direkt im Tree eine Logik hinterlegen, wo welche Daten eingefügt werden, oder die einzufügenden Daten vorher auf den Wertebereich und die Werteverteilung untersuchen und so einfügen, daß eine möglichst ausgeglichene Baumstruktur entsteht.

@Hagen: Ich denke das ist das, was Du unter sortiert einfügen verstehst - aber der 'unbedarfte Anfänger' wird eben die Daten einfach der Wertigkeit nach einfügen - was dann eben nur zu einer verketteten Liste führt.

Grüße Joche

[Hagen Reddmann]

<i> was dann eben nur zu einer verketteten Liste führt. </i>

Hm, das hängt vom Trie ab. Eigentlich kann ein Tree nie zu einer verketten List verkommen. Entweder ist es kein Tree im eigentlichen Sinne, z.B. ein Nodebaum, oder es ist tatsächlich falsch am Source.

Zb. beim AVL Tree oder Red/Black Tree hat jede Node immer nur maximal 2-3 Unternodes. Man kann also nicht auf verkettet Listen kommen. Dies wäre mit stinklnormalen Node Bäumen der Fall, aber dann reden wie hier NICHT mehr von BTree's = binären Bäumen.

Gruß Hage

[Jochen Reichenberg]

Hallo Hagen,

an dieser Stelle möchte ich erst mal Laurie Anderson zitieren: 'Ich hör' die Worte, aber versteh' nicht ihren Sinn.'

Aber es scheint tatsächlich ein Kommunikationsproblem vorzuliegen. Also ich hab' gerade noch mal nach einer Definition für BTree 'gegoogelt' (nur um sicher zu gehen, daß ich nicht komplett daneben liege). Dabei habe ich folgende Definition gefunden:

<I>Binäre Suchbäume</I>

<I>Definition 3..46 Binäre Suchbäume entstehen durch Einfügen einer Folge von Elementen. Das erste Element wird zur Wurzel des binären Suchbaumes. Die restlichen Elemente der Folge werden nun in zwei Teilfolgen - eine mit Elementen kleiner als die Wurzel und eine mit denen, die größer als die Wurzel sind - aufgespalten. Danach verfährt man mit den beiden Teilfolgen rekursiv weiter, wobei deren Wurzeln an angehängt werden. </I> <BR>
Leider sind da jetzt alle Symbole nicht mehr drin... (Quelle: http://fsmat.at/~atrax/data/diploma/node23.html)

Aber dennoch entspricht diese Definition dem, was ich unter einem BTree verstehe. Dies scheint aber das zu sein was Du einen Node Baum nennst.(?)

Wenn ich aber nach obiger Definition den Tree mit Werten von 1 bis 100 fülle, in dieser Reihenfolge, erhalte ich eine 'Liste' mit lauter freien linken Nodes. Mach' ich hier einen Denkfehler? Übersehe ich etwas?

Die anderen von Dir genannten Tree-Arten sagen mir nichts (wie ich zu meiner Schande gestehen muß). Aber da werd' ich mich morgen mal schlau machen.

Grüße Joche