verkettete Listen

[p80286]

Zitat von Codehunter:

Zitat von p80286:

Auch wenn das etwas fortgeschritten ist, kannst Du mal ein Beispiel posten?

Was genau willst denn wissen?

Erst einmal vollkommen ohne Virtualxxxx. Dein (?) Ansatz ist ja eine Pointer-Verküpfung (und eine zweite und eine dritte...) in der in jedem Eintrag (Node?) ein pointer auf Daten enthalten ist. Aber wie sind die Daten organisiert? Einfach verpointerte Liste oder Array oder ? Oder liegen die wild im Speicher herum und wenn die Organisationslisten weg sind hast du Datenzombies?

Gruß
K-H

[Namenloser]

Zitat von Stevie:

Newsflash: Performance of Array vs. Linked-List on Modern Computers

Die gehen aber offensichtlich davon aus, dass man das Element erst noch suchen muss. Das ist ein bisschen unfair der verketteten Liste gegenüber. Denn an sich geht das Einfügen oder Löschen eines Elements in einer verketteten Liste – wenn man den Pointer schon hat – in konstanter Zeit, weil man ja nur zwei Pointer umbiegen muss. Beim Array dagegen muss man immer alle Elemente nach dem gelöschten bzw. eingefügten Element umkopieren, was mit der Anzahl der Elemente linear ansteigt. Gerade da spielt die verkettete Liste ja ihre Stärke aus. Das ist normalerweise genau der Grund, warum man sich für eine verkettete Liste entscheidet.

Bei sehr kleinen Listen (so in der Größenordnung <100 Elemente) ist allerdings das Array oft trotzdem schneller. Es kommt natürlich auch immer darauf an, ob man mehr liest oder mehr schreibt. Wenn man fast nur liest, dann kann das Array auch bei größeren Listen Sinn machen.

[Codehunter]

Zitat von p80286:

Zitat von Codehunter:

Zitat von p80286:

Auch wenn das etwas fortgeschritten ist, kannst Du mal ein Beispiel posten?

Was genau willst denn wissen?

Erst einmal vollkommen ohne Virtualxxxx. Dein (?) Ansatz ist ja eine Pointer-Verküpfung (und eine zweite und eine dritte...) in der in jedem Eintrag (Node?) ein pointer auf Daten enthalten ist. Aber wie sind die Daten organisiert? Einfach verpointerte Liste oder Array oder ? Oder liegen die wild im Speicher herum und wenn die Organisationslisten weg sind hast du Datenzombies?

Im Wesentlichen packe ich die Nutzdaten als Payload gleich mit in den Record. Der Record wird mit New() und Dispose() bzw. Initialize() und Finalize() erstellt und zerstört. Seit man Records auch noch Prozeduren anfügen kann, implementiere ich die ganze Verknüpfungslogik direkt im Record. Wenn man es richtig anstellt, stupst man nur das Rootelement an und das Ganze schreibt sich z.B. selbst in einen Stream zwecks Sicherung auf Festspeicher.

Willst du mittendrin ein Element löschen, dann lässt du dieses Element alle Verweise auf sich selbst in anderen Elementen auf das jeweils nächste Nachbarelement ändern. Das geht, wenn jedes Element seine Nachbarn "persönlich" kennt.

Du könntest wenn du viel Wert auf Integrität legst, einen Zeiger auf jeden Record in eine TList schreiben, um sie dann in einem Destructor abzuarbeiten und freizugeben. Aktiv arbeiten würde ich aber mit der TList nicht.

[p80286]

Ah so, vielen Dank!
das halte ich mal im Hinterkopf

Gruß
K-H

[Zacherl]

Zitat von Namenloser:

Zitat von Stevie:

Newsflash: Performance of Array vs. Linked-List on Modern Computers

Die gehen aber offensichtlich davon aus, dass man das Element erst noch suchen muss. Das ist ein bisschen unfair der verketteten Liste gegenüber. Denn an sich geht das Einfügen oder Löschen eines Elements in einer verketteten Liste – wenn man den Pointer schon hat – in konstanter Zeit, weil man ja nur zwei Pointer umbiegen muss. Beim Array dagegen muss man immer alle Elemente nach dem gelöschten bzw. eingefügten Element umkopieren, was mit der Anzahl der Elemente linear ansteigt. Gerade da spielt die verkettete Liste ja ihre Stärke aus. Das ist normalerweise genau der Grund, warum man sich für eine verkettete Liste entscheidet.

Das häufige Anfordern und Freigeben von vielen kleinen Speicherblöcken kann durchaus langsamer sein, als die einmalige Anforderung eines einzelnen (oder wenigen) großen Blocks. std::vector over-allocated z.B. anhand bestimmter Growth-Faktoren. Bei einer linked-list wäre das nur möglich, wenn man alle Nodes im selben Speicher hält, wofür man dann aber wiederrum z.B. ein extra Bitmap benötigt, um die freien Bereiche zu Tracken (habe ich deshalb noch in kaum bzw. sogar in keiner Implementation gesehen). Kann also schon sein, dass das Verschieben des Speichers performanter ist. Denke das muss man alles individuell auf den Anwendungsfall bezogen testen.