Grösse dynamischer Arrays

[Rüdiger Heim]

Hallo Delphi User,
ich möchte eine Liste von Einträgen (nummerierte Knoten mit deren Koordinaten) in einem Array ablegen, um sehr schnell darauf zugreifen zu können. Dabei sollen die Knoten-Nummern gleich mit der Array Indizierung sein. Deshalb lege ich ein dynamisches Array im Umfang der maximalen Knoten-Nummer an. Dies bedeutet dann ggf. aber sehr viel Speicherbedarf, weil die Knoten-Nummern nicht lückenlos aufeinanderfolgen und u.U. sehr grosse Nummern auftreten.
Die Delphi Anweisungen verraten sehr schnell, dass ich kein versierter Programmierer bin!
var NodeArray : Array of Array of Integer;
SetLength(NodeArray,NodeMax,3);
Schon jetzt herzlichen Dank für die freundliche Hilfe.

Rüdiger Heim

[Hagen Reddmann]

Hi

Es geht um binäre Bäume ?
Der Ansatz mit einem Array, bei vielen Knoten, ist schlecht.
Im Normalfall nutzt Du, sagen wir mal 1000 Knoten, aber 100000 Knoten wären möglich. Das Knoten "Index" array Deiner Art wäre so groß das alleine der Zugriff auf dieses Array langsammer ist als eine gut programmierte binäre Suche durch den Baum. Grund ist der CPU-Cache. Bei der binären Suche, suchst Du immer die Unterknotenliste eines Knotens durch. Diese Liste wird kleiner als der Cache sein und somit auch im Cache gehalten. Desweiteren werden bei der binären Suche von 65536 Einträgen NUR max. 17 Vergleiche durchgeführt, d.h. um in einer sortierten Liste von 65535 Integerwerte nachzuschlagen ob ein bestimmter Integerwert existiert, brauchst Du nur max. 17 Elemente der Liste zu überprüfen !! Solche sortierten AVL-Bäume sind gerade deshalb so flexibel UND schnell. SCHNELLER als ein Scan durch ein unsortiertes/sortiertes Array. Natürlich ist der Aufwand/Verwaltung solcher Bäume größer, und ein großteil der anschließenden Sucharbeit wird schon beim Erstellen solcher Bäume erledigt. Auch der Speicherverbrauch im gesamten ist gößer, da solche Bäume Verwaltungsfelder wie Parent, Childlist, Nextnode, Prevnode etc benötigen. Die Leistungsfähigkeit solcher Bäume ist aber unbestritten, beste Beispiele sind die Zipper/Packer.

Gruß Hage