verkettete Liste

[alzaimar]

Zitat von helga5:

Soll etwas schneller als shellsort sein, da rekursiv.
Soll das heissen, dass rekursiv schneller als iterativ ist?

Nein. Es kommt hier auf das Verfahren an. Quicksort ist zwar von der Komplexität her genauso wie Shellsort (und auch Mergesort), in der Praxis hat sich aber quicksort bewährt, weil es einfach am kompaktesten ist, also pro Vergleich, Vertauschen etc. am wenigsten Overhead produziert.

Eine iterative Variante von Quicksort, die den rekursiven Aufruf mit einem eigenen Stack simuliert, ist noch marginal schneller (ca. 4%).

Wirklich schnell ist nur die Skip list, die sowohl der LL, als auch dem DA (wie komm ich nur auf VA?) in allen Belangen haushoch überlegen ist.

[Lemmy1]

Hrm also das anhängen eines Elementes an ein dynamisches Array ist nicht zwingend O(1), da Windows u.U. einen neuen Speicherbereich finden muss, da Arrays nicht fragmentieren können.

Ergo ist das anhängen eines Element O(n) (n=Anzahl Element im Array).

[alzaimar]

Ich schrieb[*], das man die Größe des dynamischen Arrays verdoppelt, wenn das neue Elemnt nicht mehr hineinpasst. Windows vergrößert von sich aus gar nichts, oder?
Aber wenn ich das mache, und zwar immer verdoppeln, kann man das vernachlässigen, auch rechnerisch, ergo O(1).

[edit] (*) Nee, hab ich gar nicht geschrieben, sondern nur gedacht, das ich das geschrieben habe . Aber wer nach vor jedem Append das Array erstmal vergrößert, ist selbst schuld. [/edit].

[Lemmy1]

Yup beim Verdoppeln hast recht. Aber das geht ja nur, wenn ich zum Beispiel Zeilen aus einer Datei auslesen ohne die Gesamtgröße zu kennen.

Wenn ich aber sowieso nur ein einziges Element anhängen will, dann bringt mir Verdoppeln halt oft nix

[alzaimar]

Zitat von Lemmy1:

Wenn ich aber sowieso nur ein einziges Element anhängen will, dann bringt mir Verdoppeln halt oft nix

Dann ist aber auch eine Komplexitätsbetrachtung für'n A****, oder? Egal., Ich hätte es dazu schreiben sollen und Dein Einwand ist berechtigt.

[himitsu]

Also wenn ich mir meinen MM so anseh, dann kommt's da auf die Größe das Array's an.

bei 'nem großen Array und vielen einzufügenden/anzuhängenden Einträgen ist auf jedenfall die verkettete Liste schneller, da die kleinen Speicherblöcke schneller/optimaler verwaltet werden.
Es sei den du verwendest 'ne optimierte SetLength-Funktion (hab z.B. sowas für Strings, da kann man das Verhalten bei Längenändernung beeinflussen), da könnte es sich dann eventuell wieder etwas ausgleichen.


Ach ja, was das Verdoppeln angeht ... sowas würde ich wohl eher nicht anraten ...stellt euch doch nur mal vor das array ist schon echt groß und ratet mal, wie extrem groß es dan werden würde

http://www.delphipraxis.net/internal...=451739#451739 in dem Beitrag sieht man mal mein SetLength (Parameter und so) und da kann man dann halt angeben wie und in welchen Schritten der String (ist ja auch nur ein dynamisches CharArray) vergrößert/verkleinert wird.

[alzaimar]

Wie immer, muß man zwischen Theorie (Komplexitätsbetrachtung) und Realität unterscheiden.

Wie ich schon sagte, bei einem dynamischen Array muß man die Größe jeweils verdoppeln (oder jedenfalls um einen Faktor vergrößern), und nicht um einen konstanten Wert. Ein konstanter Wert wird die Komplexität von O(1) auf O(n) verschlechtern, eine Vergrößerung um einen Faktor ('2') eben nur marginal. Warum? Weil dieser Umstand bis im Zahlenraum von Integern nur maximal 31 mal vorkommen kann. Bei 2 Milliarden Werten ist der Aufwand dann zu verschmerzen und geht auch rein rechnerisch gegen 0.

Bei einer echten Anwendung, wie himitus MM (Memory-Manager?) wird gesucht, gelöscht, einfügt etc. Wer da die Nase vorn hat, hängt wirklich davon ab, was am häufigsten ausgeführt wird. Ich kann mir nicht vorstellen, das ein dynamisches Array, das anfangs auf ein paar 100k dimensioniert ist, performancetechnisch von einer LL abgehängt wird. Aber erst der Versuch macht schlau, und bis dahin vertraue ich himitsus Erfahrung.

Ich kann mir aber nun wirklich nicht vorstellen, das eine verkettete Liste in einer App gegenüber einer Skiplist oder Hashmap wirklich die Nase vorn hat. Na ja, vielleicht bei < 20 Elementen...

[Khabarakh]

Borland verwendet für seine TList-Implementation (bei mehr als 64 Einträgen) eine Vergrößerung von 25%, damit sollte der ungenutzte Speicher wirklich nicht sehr ins Gewicht fallen.
Aber eigentlich dachte ich, dass sich in der Praxis etwa der Faktor 1,7 bewährt hätte .

[add]
Microsoft hält sich im .Net-Framework eher daran: 200% der alten Capacity.
Wer beide Werte nicht mag, kann sich ja immer noch eine eigene Klasse anlegen .
[/add]

[himitsu]

eine prozentuale Änderung macht sich eh mehr schlecht, als recht.
wenn die Liste klein ist, dann ist die änderung winzig und bei 'ner großen Liste ist die änderung rießig ... besser ist halt ein Wert, der sich nach der Elementgröße und der vermutlichen Menge neuer Elemente, oder halt wie oft/schnell was Neues eingefügt wird richtet.

[alzaimar]

Zitat von himitsu:

eine prozentuale Änderung macht sich eh mehr schlecht, als recht.
wenn die Liste klein ist, dann ist die änderung winzig und bei 'ner großen Liste ist die änderung rießig ... besser ist halt ein Wert, der sich nach der Elementgröße und der vermutlichen Menge neuer Elemente richtet.

Nein, stimmt nicht. Also, der erste Satz stimmt nicht. Der Zweite schon, aber woher willst Du denn wissen, wieviel vermutlich dazukommt? Wenn Du das wüsstest, könntest Du die Liste gleich groß genug machen.

Eine Liste, die ihre Größe jeweils verdoppelt, tut dies (bei einer angenommenen Anfangsgroße von 1000 Elementen) nur 21x in ihrem Leben. Und das auch nur, wenn man sie mit 2Mrd. Elementen zuballert, aber wer macht das schon? Im richtigen Leben dürfte sie sich maximal 10x vergrößen. Dann fasst sie immer noch 2^20 Elemente, und das sollte doch reichen. Die Wartzezeit, um eine Liste von 5 auf 10MB zu vergrößern, liegt bei wieviel? 10ms? Und selbst wenn das viel viel langsamer wäre, würde das nur 1x vorkommen. Da ist mir das doch schnurz.

Eine prozenturale Änderung spiegelt genau das wieder, was gerade mit der Liste passiert. Wenn ich als Programmierer das DA anfangs auf 10 Elemente beschränke, erwarte ich i.A. keine 500.000.000 Elemente in der Liste, sondern eher weniger. Wenn ich nun ein 11.Element einfüge reagiert die Liste ziemlich schlau: Sie macht Platz für weitere 10 Elemente. Das ist nett. Und wenn ich dann 100.000 Elemente drin habe, und will das 100.001te einfügen, 'geht die Liste davon aus', das ich gleich noch ein paar hinterher schmeisse. Ergo vergrößert sie sich gleich auf 200.000.

Eine Vergrößerung um immer -sagen wir- konstant 10 oder 1000 Elementen ist dagegen ein echter Hemmschuh. Natürlich wird der Speicher so nicht unnötig verbraten, aber das ist mir völlig schnurz. Wichtiger ist hier doch die Performance, oder?

Ich hatte mich mal ne Weile mit dieser 'Technik' beschäftigt... Man merkt performancetechnisch einfach nicht, das sich da eine dynamische Liste von der Größe her verdoppelt: Ob ich die Liste gleich 10000000 Elemente groß mache, oder dynamisch vergrößere (x2), ist wirklich kaum ein Unterschied. Wenn ich die Liste dagegen jeweils um 1000 Elemente vergrößere schon. Das ist doch logisch.

Beispiel: Eine Liste umfasst anfänglich 1000 Elemente. Nun fülle ich die Liste mit 100000 Elementen. Immer, wenn ein Element nicht mehr reinpasst, vergrößere ich sie, und zwar:
a) um jeweils 1000 Elemente oder
b) ich verdopple die Listengröße.

Bei a) habe ich insgesammt 4950000 Elemente bewegt, bei b) dagegen nur 130048.

Imho macht sich a) mehr schlecht als recht ....