Listen sind dynamische Arrays

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 16:03
Autsch! Warum sind die Listen nicht verkettet?
Gibt einige Gründe.
1. Der element access schneller Um in einer verketteten liste das ite element zu erreichen musst du dich durch alle vorrigen elemente einmal durchhangeln. Bei einem array ist das eine einzige pointer operation.
2. Ein Array hat den Vorteil der cache lokalität. Wenn du also durch einen array iterierst oder auf elemente die nah bei einander sind zugreifst, hast du massive performance verbesserungen da CPUs ganze chunks von memory cachen und in einem Array der gesammte block kontinuierlich ist.
3. Das einfügen und löschen von elementen anhand eines index ist in verketteten listen viel aufwendiger. Asymptotisch braucht sowohl die verkettete Liste als auch das Array Lineare zeit. Bei der verketteten liste um den Index zu finden, beim Array um die elemente zu shiften. Konstanter aufwand ist aber bei der verketteten Liste viel höher, da du für jedes insert eine allokation machen musst (was übrigens auch massiv zur Speicherfragmentierung beitragen kann), während bei einer geometrisch wachsenden Arrayliste nur log(N) viele memory allokationen gemacht werden müssen. Außerdem ist das shiften der elemente dank cachelokalität sehr schnell, während das langlaufen einer verketteten liste verhältnismäßig langsam ist.

Es gibt praktisch nur eine situation in der eine verkettete Liste besser sein kann, und das ist wenn man ein element in der hand hat und danach ein element einfügen will (bei einer doppelt verketteten liste ist auch das löschen an dieser stelle effizient).
Und selbst hier sage ich bewusst besser sein kann, denn abbhängig von der cache lokalität, der größe des arrays, und der position an der man das element einfügen will, gewinnt auch hier der Array das rennen (beispiel, einfügen am und löschen am Ende, bei einer warmgelaufenen Liste mit geometrischem wachstum).

TList hat übrigens auch keine Iteratoren, die einzelne elemente referenzieren. Man arbeitet immer über indizes, das heißt das man so oder so für jede Operation die liste lang hangeln muss, es gibt also absolut keinen Grund das über eine Linked list zu machen. Die Vorteile einer linked list bringen nur was, wenn man auch eine API hat die einem iteratoren rauspuckt.

Timm Thaler
Beiträge: 1089
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Listen sind dynamische Arrays

Beitrag von Timm Thaler »

Warf hat geschrieben:
Fr 11. Sep 2020, 20:05
1. Der element access schneller Um in einer verketteten liste das ite element zu erreichen musst du dich durch alle vorrigen elemente einmal durchhangeln. Bei einem array ist das eine einzige pointer operation.
Wenn ich das ite Element erreichen will - nehm ich ein Array.

Der Witz einer Liste ist ja, dass es eigentlich keine numerierten Elemente gibt - weil lösche ich einen Eintrag, stimmt die Numerierung eh nicht mehr - sondern nur Anfang, Ende, Vorgänger und Nachfolger.
Warf hat geschrieben:
Fr 11. Sep 2020, 20:05
3. Das einfügen und löschen von elementen anhand eines index ist in verketteten listen viel aufwendiger.
Ja, nur: Warum sollte ich das wollen. Siehe Oben: Der Witz an verketteten Listen ist ja, dass ich eine Indizierung weder brauche noch will.
Warf hat geschrieben:
Fr 11. Sep 2020, 20:05
Es gibt praktisch nur eine situation in der eine verkettete Liste besser sein kann, und das ist wenn man ein element in der hand hat und danach ein element einfügen will (bei einer doppelt verketteten liste ist auch das löschen an dieser stelle effizient).
Ähm nein, wenn ich eine Liste mit häufig wechselnden Einträgen habe, ist mir die Indexposition in der Liste doch völlig wumpe. Dafür spare ich mir die ganze Rumkopiererei, wenn ich ein Element einfügen - ok, das kann ich am Ende tun - oder mitten raus löschen will.

Ich hab - da Arrays gewohnt - auch eine Weile gebraucht mich mit den linked Lists von Purebasic anzufreunden. Aber für bestimmte Anwendungen ist es schon ein praktisches Konzept, und eine der wenigen Sachen die ich in Pascal gern auch hätte.

Timm Thaler
Beiträge: 1089
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Listen sind dynamische Arrays

Beitrag von Timm Thaler »

Warf hat geschrieben:
Fr 11. Sep 2020, 20:05
2. Ein Array hat den Vorteil der cache lokalität. Wenn du also durch einen array iterierst oder auf elemente die nah bei einander sind zugreifst, hast du massive performance verbesserungen da CPUs ganze chunks von memory cachen und in einem Array der gesammte block kontinuierlich ist.
Nun werden ja in einer Liste auch nicht die Elemente willkürlich im Speicher verteilt, sondern es wird ein zusammenhängender Speicher reserviert, in dem die Listenelemente liegen. Der braucht vielleicht etwas mehr Platz als ein Array, kann aber dennoch am Stück im Cache liegen.

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 20:53
Wenn ich das ite Element erreichen will - nehm ich ein Array.
Es gibt einen unterschied, einen geometrisch wachsenden array selbst zu schreiben ist gar nicht mal so wenig aufwand. Ich hab mir erst demletzt mit advanced records eine eigene Arraylist klasse geschrieben mit allen wichtigen features (enumeratoren, pointer zugriff auf element, geometrisches wachstum, generics, etc.) und es sind etwa 800 zeilen code geworden. "Da nehm ich ein Array" ist nur eine option wenn man eine feste größe hat. Wenn man unbekannte größe hat, mit vielen insertions und deletions (z.b. für nen Stack zu modellieren), ist ein Array völlig ungeeignet.
Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 20:53
Der Witz einer Liste ist ja, dass es eigentlich keine numerierten Elemente gibt - weil lösche ich einen Eintrag, stimmt die Numerierung eh nicht mehr - sondern nur Anfang, Ende, Vorgänger und Nachfolger.

[...]

Ja, nur: Warum sollte ich das wollen. Siehe Oben: Der Witz an verketteten Listen ist ja, dass ich eine Indizierung weder brauche noch will.
Das kann gut sein, aber da stehst du wohl allein da. Sowohl in Pascal, als auch in Sprachen wie Java in denen Linked Lists noch sehr prevalent sind, ist das Listen interface zum größten Teil über indizes geregelt.

Ich meine du hast recht das Verkettete Listen ihren usecase haben, die sind aber so Niche, das in den allermeisten Fällen eine Arrayliste besser ist. Aus persönlicher Erfahrung kann ich nur sagen, ich hab bestimmt in den letzten 5 Jahren keine einzige situation gehabt in der eine Linked List besser gewesen wäre.
Ähm nein, wenn ich eine Liste mit häufig wechselnden Einträgen habe, ist mir die Indexposition in der Liste doch völlig wumpe. Dafür spare ich mir die ganze Rumkopiererei, wenn ich ein Element einfügen - ok, das kann ich am Ende tun - oder mitten raus löschen will.
Außschließlich wenn du bereits schon das element in der hand hast. Sobald du suchen musst durch die Liste wirds teuer. Ich habe auf dieser Seite mal 2 graphen gefunden: https://dzone.com/articles/performance- ... odern-comp
Bild
Bild
Ich hab - da Arrays gewohnt - auch eine Weile gebraucht mich mit den linked Lists von Purebasic anzufreunden. Aber für bestimmte Anwendungen ist es schon ein praktisches Konzept, und eine der wenigen Sachen die ich in Pascal gern auch hätte.
Ich weiß das es Nützlich sein kann, und ich gehöre auch zu den Leuten die sowas komplett rum optimieren und sich solche Datenstrukturen auch selbst bauen wenn sie fehlen. Ich kann dir aber aus meiner erfahrung sagen, dieser eine usecase, das du durchgängig das "operationselement" in der hand hast, hatte ich bisher so selten das ich mich nicht mal dran erinnere wann das letzte mal war. Die allermeiste zeit will ich bei ner liste einfach was haben wo ich sachen in order reinschrieben kann und rausholen kann und suchen kann. Und da gewinnt eine Array liste einfach immer
Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 21:07
Nun werden ja in einer Liste auch nicht die Elemente willkürlich im Speicher verteilt, sondern es wird ein zusammenhängender Speicher reserviert, in dem die Listenelemente liegen. Der braucht vielleicht etwas mehr Platz als ein Array, kann aber dennoch am Stück im Cache liegen.
Und sobald du das erste element gelöscht oder eingefügt hast ist deine reihenfolge bereits kaputt, außer du maintainest die ordnung, in anderen worten, du hast eine Array liste

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »


Timm Thaler
Beiträge: 1089
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Listen sind dynamische Arrays

Beitrag von Timm Thaler »

Warf hat geschrieben:
Fr 11. Sep 2020, 22:37
Das kann gut sein, aber da stehst du wohl allein da. Sowohl in Pascal, als auch in Sprachen wie Java in denen Linked Lists noch sehr prevalent sind, ist das Listen interface zum größten Teil über indizes geregelt.
Echt? PureBasic kann das seit Jahren und gar nicht schlecht.
Warf hat geschrieben:
Fr 11. Sep 2020, 22:37
Außschließlich wenn du bereits schon das element in der hand hast. Sobald du suchen musst durch die Liste wirds teuer.
Die Seite geht leider auch von der irrigen Annahme aus: "elements of linked-list can be placed anywhere in the memory" - Nein, wenn man Speicher reserviert für die LL, dann liegt die auch in diesem Speicherbereich und kann genauso gecached werden wie ein Array.

Und der Witz an einer Liste ist - dass ich meistens suchen muss.

Nehmen wir mal das klassiche Adressbuch. Wenn ich einen Eintrag brauche, nützt mir ein Index nichts. Und auch eine Reihenfolge der Einträge nützt mir nichts. Wonach will ich die festlegen - Vorname, Nachname, Wohnort, Firma, Alter... kann beliebig sortiert sein.

Hier ist eine LL einem Array klar überlegen.
Warf hat geschrieben:
Fr 11. Sep 2020, 22:37
Ich weiß das es Nützlich sein kann, und ich gehöre auch zu den Leuten die sowas komplett rum optimieren
Im Gegenteil, ich hatte das mit Arrays angefangen und dann gemerkt, dass ich mit Listen viel besser dran bin.

https://www.purebasic.com/german/docume ... index.html

Das ist so genial: Bei einem Swap werden keine Daten rumkopiert, sondern nur die Pointer getauscht. Bei einem Merge werden nicht die Listen umkopiert, sondern nur die Pointer des letzten Elements der ersten Liste und des ersten Elements der zweiten Liste ersetzt. Und Länge und Pointer auf letztes Element angepasst.

Das geht alles um so viel schneller als mit Arrays.
Warf hat geschrieben:
Fr 11. Sep 2020, 22:37
Und sobald du das erste element gelöscht oder eingefügt hast ist deine reihenfolge bereits kaputt, außer du maintainest die ordnung, in anderen worten, du hast eine Array liste
Es gibt keine Reihenfolge. Es gibt Elemente und Pointer auf diese Elemente, und die Elemente liegen willkürlich im Speicher - aber im vorher reservierten Bereich.

Ich hab zum Beispiel Geräte, die vorhanden sein können oder nicht. Und diese haben Sensoren, die vorhanden sein können oder nicht. Die im Betrieb angesteckt oder abgezogen werden können. Die dann eingetragen und ausgetragen werden.

Das könnte man prima mit LL verwalten. Leider muss ich das mit Arrays machen.

Oder ich hab eine GUI, auf der User Elemente beliebig anordnen, verschieben, editieren und löschen können. Funktioniert in Purebasic super mit LL. Die Konvertierung in Pascal ist ein Sackgang.

Also selbst WENN LL in der Verarbeitung langsamer wären - können sie in der Handhabung durchaus angenehmer sein.

Timm Thaler
Beiträge: 1089
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Listen sind dynamische Arrays

Beitrag von Timm Thaler »

Also einen Nachteil haben LL prinzipbedingt: Wenn irgendwo EIN Pointer kaputt ist, ist die ganze Liste kaputt. Hab ich aber nie gehabt, ich pointer auch nicht selbst in der Liste rum sondern überlass das schön dem Compiler.

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 23:41
Echt? PureBasic kann das seit Jahren und gar nicht schlecht.
Ja aber pure basic ist jetzt nicht grade eine sehr beliebte Sprache
Die Seite geht leider auch von der irrigen Annahme aus: "elements of linked-list can be placed anywhere in the memory" - Nein, wenn man Speicher reserviert für die LL, dann liegt die auch in diesem Speicherbereich und kann genauso gecached werden wie ein Array.
[...]
Es gibt keine Reihenfolge. Es gibt Elemente und Pointer auf diese Elemente, und die Elemente liegen willkürlich im Speicher - aber im vorher reservierten Bereich.
Ok hier mal ein beispiel, deine CPU hat genug speicher um 2 elemente zu cachen, du beginnst mit der folgenden sequenc im memory: E1, E2, E3, E4, E5, E6.
Jetzt löschst du E2, deine reihenfolge ist jetzt (die zahlen sind die indizes) E1, _, E2, E3, E4, E5. Jetzt addest du ein element zwischen 4 und 5: E1, E5, E2, E3, E4, E6.

Jetzt willst du durch iterieren: Erster zugriff: cache miss, E1 und E5 geladen. zweiter zgriff, cache miss, E2 und E3 geladen, dritter zugriff kein cache miss, 4ter zuriff cache miss E4 und E6 geladen, 5ter zugriff cache miss, E5 und E2 geladen, 6ter zugriff cache miss, E6 geladen.

Nach einer gewissen anzahl an zugriffen wirst du auf einer liste selbst mit dem smartesten memory manager einfach eine random ordnung haben, und damit dann die ganze zeit über cache misses produzieren.
Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 23:41
Und der Witz an einer Liste ist - dass ich meistens suchen muss.

Nehmen wir mal das klassiche Adressbuch. Wenn ich einen Eintrag brauche, nützt mir ein Index nichts. Und auch eine Reihenfolge der Einträge nützt mir nichts. Wonach will ich die festlegen - Vorname, Nachname, Wohnort, Firma, Alter... kann beliebig sortiert sein.
Und suchen geht dank cache lokalität auf einem kontinuierlichen block deutlich länger. Die C++ STL die komplett auf performance getrimmt ist benutzt selbst für Sortierte listen kontinuierliche memoryblöcke als RBT.
Hier ist eine LL einem Array klar überlegen.
Aber genau hier ist die LL unterlegen, weil du zum suchen einmal komplett durchiterieren musst. Selbst zum sortieren, wenn du quicksort benutzt hast du massiven vorteil durch cache lokalität, da du linear durchsuchst.
Das ist so genial: Bei einem Swap werden keine Daten rumkopiert, sondern nur die Pointer getauscht. Bei einem Merge werden nicht die Listen umkopiert, sondern nur die Pointer des letzten Elements der ersten Liste und des ersten Elements der zweiten Liste ersetzt. Und Länge und Pointer auf letztes Element angepasst.
Selbst bei einem swap, wenn deine daten so groß sind, kannst du ja auch einfach deine daten auf dem heap (oder einem stack allocator) ablegen und eine arrayliste von pointern handhaben. Somit must du auch nicht die daten kopieren.
Also selbst WENN LL in der Verarbeitung langsamer wären - können sie in der Handhabung durchaus angenehmer sein.
Das sehe ich halt komplett anders. Das interface bestimmt die handhabung, die unterliegende datenstruktur die performance. Bei Java z.b. kannst du eine LinkedList oder eine ArrayList verwenden, die stellen beide das selbe interface bereit, und du kannst in 99% der Fälle einfach das eine durch das andere austauschen ohne eine zeile code anzupassen.

Wenn es um die Handhabung geht ist das problem nicht die Unterliegende Datenstruktur, sondern das Interface. Das ist ja tatsächlich auch der Grund warum ich mir oft solche Datenstrukturen selbst schreibe, weil in manchen Situation TFPGList (oder auch TVector) mir einfach nicht ausreichen von der funktionalität.

Mathias
Beiträge: 5039
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunc)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Listen sind dynamische Arrays

Beitrag von Mathias »

Und sobald du das erste element gelöscht oder eingefügt hast ist deine reihenfolge bereits kaputt, außer du maintainest die ordnung, in anderen worten, du hast eine Array liste
Sind die verketteten Liste nicht eine Altlast aus TP-Zeiten, als es noch keine dynamische Array gab ?
Auch musste man dazumal mit den 640KB Base Ram anders wirtschaften, als mit den heutigen GB-Maschinen.
Mit Lazarus sehe ich gün
Mit Java und C/C++ sehe ich rot

PascalDragon
Beiträge: 55
Registriert: Mi 3. Jun 2020, 07:18
OS, Lazarus, FPC: L 2.0.8, FPC Trunk, OS Win/Linux
CPU-Target: Aarch64 bis Z80 ;)
Wohnort: München

Re: Listen sind dynamische Arrays

Beitrag von PascalDragon »

Mathias hat geschrieben:
Sa 12. Sep 2020, 08:12
Und sobald du das erste element gelöscht oder eingefügt hast ist deine reihenfolge bereits kaputt, außer du maintainest die ordnung, in anderen worten, du hast eine Array liste
Sind die verketteten Liste nicht eine Altlast aus TP-Zeiten, als es noch keine dynamische Array gab ?
Auch musste man dazumal mit den 640KB Base Ram anders wirtschaften, als mit den heutigen GB-Maschinen.
Verkettete Listen sind eine ganz ordinäre, algorithmische Datenstruktur, die durchaus ihren Verwendungszweck hat. Das hat nichts mit „aus TP-Zeiten” zu tun.
FPC Compiler Entwickler

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Mathias hat geschrieben:
Sa 12. Sep 2020, 08:12
Sind die verketteten Liste nicht eine Altlast aus TP-Zeiten, als es noch keine dynamische Array gab ?
Auch musste man dazumal mit den 640KB Base Ram anders wirtschaften, als mit den heutigen GB-Maschinen.
Verkettete Listen haben ihren verwendungszweck, und in optimierter Form werden sie auch noch verwendet. Z.B. in Oracles Java JDK/JVM sind sie noch sehr beliebt, dort erden aber nicht einzelne Elemente verbunden sondern blöcke aus elementen (wobei die größe der blöcke so gewählt is um cache lokalität zu optimieren).

Bevor die CPUs solche caches hatten wie heute, waren LLs insgesammt auch einfach schneller im einfügen und löschen von elementen. Mit modernen caches ist aber das rumkopieren von elementen mittlerweile tatsächlich schneller als das pointer entlang hangeln, weshalb auf modernen CPUs LLs nur noch in sehr nichen situationen sinn machen. Die version die Java bietet ist z.b. ein Kompromiss aus beidem, bietet cache lokalität zu einem gewissen grad, während es, grade bei langen listen, das einfügen und löschen recht effizient gestalten kann durch das simple pointer umlegen einer LL

Timm Thaler
Beiträge: 1089
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Listen sind dynamische Arrays

Beitrag von Timm Thaler »

Warf hat geschrieben:
Sa 12. Sep 2020, 00:53
Nach einer gewissen anzahl an zugriffen wirst du auf einer liste selbst mit dem smartesten memory manager einfach eine random ordnung haben, und damit dann die ganze zeit über cache misses produzieren.
Moderne Prozessoren haben mehrere MB Cache, wie wahrscheinlich ist es bitte, dass die LL Elemente so groß sind, dass Dein Szenario zutrifft, aber noch klein genug, dass immer zwei davon in den Cache passen?

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Timm Thaler hat geschrieben:
So 13. Sep 2020, 06:13
Moderne Prozessoren haben mehrere MB Cache, wie wahrscheinlich ist es bitte, dass die LL Elemente so groß sind, dass Dein Szenario zutrifft, aber noch klein genug, dass immer zwei davon in den Cache passen?
Das war ein beispiel, auch wenn 100 elemente in den cache passen, sobald deine liste lang genug ist wirst du cache misses haben. Und eine Arrayliste (also wenn der memoryblock sortiert ist) minimiert die Anzahl an cache misses. Und die mehreren MB Cache sind der L2 cache, den jeder core benutzt, also von allen parallelen prozessen/threads genutzt wird. Meine CPU hat 12 cores, da sind die 6mb L2 cache pro core nur noch 0,5 mb. Zusammen mit den 1MB L1 cache, hat also jeder core knapp 1,5 mb cache zur verfügung, wobei da natürlich auch noch der instruction cache dabei liegt. Also von "mehreren" MB würde ich hier nicht reden

Und wenn du listen hast die eh so klein sind das sie komplett in den cache passen, dann brauchen wir hier nicht über performance zu reden, denn dann ist die performance herzlichst egal. Interessant wird das eh erst auf größeren listen mit ein paar millionen einträgen, und mehreren (hundert) MB speicherverbrauch.
Wobei ich bei kleinen listen sogar vorstellen könnte das die kosten des memory managers massiv dominieren, welche bei größeren listen irrelevant im verhältnis zur asymptotischen Laufzeit werden.

mschnell
Beiträge: 3417
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: Listen sind dynamische Arrays

Beitrag von mschnell »

PascalDragon hat geschrieben:
Fr 11. Sep 2020, 16:36
Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 16:03
Warum hat Pascal das nicht so implementiert?
Weil du mit Arrays 'nen schnelleren indexbasierten Zugriff hast. Dafür ist halt Einfügen/Entfernen potentiell langsamer (wobei Einfügen am Ende auch trivial ist, so lange die aktuelle Kapazität noch nicht erreicht ist).
Wenn man einen Kompromiss zwischen Einfüge- und Lese- Effizienz will, muss man eine (Memory-) Datenbank nehmen.
-Michael

Socke
Lazarusforum e. V.
Beiträge: 2780
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Listen sind dynamische Arrays

Beitrag von Socke »

mschnell hat geschrieben:
Mo 14. Sep 2020, 10:20
Wenn man einen Kompromiss zwischen Einfüge- und Lese- Effizienz will, muss man eine (Memory-) Datenbank nehmen.
-Michael
Dann stellt sich aber auch hier die Frage: Welche Datenstruktur nutzt die Datenbank? Sind es Arrays, verkettete Listen oder vielleicht sogar Bäume? Bäume? Warum wurden Pascal-Listen nicht als Bäume implementiert?!
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

Antworten