Gilt auch für die konkrete Java-Klasse:
So, when should you use LinkedList? For a long list that works as a FIFO queue, the LinkedList should be faster than the ArrayList. However, even faster is the ArrayBlockingQueue or the CircularArrayList that I wrote a few years ago. The answer is probably „never“.
[JavaSpecialists 111] - What is faster - LinkedList of ArrayList?
und Funktionalität, speziell unmodifiable Head-Tail-Listen sind was davon? genau 
neben all den möglichen Problemchen einer LinkedList zusätzlich auch noch der riesige Aufwand, bei mancher Änderung komplett neue Liste zu erzeugen…
[QUOTE=SlaterB]und Funktionalität, speziell unmodifiable Head-Tail-Listen sind was davon? genau
neben all den möglichen Problemchen einer LinkedList zusätzlich auch noch der riesige Aufwand, bei mancher Änderung komplett neue Liste zu erzeugen…[/QUOTE]
Das hatten wir doch alles schonmal. Es gibt auch entsprechende „funktionale“ (*) Alternativen für Datenstrukturen, die wahlfreien Zugriff benötigen. Das klassische Paper dazu hatte ich schon mehrfach genannt, **lesen **kann ich aber nicht für dich. Irgendwie ist es schon zwanghaft, wie du an jeden Baum pinkeln musst, an dem „funktional“ dransteht.
(*) genauer gesagt „persistente“ (was aber auch mehrere Bedeutungen hat).
ist es nicht bedenklich, zu so einem Grundthema wie Listen ein ‚Paper‘ posten zu müssen?
für beweisbar sichere Profi-Anwendungen sicher praktisch, aber für Programmieranfänger?
auch jede normale Frage dazu wird zu einem Wissenschaftsprojekt
Scala equivalent of java.util.ArrayList - Stack Overflow
oder auch noch
A Tour of Scala - an interactive scala tutorial - Mutable Collections
Scala „encourages“ using immutable collections (hence they are those used by default) however sometimes mutable collections might have some benefits
→ Scala als Beispiel ist eine Sprache die LinkedList als Standard verwendet, also quasi komplett ‚should be avoided‘
ein interessanter Fakt zum Thema, einfach genannt, kannst du unnötig niedermachen oder nicht, wie du möchtest
Die Essenz der Aussage des Vortrages ist, das JEDE Objektorientierte Sprache im Kern eine LinkedList ist. Die Ableitungshierarchie ist nichts anderes als eine LinkedList.
Sollte man deshalb jetzt alle OO Sprachen vergessen? Sicher nicht! Nur sollte klar sein, dass eben alles auch kostet.
Genauso ist es mit funktionalen Sprachen - denkt man bis zum Schluss, waere es immer am besten, haette man nur pure functions. Schlicht deshalb, weil man sich nie mehr um Aenderungen an Datenstrukturen kuemmern muss, da immer alles neu erzeugt wird (immutable). Das macht den Code prinzipiell einfacher. Und kostet eben.
Fuer mich ganz klar, Stroustrup hat den Titel versemmelt, sollte heissen: “Why you should never listen to a talk given by Stroustrup”
Jetzt ist mir auch bewusst warum “The C++ Programming Language” unlesbar ist.
Aber zurueck zum Thema, ich behaupte mal ganz einfach dass die meisten Listen mit denen man als Anwendungsentwickelr zu tun hat weniger als 10 Elemente enthalten, da von performance Nachteilen zu reden ist am Thema vorbei, speziell wenn Performance nicht wirklich den Loewenanteil an Kosten fuer Software hat, damit behaupte ich einfach mal das Bjarne viel zu viel ueber premature optimisation redet.
Was ich gar nicht verstehe ist wie man hier ueber Scala streiten kann, ist gar nicht das Thema…
ein Set oder eine Map verwendet man aber schon auch als wichtige Grundelemente,
und wäre sicher nicht begeistert wenn intern alles über lange Listendurchläufe abgewickelt wird,
LinkedList statt ArrayList ist über dem Daumen etwa ein solcher Fall:
wo es auch schnell gehen kann wird intern Bremse eingesetzt, von außen nicht zu erkennen
freilich auf GHz-CPU nicht direkt zu merken,
falls es dann aber doch mal eine größere Liste wird vielleicht an das Falsche gewöhnt oder schwer Code umzustellen…,
warum die Gefahr bewußt einbauen?, LinkedList zu schreiben ist ja nichtmal textuell kürzer als ArrayList 
bisschen auch wie String + String in Schleifen, da kann man irgendwann tatsächlich 20 sec statt 0.002 sec schaffen,
mit LinkedList freilich nicht so ernst
[quote=SlaterB]freilich auf GHz-CPU nicht direkt zu merken,[/quote]Das hat mit der Geschwindigkeit der CPU erst mal gar nichts zu tun, denn es geht um die Lokalität der Daten, auf die zugegriffen wird, also wie wahrscheinlich es ist, dass die benötigten Daten bereits im schnellen Cache den CPU (S-RAM) liegen und nicht erst aus dem langsamen Arbeitsspeichern (D-RAM) oder gar von der Festplatte geladen werden müssen.
Was Bjarne hier verschweigt ist, dass diese Wahrscheinlichkeit nicht so dramatisch sinkt nur weil man eine LinkedList nutzt. Erst wenn die Liste eine kritische Größe erreicht wird das relevant.
bye
TT
Ist jetzt nicht so neu, die komplexe, aktuelle Hardwarearchitektur mit ihren ganzen Spielerein sorgt bei Laufzeitbetrachtungen bei den Konstanten vor den ganzen Komplexitäten für Verzerrungen. Und Stroustrup zielt darauf ab, im ursprünglichen Video sagt er am Ende (im Kontext von Performance) er empfiehlt speicherkompakte Datenstrukturen und einen ebenmäßigen Zugriff auf diese. D.h. nicht wild im Speicher umherhüpfen, um eben die beste Unterstützung durch die aktuelle Hardwarearchitektur zu erhalten. C++ hat noch den Vorteil das es Value-Types hat und man somit schon automatisch für ein Cache-freundliches Speicherlayout gesorgt werden kann.
Das Löschen am Ende der LL geht noch etwas schneller wenn die Methode removeLast der LL verwendet wird. Was mich aber etwas irritiert ist, dass das Einfügen/Löschen am Ende länger dauert als am Anfang wobei prinzipiell ähnliches gemacht wird. Da die LL eine Referenz auf Anfang und Ende kennt wäre meine Erwartung das beides ungefähr gleich schnell sein müsste.
ist auch ziemlich genau gleichschnell, nur werden in dem Test für Ende um Faktor 1000 mehr Durchläufe ausgeführt
Sicher gibt es auch zugänglichere Quellen als das Paper (wobei der hier relevante Teil 6.2.1. „Binary Random-Access Lists“ auch keine Raketenwissenschaft ist), aber ich habe den Eindruck, dass du weniger diskutieren oder lernen, sondern eher sticheln willst. Nun ist ja jedem völlig selbst überlassen, ob er sich mit einem Thema beschäftigen will oder nicht, nur ist es in letzteren Fall albern, seine Unwissenheit auch noch wie eine Monstranz vor sich her zu tragen und bei jeder sich bietenden Gelegenheit zu demonstrieren.
Ich meine, es gibt sicher genügend Themen, bei denen du wesentlich mehr als ich weißt, und ich das auch gern offen zugebe, warum kannst du das umgekehrt nicht auf diesem einen Gebiet auch? Oder versuche doch einfach mal wirklich vorurteilsfrei an das Thema heranzugehen, statt anderen andauernd unqualifiziert ans Bein zu pinkeln.
Falls du es nicht mitbekommen hast: Ich lasse mich durch diese Einwürfe nicht mehr triggern, werde sie aber auch nicht umkommentiert so stehenlassen.
Ah voll übersehen.
echt? hätte diesen Abschnitt zu was auch immer ‚hier‘ ist nicht relevanter als jeden anderen im Paper erkannt,
datatype a Tree = Leaf of a | Node of int x a Tree x a Tree
datatype a Digit = Zero | One of a Tree
type a RList = a Digit list
und was auch immer alles…
in welchem Thema hier im Forum wurde zuletzt in solchen Bahnen diskutiert/ gesprochen?
und deswegen darf nicht auf LinkedList in Funktionalität hingewiesen werden? soso
deine wiederholten Pinkeltheorien überlasse ich dir mal ganz, spricht ausreichend für dich…
Ist das wirklich so unglaublich furchtbar, mal eine andere Syntax zu lesen? Ich kann auch kein ML, aber komischerweise kann ich damit trotzdem etwas anfangen:
datatype a Tree = Leaf of a | Node of int x a Tree x a Tree -> ein Baum ist entweder ein Blatt, das ein a beinhaltet, oder ein Knoten, der ein a und zwei Unter-Bäume beinhaltet
datatype a Digit = Zero | One of a Tree -> eine “Stelle” ist entweder leer oder beinhaltet einen Baum
type a RList = a Digit list -> Eine RListe ist eine Liste von “Stellen”
In Java wäre also RList<A> ungefähr List<Optional<Tree<A>>>.
Jetzt erzähle mir, wo da für dich die Schwierigkeit liegt.
Was die “Bahnen” angeht: Ausgangspunkt ist ein Video über ganz normaler veränderliche Datenstrukturen, die es genau so auch in der Java-Standard-Bibliothek gibt. Dann kommst du, verteilst mal eben off-topic unbegründete Seitenhiebe auf funktionale Datenstrukturen (die man natürlich wie alles andere auch falsch einsetzen kann, also ein typisches Strohmann-Argument). Wenn man darauf hinweist, dass auf den Einwand schon x-mal geantwortet wurde und es sehr wohl geeignete Alternativen gibt, ist das natürlich wieder zu schwierig und akademisch. Du machst einfach nicht den Eindruck, dass du überhaupt an einer Diskussion interessiert bist, sondern dass du einfach bloß provozieren willst. Dabei ist das Thema durchaus interessant, nur ist mir meine Zeit zu schade, um gegen eine Wand zu reden.
[ot]
Kommt mal runter, ihr Zicken 
Das war kein Paper.
Das war eine…
Doktorarbeit. Was sollen die Leute auch machen, die zwar Informatik studiert haben, aber dann merken, dass sie gar nicht Programmieren können? 
Sowas wie TAOCP wäre wohl nichts für dich. „Sortieren … da muss man doch nur Arrays.sort aufrufen!“.
(Nicht so ernst nehmen. Ich finde es nur im 
- Sinne etwas unterhaltsam. Vielleicht weil ich mich sowohl in der Ecke derer, die GAR keinen Praxisbezug mehr haben, nicht so heimisch fühle, als auch nicht befürworte, seinen Horizont mit Radius 0 als „Standpunkt“ zu bezeichnen. Den Horizont kann man übrigens sehr elegant mit Geometrischer Algebra ausrechnen. Davon werdet ihr in Zukunft noch öfter hören.
[/ot]
On-topic? Morgen, vielleicht
hmm, der Vergleich dazu wäre doch eher, sich hier gar nicht für den inneren Aufbau der Listen zu interessieren, das Gegenteil von dem was hier passiert!
bekannte Sortierverfahren anzuschauen, zu implementieren, zu vergleichen ist eine anschauliche und typische Aufgabe für gehobene Anfänger,
erste Semester Informartik an der Uni, evtl. auch schon ein nettes Theme für Informatik-Unterricht an der Schule
ArrayList vs. LinkedList ist genau die gleiche Höhe, inneren Aufbau kennenlernen, interpretieren, Vor- und Nachteile bei bestimmten Operationen voraussagen oder benchmarken
Inhalt wie aus dem Paper
Essentially, this function resets the first 1 to 0, while setting all the preceding 0s to 1 s. The analogous operation on lists of trees is
borrowTree. When applied to a list whose first digit has rank r, borrowTree returns a pair containing a tree of rank r, and the new list without that tree.
wird in dem Art-Buch hoffentlich nicht vorkommen oder höchstens auf wenigen Prozent der Seiten notgedrungen statt als durchgehende Standard-Sprache,
dieses Paper ist ja schließlich auch eine Doktorarbeit
Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
…,
welchen Zweck das hat, das hier zu posten, verstehe ich weiterhin nicht, erscheint auf jeden Fall unpassend
funktionale Listen sind ein interessanterr Listengrundtyp und im internen Aufbau stark an LinkedList angelehnt,
was könnte es an der Aufnahme dieses Punktes in den Thread für ein Problem geben?
-
ArrayList haben den Speichervorteil der zusammenhängen Ablage der Daten und kommen bestens mit Add/ Remove am Ende der Liste zurecht,
Hinzufügen/ Entfernen am Anfang dagegen schlimme Sache, Queue mit FIFO von Standard-ArrayList denkbar ungeeignet zu implementieren -
doppelt verkettete zustandbehaftete LinkedList kommt bestens mit Änderungen vorne wie hinten aus,
einzelner Zugriff in der Mitte ganz schlimm,
beim Durchlauf immer noch hier angesprochenes theoretische Speicherproblem, jeweils Sprung an beliebige Stelle im Arbeitsspeicher, -
Head-Tail-Listen sind nach vorne hin wie LinkedList, bedenklich aber Richtung Ende der Liste…,
allein schon der Lauf dorthin langsam, nach strengen Konzept wird sicher kein Link direkt ans Ende bestehen
der GAU dann aber wenn gar noch Elemente hinten entfernt oder hinzugefügt werden müssen, kompletter Listenneuaufbau,
nicht nur langsamer Speicherzugriff auf jedes einzelne Element in der Liste, was dem Video von Anfang schon Performance-Bedenken wert war,
sondern gar noch für jedes einzelne Element neue Speicherplätze anzulegen…, zigfach langsamer!
falls die Implementierung gar ganz streng minimal ist,
dann wird auf spezielle Implementierung für Methoden für hinten-Operationen verzichtet, sondern auf die vorhandenen Methoden zugriffen:
erst reverse(), Liste umkehren, dann ein Element vorne hinzufügen oder entfernen, dann nochmal reverse(),
also den Aufwand nochmal verdoppelt, zwei neue Listen in allen Bestandteilen komplett neu angelegt!
faszinierend als Möglichkeit und mag man alles für beweisbare Sauberkeit im Code hinnehmen,
aber schon eine erstaunliche Langsamkeit, welche Thematisierung wert ist,
da muss man sich nicht angegriffen fühlen, als Tatsache einfach interessant und wichtig zu wissen
eine Head-Tail-Liste darf man besser überhaupt nur wie eine Art Stack benutzen, vorne anfügen, vorne wieder abnehmen,
Durchlauf ohne Änderungen geht auch noch,
alles andere reichlich nicht empfehlenswert, und das ist die Standardliste in funktionalen Sprachen!..
die klassische Sicht auf eine Liste, ganz normales Anfügen am Ende, wird technisch verboten bzw. höchst inperformant gemacht,
wenn LinkedList in Java schon ihre Probleme hat, und zum Glück auch nicht der Standard ist, dann kommt sie doch noch weitaus besser zurecht,
Head-Tail-Listen sind um ein Vielfaches bedenklicher
[QUOTE=SlaterB]faszinierend als Möglichkeit und mag man alles für beweisbare Sauberkeit im Code hinnehmen,
aber schon eine erstaunliche Langsamkeit, welche Thematisierung wert ist,
da muss man sich nicht angegriffen fühlen, als Tatsache einfach interessant und wichtig zu wissen[/QUOTE]
Es geht nur am Rande um theoretische Dinge wie Beweisbarkeit von irgendwas.
Die Langsamkeit einer einzelnen Kopieraktion einer immutable List ist voellig irrelevant, wenn man bedenkt, dass das dafuer jeder Funktionsaufruf in einem eignen Prozess (im Idealfall als auf einem eignen CPU Kern) laufen kann. OHNE das man irgendwas am Code aendern muss.
Zudem ist es voellig absurd, gegen funktionale Sprachen mit dem Performancethema zu argumentieren, wenn man Java (!) als Alternative hernimmt.
Und uebrigens, man sollte auch bei Java stets Kopien von Listen zurueckliefern (in Methoden, die Zugriff auf internen Zustand einer Klasse bieten). Ansonsten kann man die Liste veraendern und damit auch den Zustand, den man eigentlich verstecken wollte. Wodurch information hiding als Grundprinzip von OOP ins Absurde gefuehrt wird.
Ganz oben drauf kommt noch, Compiler fuer funktionale Sprachen koennen teilweise deutlich besser Optimieren - das Performanceproblem kommt primaer aus der Garbage Collection - und das Problem existiert 1:1 auch in der Javawelt.
wenn eine Methode eine Liste hat und ein Element hinzufügen soll und die vergrößerte Liste zurückgeben soll, der Aufrufer auf die neue Liste wartet um damit zu arbeiten,
welche Funktionsaufrufe sollen dann von was ausgelagert werden zu welchem Zweck?
soll der Methoden-Prozess an sich (und vor allem der Aufrufer…) nutzlos warten während ein separater Prozess die Liste zusammenbaut?
durch den kettenartigen Aufbau kann auch der Kopiervorgang der Liste nicht aufgespalten werden, muss alles in Reihenfolge passieren
Und uebrigens, man sollte auch bei Java stets Kopien von Listen zurueckliefern (in Methoden, die Zugriff auf internen Zustand einer Klasse bieten). Ansonsten kann man die Liste veraendern und damit auch den Zustand, den man eigentlich verstecken wollte. Wodurch information hiding als Grundprinzip von OOP ins Absurde gefuehrt wird.
auch wenn dieses Konzept für sich seine Fragezeichen hat, kann gut oder ähnlich verschwenderisch sein,
ist eine fachliche Entscheidung zur Kopie noch eine ganz andere Sache als technischer Zwang,
eine Kopie am Ende der Rückgabe ist eine Sache, aber genauso 1000 unnötige Zwischenkopien beim internen Zusammenbau?
man wird technisch zur Verwendung von mutable Zwischenobjekten oder Reihenfolgevorgabe gezwungen (vorne anfügen weil leichter, am Ende reverse() )
mit BigDecimal oder vor allem String hat man in Java durchaus ähnliches,
besonders der String-Zusammenbau in Schleifen wie schon genannt anschaulicher Vergleich, simpel mit + zusammenfügen ergibt immer neue Kopien,
auch in normalen Programmen durchaus schnell mal Probleme von zig Sekunden Ausführdauer wo ms erreicht, nicht nur graue Theorie,
schafft es gelegentlich als Anfänger-Problem-Threads in Foren,
dasselbe Fiasko könnte man bei unbedarfter Verwendung von Head-Tail-Listen mit Anfügen hinten haben, gefährlich,
bei String ist man zu StringBuilder gezwungen, schlimm genug, aber deswegen nicht für Listen 1:1 genauso vertretbar,
Listen sind höhere intelligentere Objekte als ein String als Zeichenkette, Listen will man sortieren, umdrehen, durchsuchen können
man kann extra Listen von Teil-Strings einsetzen, genau um nicht der Komplexität eines langen zusammengesetzten Strings ausgesetzt zu sein,
man stelle sich vor, 10 Teil-Strings wären in einem großen String gespeichert:
„aaaaaaaaa, eeeeeeeeee, bbbbbbbbbb, cccccccccc, dddddddddd, usw.“
und wollte dann sortieren, oder ein Element herausnehmen, String parsen, aufsplitten, umständlich suchen wo ein bestimmter Teil beginnt, neu zusammensetzen usw., schrecklich
in Teilen stellt sich die Verwendung von LinkedList und auch Head-Tail-Listen so umständlich dar
edit:
warum schaltet Java jede Performance-Frage aus?
auch in Java verwendet man Sets, Maps, DB-Cache usw., von jedem Level aus kann man sich um aktuelle Lage bemühen oder nicht
[QUOTE=SlaterB]warum schaltet Java jede Performance-Frage aus?
auch in Java verwendet man Sets, Maps, DB-Cache usw., von jedem Level aus kann man sich um aktuelle Lage bemühen oder nicht[/QUOTE]
Wegen des Garbage Collectors. Wenns dir um wirkliche Performanceoptimierung geht, kommst du um eine Sprache nicht rum, wo du zumindest den GC abschalten und dann direkt im Speicher rummachen kannst.
Bei Parallelisierung gehts meist um das mehrfache, parallele Abarbeiten des Programms, z.B. bei einem Server, der Requests abarbeitet. Bei funktional ist jeder Request ein Aufruf der “obersten” Funktion. Klassisch brauchst entweder Threads (da musst hoellisch aufpassen und entsprechend Listen & Datenstrukturen kopieren) oder startest eine JVM pro Request. Beides ist alles andre als performant.
Imho der Hauptgrund dafuer, das Node.JS so gross geworden ist. Da kannst mit einer haesslichen Sprache (JS), die interpretiert und nicht kompiliert wird (hat V8 nen JIT?) auf kleinerer Hardware mehr Requests verarbeiten, als mit nem schicken EE Container.
Das mit den Zwischenkopien beim Verarbeiten von Listen in funktionalen Sprachen ist nicht relevant. Das optimiert der Compiler einfach weg, so dass am Ende die Liste genau einmal durchlaufen wird und alle Aenderungen (map, filter, etc) innerhalb dieses einen Loops durchgefuehrt werden. Ausserdem koennen hier einmal erzeugte List-Instanzen auch wiederverwendet werden (vom Compiler), sobald sie aus dem aktuellen Scope gefallen ist.