# Arrays vs Liste vs Vector



## aha_01 (4. Jan 2011)

Hallo,
ich habe ein Verständnisfrage:
was ist am Perfomantesten zu benutzen: Arrays bzw. multidim. Arrays, Listen, Vectoren, oder ArrayListen,...?
Welches ist schneller? Welches braucht mehr Speicher?...

Ein Link zu einem GUTEN Tuto. AUF DEUTSCH wäre auch ne gute Antwort :rtfm:

Danke im Voraus 
Grüße 
Aha


----------



## nrg (4. Jan 2011)

Arrays für indexierten Zugriff und wenn die Anzahl der Elemente davor klar sind
ArrayList für den indexierten Zugriff und wenn die Anzahl der Elemente nicht zurvor klar sind
LinkedList, wenn du häufig zwischendrin Elemente hinzufügen oder löschen musst
TreeList oder TreeMap, wenn die Liste/Map immer sortiert sein soll
Maps für eine Key/Value Beziehung
Vectoren oder HashTable, wenns ThreadSafe sein soll

Aber so ganz pauschal kann man das nicht sagen. Da spielen schon noch paar mehr Faktoren rein. Finde das Tut hier ganz gut: http://www.inabrenner.de/pdf/SCJP.pdf Kapitel 12 - Das Collection Framework


----------



## sambalmueslie (4. Jan 2011)

hm ganz allgemein würde ich dir Java ist auch eine Insel empfehlen  gibts als Openbook 

Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 3.10 Arrays

der prinzipielle Unterschied zwischen 

- Arrays, mehrdimensionalen Arrays 
und
- Listen, Vektoren usw.. 

ist, dass es sich bei dem einen um einen nativen Datentypen handelt (Array) und bei dem anderen um Klassen.
Mit allen Vor- und Nachteilen die es dafür gibt.

Am performantesten und unflexibelsten sind sicher Arrays wobei es keinen Unterschied macht ob mehrdimensional oder nicht, da das einfach nur ein umrechnen des Indexes ist  die Daten liegen in beiden Fällen einfach hintereinander im Speicher (zumindest war das bei C++ so)

Die anderen dynamischen Container (Liste, Vector usw.) sind sehr flexibel haben dafür aber auch einen Verwaltungsaufwand.
Am besten schreibst du dir ein kleines Programm das mit den jeweiligen Typen arbeitet.
(Zugriff, Suchen, Hinzufügen usw.. ) um herauszufinden was am schnellsten ist. Die Frage ist aber, ob das wirklich nötig ist?
Im Zeitalter heutiger Rechenleistung ist das durchlaufen einer Liste eher Peanuts, so lange die Liste nicht gerade die Telefonbuchdaten für ganz Deutschland enthält


----------



## nrg (4. Jan 2011)

@sambalmueslie: das was du meinst sind primitive Datentypen aber das hat nix mit Arrays bzw. Collections zu tun. Arrays können genauso gut auch mit Objekten gefüllt sein. Der Grund warum es keine primitiven Listen o.ä. gibt ist, weil es ganz einfach keine primitiven Generics gibt. Dafür gibt es aber Wrapper-Klassen


----------



## aha_01 (4. Jan 2011)

Danke für die rasche Antwort Leute dies hat mir n bißjen die Augen aufgemacht :toll:


----------



## Icke_ (4. Jan 2011)

Hallo,

Du musst echt aufpassen, ein Teil der Äußerungen ist einfach falsch. Ein Array ist in Java genauso eine Klasse wie alle nicht primtiven Datentypen auch. 

Auch sind Arrays nicht "unflexibel", der Aufwand ist hier nur anders. Alle Datenstrukturen die Du benannt hast (Vector, Listimplementierungen und Arrays) dienen der Sammlung von mehreren gleichartigen Typen.

Bei einem Array handelt es sich um einen zusammenhängenden Speicherbereich, der eine feste Anzahl von Objekten eines bestimmten Typs aufnehmen kann. Das besondere hierbei ist, dass Du den Speicher in einem Rutsch und vollständig allokierst. Erzeugst Du ein Array mit 500.000 Elementen wird der benötigte Speicher sofort reserviert, auch wenn Du diesen Speicher überhaupt nicht verwendest. Auch kennt ein Array seinen Füllstand nicht, jede Zelle im Array hat einen Index (beginnend bei 0), der genau ein Element referenziert. Beim Zugriff auf das Array gibst Du immer explizit den Index der Zelle an, in die Du etwas schreiben bzw. aus der Du etwas lesen möchtest. Welche Zelle Du schon befüllt hast weiß das Array nicht, diese Information müsstest Du selbst pflegen.
Ein Array ist in seiner Größe statisch. Das heißt, dass wenn Du ein Array der Länge 10 erzeugst, Du genau 10 Elemente aufnehmen kannst. Brauchst Du Platz für ein 11tes Element, erzeugst Du ein neues größeres Array und kopierst die Werte des Alten rüber.
Der Vorteil von Arrays ist, dass Du die Kosten für die Speicherallokation auf alle Elemente verteilst. Das Reservieren von Speicher verursacht fast konstante Kosten, relativ unabhängig von der Größe. Erzeugst Du ein Array mit 500.000 Elementen dauert die Speicherreservierung nicht länger als die Erzeugung eines Arrays mit 5 Elementen. 
Hast Du zudem einen primitiven Datentypen steht die Größe jedes Datums fest und Du kannst für jeden Index, die Größe des Datentypen und der Startadresse des Arrays sofort die Adresse einer Zelle bestimmen. Das ist sehr effizient und durch lokalen Caching wird in der Regel gleich ein guter Teil des Arrays mit geladen, so dass kostenaufwändige Sprünge im Speicher entfallen. 

Das ist aber nur die halbe Wahrheit. Erstellst Du ein Array von Objekten, dann sieht das ganze etwas anders aus. Nimm z.B. ein Array von 10 Strings, hier kannst Du nicht sagen wie groß der benötigte Speicher sein wird, das hängt von der Länge der Strings ab. Das gilt aber nicht nur für Strings und deshalb bedient man sich der Indirektion. Ein Array das Objekte speichert, legt nicht die Objekte selbst ab, sondern verwaltet Referenzen (Zeiger) auf die Objekte. Zwar hast Du somit die Adressen der Objekte in einem zusammenhängenden Speicher und hier alle Vorteile des Feldes, der Zugriff auf das eigentliche Datum (Objekt) erfordert aber das auflösen der Referenz, was einem Sprung im Speicher gleich kommt, somit verlierst Du hier den Vorteil. Auch wird der Speicher für die einzelnen Objekte erst reserviert, wenn Du diese mittels new-Operator erzeugst (natürlich gilt das nicht für Elemente, die static markiert sind, aber das ist ein anderes Thema).

Listen widerum sind dynamische Strukturen, deren Größe automatisch verwaltet wird. Der Klassiker ist die verlinkte Liste, bei der jedes Element einen Zeiger auf seine Nachbarn verwaltet. Wird ein neues Element Y eingefügt, so wird das letzte Element der Liste X mit Y verlinkt, wobei der Nachfolger von X auf Y gesetzt wird und der Vorgänger von Y auf X. Existieren Vorgänger und Nachfolger, nennt man das doppelt verkettet, man kann auch nur in einer Richtung verketten, etc. Zudem kann man sich das erste und letzte Element explizit merken. Der Vorteil so einer Liste ist, dass immer genau der Speicher verwendet wird, der wirklich für die Datenhaltung benötigt wird. 
Allerdings hast Du keinen Wahlfreien Zugriff mehr auf ein Element. Willst Du das dritte Element, musst Du vom ersten Element zum Nachfolger und hier zum Nachfolger (einen Index gibt es ja nicht). Da die Elemente nach und nach erzeugt werden, entsteht bei jedem Hinzufügen der Aufwand zum Erzeugen eines neuen Elements und es entstehen Kosten für die Reservierung des Speichers. Zudem hängt der so erzeugte Speicher nicht zusammen und man muss kostenintensiv hin und her springen (ggf. müssen eben Speicherbereiche erst geladen werden). 
Der Vorteil von Listen ist, dass Du einfach Elementen hinzufügen oder entfernen kannst, die Größe wird automatisch angepasst. Dafür muss man mit Performanceeinbußen beim Zugriff rechnen.

Ein Kompromiss aus den Vorteilen der beiden beschriebenen Lösungen stellt eine ArrayListe dar. Ein solches Element arbeitet zunächst wie eine Liste und kümmert sich selbst darum, dass die Größe der Liste angepasst wird. Allerdings wird der Speicher hier nicht auf exakt die benötigte Größe beschränkt. Vielmehr wird zunächst ein Array einer bestimmten Größe erzeugt. Sagen wir der Größe 10 (das ist ein rein fiktiver Wert). Werden Elemente hinzugefügt (oder entfernt) inkrementiert bzw. dekrementiert die ArrayListe einen internen Wert, der dem Index des letzten belegten Felds entspricht. Nähert sich die Belegung einem bestimmten Anteil (z.B. 80% Füllstand), dann wird ein neues Array erzeugt. Hier kann es verschiedene Möglichkeiten geben dieses zu berücksichtigen. Man kann hier eine verkettete Liste verwenden, die eben die Arrays verknüpft, man kann aber auch ein größeres Array erzeugen und die Daten verschieben oder auch eine ganz andere Lösung finden.
Der Vorteil einer ArrayList ist somit, dass man eine gute Effizienz durch die Verwendung von Arrays erhält, aber auch die Dynamik einer Liste nutzen kann. 

Weitere wichtige Strukturen sind, wie schon durch die anderen Posts erwähnt, Maps. Diese speichern eine Schlüssel-Wert Beziehung, bei der einem Schlüssel genau ein Wert zugeordnet wird. So wie ein Array zu einem bestimmten Index die Belegung liefert, liefert eine Map die Belegung zu einem gegebenen Schlüssel. 
Willst Du eine mathematische Menge von Elementen verwalten, so kannst Du auf Sets zurückgreifen. Auch ein Set nimmt eine dynamische Anzahl von Elementen gleichen Typs auf, allerdings wird jedes Element nur genau einmal aufgenommen. Fügst Du die Werte (1,3,4,1,3) in ein Set ein, so würde hier nur (1,3,4) gespeichert werden. 

Allgemein für die Collection-Klassen gilt, dass jede Variante die nicht threadsafe ist deutlich performanter läuft als ihr für Nebenläufikgeit ausgelegtes Pendant. Threadsafe heißt immer Kosten für Syncronisation und die übersteigen viele einfache Operationen um den Faktor 100 oder mehr. Entsprechend sollte man diese Klassen wirklich nur einsetzen wenn nebenläufig auf die gleiche Collection zugegriffen wird.


----------



## bygones (4. Jan 2011)

Icke_ hat gesagt.:


> Auch sind Arrays nicht "unflexibel", der Aufwand ist hier nur anders. Alle Datenstrukturen die Du benannt hast (Vector, Listimplementierungen und Arrays) dienen der Sammlung von mehreren gleichartigen Typen.


doch sind sind... array ist fix und man kann ihn nicht vergrößern, verkleinern.

Rest ist zu viel zu lesen ....


----------



## SlaterB (5. Jan 2011)

Icke_ hat gesagt.:


> Nähert sich die Belegung einem bestimmten Anteil (z.B. 80% Füllstand), dann wird ein neues Array erzeugt.


eher wenn genau 100% erreicht sind, welchen Sinn hätte es schon früher hochzugehen?
dann hätte man immer 20% leer, Vorgabe der genauen Größe wäre hinfällig

in einer Map mit Kollisionen gleicher Keys kann man Platz vorrätig halten

interessant ist, um wieviel das Array der ArrayList bei Überlauf vergrößert wird,
nur eine weitere Position wäre für sich speichersparsam, bei 10x Einfügen hintereinander aber ständig erforderlich und dann sehr aufwendig,
zu viel sollte man auch nicht dazugeben, sonst hat man vielleicht viel leeren Platz,
es wird also 150% der vorherigen Größe gewählt oder ähnlich


----------



## maki (5. Jan 2011)

> interessant ist, um wieviel das Array der ArrayList bei Überlauf vergrößert wird,


Sie wird verdoppelt, ist ein kompromiss zwischen Speicherveschwendung und dem teueren allokieren von mehr Speicher.

@Icke_
List bietet immer wahlfreien Zugriff über get(..), also zB. auch LinkedList, der Unterschied ist die Laufzeit.
Es gibt ausserdem einen Unterschied zwischen synchronisierten Collections und denen für  Nebenläufigkeit (Concurrency), die Standard Collections sind nicht syncronisiert, aber syncronisiert ist eben genau das Gegenteil von Nebenläufig.
Magst vielleicht in Zukunft über Dinge schreiben die du kennst, dann vielleicht gerne auch weniger


----------



## SlaterB (5. Jan 2011)

also in meiner Java-Version sind es ca. 150% 

```
/**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure  that it can hold at least the number of elements
     * specified by the minimum capacity argument. 
     *
     * @param   minCapacity   the desired minimum capacity.
     */
    public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
	    elementData = (E[])new Object[newCapacity];
	    System.arraycopy(oldData, 0, elementData, 0, size);
	}
```
Magst vielleicht in Zukunft..


----------



## tuttle64 (5. Jan 2011)

aha_01 hat gesagt.:


> Welches ist schneller?




schnell bezüglich was, sequentieller durchlauf oder sortiertes einfügen? wie du bereits an den obigen antworten entnehmen kannst, gibt es auf deine allgemeine frage keine allgemeine antwort.


----------



## kirdie (6. Jan 2011)

@Aha: Kennst du dich mit Komplitätstheorie aus? Das hat mir sehr viel geholfen um zu wissen, wann welche Collection oder ein Array gut ist. Bei so kleinen Sachen (wo die Geschwindigkeit nicht so wichtig ist) nehme ich aber eher das was am besten passt, also am komfortabelsten ist.


----------



## timbeau (6. Jan 2011)

Was ist denn Komplitätstheorie? 

Wichtig sind hier die Landau-Symbole bzw deren Nutzung. Was will ich in meinem Algorithmus machen und welche Laufzeit haben diese Operationen auf den verschiedenen ADTs.


----------



## fastjack (6. Jan 2011)

mmm @Icke_ schreibt ja gar nicht mehr...


----------



## Icke_ (7. Jan 2011)

maki hat gesagt.:


> @Icke_
> Standard Collections sind nicht syncronisiert, aber syncronisiert ist eben genau das Gegenteil von Nebenläufig.
> Magst vielleicht in Zukunft über Dinge schreiben die du kennst, dann vielleicht gerne auch weniger



Den Tipp kann ich nur zurück geben. Das Gegenteil von synchronisiert ist unsynchronisiert, das Gegenteil von nebenläufig ist sequentiell (oder nacheinander). Eine synchronisierte Liste macht keinen Sinn, wenn Du keine Nebenläufigkeit hast, denn es gibt keinen konkurrierenden (zeitgleichen) Zugriffe auf eine Ressource. 

Was also willst Du hier sagen? Ich habe darauf hingewiesen, dass syncronized threadsafe impliziert. Aber das interessiert mich doch nur bei konkurrierenden Theads (und bestimmten Operationen auf bestimmten Datenstrukturen, bei denen es eben zu Problemen durch die "Gleichzeitigkeit" kommen kann). 

Syncronized vermeidet auch keinesfalls die Nebenläufigkeit, allein die Auswirkungen werden geändert. Syncronized sorgt dafür, dass vor ein Synchronisationmonitor verwendet wird, bei dem sichergestellt ist, dass nur ein Thread diesen "belegen" kann. Vor dem betreten einer Methode wird eben sichergestellt, dass der Aufrufer diesen Monitor belegt oder wenn dieser bereits belegt ist auf die Freigabe wartet. Selbst wenn jetzt also ein zweiter (nebenläufiger!) Thread eine synchronisierte Methode betreten möchte, die bereits ausgeführt wird, dann haben wir echte Nebenläufigkeit. Denn während der eine Thread wartet und hierfür sogar schlafen gelegt werden kann, wird der andere Thread die Ausführung der Methode weiterführen. Was also genau hat sich an der Nebenläufigkeit durch die Synchronisation geändert? 

Danke also für diesen Kommentar...


----------



## fastjack (7. Jan 2011)

Naja, sagen wir mal das Gegenteil von synchron ist asynchron.



> Ich habe darauf hingewiesen, dass syncronized threadsafe impliziert



das stimmt leider auch nicht, Du meinst bestimmt "immutability impliziert thread-safety", das wäre korrekt.


----------



## Icke_ (7. Jan 2011)

fastjack hat gesagt.:


> Naja, sagen wir mal das Gegenteil von synchron ist asynchron.


Sorry, hast Du natürlich recht, das Wort ist mir glatt entfallen, peinlich!



fastjack hat gesagt.:


> das stimmt leider auch nicht, Du meinst bestimmt "immutability impliziert thread-safety", das wäre korrekt.


Nein, das meine ich nicht. Sicher impliziert immutability thread-safety und wenn ich jetzt rein funktional programmiere (und Monaden außen vor lasse) arbeite ich auch thread-safe ;-) 

Wenn wir die Formulierung jetzt auf die Goldwaage legen wollen, dann klar, das Wort syncronized impliziert keine thread-safety. Die korrekte Verwendung davon in einer Klasse tut dies für Exemplare der Klasse schon. Dabei muss natürlich korrekt und vollständig, im Kontext des gleichen Synchronisationsobjekts eine Sperrung erfolgen.

Natürlich kann ich auch auf andere Art eine Anwendung thread-safe bekommen, aber Exemplare einer Klasse, in welcher jede Methode syncronized markiert ist sind thread-safe. Es wäre allerdings nicht für jede Klasse sinnvoll jede Methode auf diese Art zu synchronisieren, da es a) vielleicht völlig unnötig ist und b) man vielleicht auch verschiedene Synchronisationsmonitore verwenden sollte um das Laufzeitverhalten für verschiedene Anwendungsfälle zu verbessern. 
Aber nochmal, die Synchronisation erfolgt um thread-safety zu erreichen und tut dies auch. Natürlich kann ich jetzt sagen, dass ich die Ressource public deklarieren und von außen einen konkurrierenden Zugriff ermöglichen könnte, so dann wäre dieser nicht thread-safe oder ich lasse das synchronized für mindestens eine Methode aus, die auf die Resource zugreift oder natürlich kann ich einen Synchronisationmonitor an ein Objekt binden und in einem statischen Kontext verwenden. Sehen wir also von konstruierter Fehlbenutzung ab (wird können ja wohl GMV annehmen), dann sehe ich nicht was synchronized für einen anderen Zweck hat als thread-safety zu erreichen (natürlich nur in korrekter Benutzung).


----------



## nrg (7. Jan 2011)

also ich hab mir nichtmal 50% von deinen Romanen durchgelesen und genau das ist wahrscheinlich auch die indirekte Mitteilung meiner Vorposter . Wenn wir uns in irgendwas tiefer einlesen wollen, gibt es dazu genug Fachliteratur im Web. Das einzige was der TO hier wollte ist doch eine kurze Zusammenfassung. Den Rahmen sprengst du aber irgendwie für mein Empfinden und das ist jetzt nicht falsch zu verstehen  (edit: und das ist auch - wie schon gesagt - imho der Grund, warum Aussagen "auf die Goldwaage gelegt" werden).


----------



## F.S.WhiTeY (7. Jan 2011)

Mal zu was ist schneller:

Array Vergrößern:

neues array anlegen O(1)
Array Kopieren O(n)
Array Sortieren:
(QuickSort standart Java) O(n*log(n) )

JAVA API:


> public static void sort(long[] a)
> 
> Sorts the specified array of longs into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.



Collection Vergrößern:

O(1), einfach anhängen
Sortieren: (Java Merge Sort) O( n^2 log(n))



> The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n^2 log(n) performance that would result from attempting to sort a linked list in place.



Und der Rest ist auch in der API nachzulesen... einfügen ist bei TreeMaps z.B. Aufwendiger ( O(log(N))  )

Fragen die man sich stellen sollte:

Wie groß ist die Datenmenge die ich verwalten muss ? 

bei großen daten ist Konstanter aufwand nich so gut... Potenzen an dem n sind immer schlecht.

Bei kleinen Datenmengen ist konstanter Aufwand ne feine sache. 

Wie und vorallem wie offt muss ich auf eine Ressource zugreifen ?

Müssen die Ressourcen geordnet sein?

und noch so einiges mehr....


----------



## maki (8. Jan 2011)

Icke_ hat gesagt.:


> Den Tipp kann ich nur zurück geben. Das Gegenteil von synchronisiert ist unsynchronisiert, das Gegenteil von nebenläufig ist sequentiell (oder nacheinander). Eine synchronisierte Liste macht keinen Sinn, wenn Du keine Nebenläufigkeit hast, denn es gibt keinen konkurrierenden (zeitgleichen) Zugriffe auf eine Ressource.
> 
> Was also willst Du hier sagen? Ich habe darauf hingewiesen, dass syncronized threadsafe impliziert. Aber das interessiert mich doch nur bei konkurrierenden Theads (und bestimmten Operationen auf bestimmten Datenstrukturen, bei denen es eben zu Problemen durch die "Gleichzeitigkeit" kommen kann).
> 
> ...


Zu sagen das "nebenläufiges Warten" wirklich nebenläufig wäre ist ein Widerspruch.

Synchronisiert ist eben nicht nebenläufig sondern das sequenzieren von Threads, hast du ja selber beschrieben.

Worauf ich hinaus möchte:
Es gibt neben den synchronisierten Collections die eben darauf beruhen dass Threads sequenziert werden und den unsynkronisierten Collections gibt es auch welche die für Nebenläufigkeit ausgelegt sind im java.util.concurrent Package, einfach mal nachsehen, da werden u.a. sog. "Skiplists" eingesetzt, diese basieren auf wartefreien Algorythmen, dass sind wirklich nebenläufige Collections.

Es gibt es einen unterschied zwischen Nebenläufig und synchronisiert, Threadsafe git es in mind. 2 Varianten, aber nebenläufig (engl. "concurrent") ist nicht synchronisiert.

Dazu kommt dass alle sychronisierten Collections (zB. durch java.util.Collections) nochmals eine externe synchronisation bei Nutzung des Iterators benötigen, sonst fliegt bald eine ConcurrentModificationException.


----------



## Icke_ (8. Jan 2011)

maki hat gesagt.:


> Zu sagen das "nebenläufiges Warten" wirklich nebenläufig wäre ist ein Widerspruch.


Der worin liegt? Ein Prozess kann neben einem anderen ausgeführt werden (ist damit nebenläufig) und kann warten (z.B. weil ein Sleep das verlangt). Trotzdem sind die beiden Prozesse nebenläufig. Nebenläufigkeit sagt gerade nicht, dass immer etwas läuft (auch wenn das im Namen steckt).



maki hat gesagt.:


> Es gibt neben den synchronisierten Collections die eben darauf beruhen dass Threads sequenziert werden


Sorry, aber die Collection Klassen haben nichts, aber wirklich gar nichts mit der Nebenläufigkeit zu tun. Das Verhalten von nebenläufigen Prozessen (leichtgewichtig Threads) wird hier gesteuert oder auch nicht, aber ich kann eine ArrayList genauso in einem nebenläufigen Programm einsetzen wie einen Vektor oder eine Skiplist. Die Nebenläufigkeit interessiert das nicht im geringsten. 
Die ist allein durch die Verwendung eines einzelnen oder mehrerer Prozesse definiert (ob implizit oder explizit ist dann noch ein anderes Thema). 



maki hat gesagt.:


> und den unsynkronisierten Collections gibt es auch welche die für Nebenläufigkeit ausgelegt sind im java.util.concurrent Package, einfach mal nachsehen



Nehmen wir hier doch die Beschreibung der Klasse SyncronousQueue, da lese ich:


			
				Java API hat gesagt.:
			
		

> A blocking queue in which each insert operation must wait for a corresponding remove operation by another thread, and vice versa.


Na nu, da wartet ein Thread? Im nebenläufigen Paket? Ist die Klasse falsch einsortiert, mein englisch zu schlecht oder wo liegt jetzt der Fehler?!



			
				maki hat gesagt.:
			
		

> da werden u.a. sog. "Skiplists" eingesetzt, diese basieren auf wartefreien Algorythmen, dass sind wirklich nebenläufige Collections.


Eine Skiplist sehe ich auch nicht, aber Varianten des Map und Set Interface, keine für eine Liste.



			
				maki hat gesagt.:
			
		

> Es gibt es einen unterschied zwischen Nebenläufig und synchronisiert



Dass hatten wir auch schon, sieh mal in Deinem Beitrag weiter oben, Nebenläufigkeit sagt etwas über mehrere Threads aus, die gleichzeitig laufen, synchronisiert hingegen hat was mit der Steuerung des Zugriffs zu tun. Das wurde aber schon gesagt, natürlich kann man auch in einem nicht-nebenläufigen Programm synchronisieren (kostet unnötig Zeit, aber ist möglich, wurde nie anders behauptet). 



			
				maki hat gesagt.:
			
		

> Threadsafe git es in mind. 2 Varianten, aber nebenläufig (engl. "concurrent") ist nicht synchronisiert.


Was ist genau Dein Problem? Ich sehe überhaupt nicht worauf Du hier noch hinaus willst. Bier gibt es in Dunkel und Hell aber concurrent heißt auf Deutsch nebenläufig. Ob es Threadsafe in 2 oder 5 Varianten gibt ist doch völlig unerheblich für den Rest der Aussage. Nebenläufigkeit ist nicht Synchronisation, ja, stimmt. Aber wer hat das behauptet? Du sagst doch selbst:



			
				maki hat gesagt.:
			
		

> Synchronisiert ist eben nicht nebenläufig sondern das sequenzieren von Threads, hast du ja selber beschrieben.





			
				maki hat gesagt.:
			
		

> Dazu kommt dass alle sychronisierten Collections (zB. durch java.util.Collections) nochmals eine externe synchronisation bei Nutzung des Iterators benötigen, sonst fliegt bald eine ConcurrentModificationException.



Und hier wird es mir langsam auch zu blöd. Ich habe gesagt und sage auch weiterhin, dass die Zugriffe auf die Klasse Vector nebenläufig unproblematisch sind. Ein Iterator ist kein Vector. Die Klasse X, die einen Vector verwendet ist auch nicht thread-safe, nur weil ein Element dadrin thread-safe ist. Das ist klar und Du hast Recht. 
Da ich es offensichtlich behauptet habe (bitte reiche die Stelle nach an der das geschehen ist, ich kenne sie nicht) möchte ich natürlich ergänzen, dass zwar der Aufruf der Methode firstElement() oder lastElement() thread-safe ist, aber Aufrufe der Methoden des zurückgelieferten Elements sind es nicht automatisch. Achtung, das kann auch für andere Methoden gelten, zum Beispiel kann man sich ein Array zurückgeben lassen und auch dieses ist ggf. nicht thread-safe. Und hey, maki sagte dass die Klassen aus dem Package java.util.concurrent Nebenläufig sein, aber Achtung, auch hier sind nicht alle Rückgabewerte thread-safe sondern nur die Aufrufe der Methoden der Klassen in dem Package. 

Sorry, mir wird das langsam einfach zu blöd. Wenn Du hier sagst, dass Nebenläufigkeit nicht synchronisiert heißt, dann stimme ich Dir zu und habe nie das Gegenteil behauptet. Wenn Du sagst, dass Synchronisation für Objekte Sinn macht, auf welche nicht nebenläufig zugegriffen werden, dann hätten wir unterschiedliche Ansichten. Um es noch mal klar zu sagen, es ist möglich, aber nicht sinnvoll, da man sehr teure Operationen für die Synchronisation bemüht ohne dass sie einen Nutzen hätten. 
Wenn Du sagst thread-safe ist nicht gleich zu setzen mit Synchronisation oder Nebenläufigkeit, dann stimme ich Dir zu, denn es mit thread-safe wird nur eine Eigenschaft bezeichnet, die eben sagt dass nebenläufige Zugriffe ohne weitere Synchronisation problemfrei möglich sind. 
Beim Besten willen heißt Nebenläufigkeit aber nicht dass zwei Threads immer parallel laufen und sich nicht gegenseitig blockieren dürfen. Und nur weil ein Thread auf die Freigabe einer Ressource durch einen anderen Thread wartet ist die Nebenläufigkeit nicht aufgehoben (sonst erklär mir mal Deadlocks...). 

Obwohl ich das Gefühl habe, dass wir schon mehr als OT sind, eine Frage die ich wirklich hätte (die ist dann auch weniger OT), Du sagst ja:


			
				maki hat gesagt.:
			
		

> da werden u.a. sog. "Skiplists" eingesetzt, diese basieren auf wartefreien Algorythmen, dass sind wirklich nebenläufige Collections.


Ich hab jetzt nichts dazu gefunden, aber kannst Du mir hier bitte sagen, wie die Algorithmen da wartefrei arbeiten? Ganz ehrlich, würde mich interessieren! Ich kenne hier einfach keinen Ansatz der funktionieren würde, der komplett ohne blockierendes Warten auskommt. Oder arbeiten die nur asynchron, kehren also ggf. sofort zurück, während intern immer noch blockierend gewartet wird?


----------



## maki (8. Jan 2011)

> Der worin liegt? Ein Prozess kann neben einem anderen ausgeführt werden (ist damit nebenläufig) und kann warten (z.B. weil ein Sleep das verlangt). Trotzdem sind die beiden Prozesse nebenläufig. Nebenläufigkeit sagt gerade nicht, dass immer etwas läuft (auch wenn das im Namen steckt).


Der Unterschied ist doch offensichtlich: Echte Nebenläufigkeit vs. Sequenzierung



> Sorry, aber die Collection Klassen haben nichts, aber wirklich gar nichts mit der Nebenläufigkeit zu tun. Das Verhalten von nebenläufigen Prozessen (leichtgewichtig Threads) wird hier gesteuert oder auch nicht, aber ich kann eine ArrayList genauso in einem nebenläufigen Programm einsetzen wie einen Vektor oder eine Skiplist. Die Nebenläufigkeit interessiert das nicht im geringsten.
> Die ist allein durch die Verwendung eines einzelnen oder mehrerer Prozesse definiert (ob implizit oder explizit ist dann noch ein anderes Thema).


Eben nicht, es gibt Collections die wirklich nebenläufig funktionieren (im java.util.concurrent Package), da können mehrere Threads gleichzeitig hinzufügen/entfernen/iterieren, kein Problem. 
Dann gibt es Collections die nicht von mehreren Threads genutzt werden dürfen, die "Standard"collections wie ArrayList und HashSet.
Dann gibt es Collections die synchronisiert sind, also bei denen die Zugriffe der einzelnen Threads sequenziert werden, Vector etc., aber selbst bei diesen muss nochmals extern synchronisiert werden wenn während der Iteration die Collection ändert (entfernen/hinzufügen).

Ein Vector ist nicht Nebenläufig, sondern synchronisiert, und da gibt es eben einen Unterschied.



> Nehmen wir hier doch die Beschreibung der Klasse SyncronousQueue, da lese ich:


Richtig, hast dir auch die falsche ausgesucht *g*
ConcurrentSkipListMap, ConcurrentSkipListSet, ConcurrentLinkedQueue etc. eben, probier doch mal diese aus 



> Eine Skiplist sehe ich auch nicht, aber Varianten des Map und Set Interface, keine für eine Liste.


Keiner hat behauptet dass diese das Listinterface implementieren, sie basieren auf einer sog. "SkipList"
Denke dass du hier die Neuerungen in Java 6 verpasst hast, seitdem gibt es eben nicht nur "nicht threadssafe" und "threadsafe weil synchronisiert", sondern eben auch "threadsafe weil Nebenläufig-(concurrent)fähig"



> Und hier wird es mir langsam auch zu blöd. Ich habe gesagt und sage auch weiterhin, dass die Zugriffe auf die Klasse Vector nebenläufig unproblematisch sind. Ein Iterator ist kein Vector. Die Klasse X, die einen Vector verwendet ist auch nicht thread-safe, nur weil ein Element dadrin thread-safe ist. Das ist klar und Du hast Recht.


Jede Collection bietet einen Iterator, bei einem Vector zB. ist dieser aber nicht synchronisiert, also nicht Threadsafe, obwohl Vector an sich syncronisiert ist.



> Beim Besten willen heißt Nebenläufigkeit aber nicht dass zwei Threads immer parallel laufen und sich nicht gegenseitig blockieren dürfen. Und nur weil ein Thread auf die Freigabe einer Ressource durch einen anderen Thread wartet ist die Nebenläufigkeit nicht aufgehoben (sonst erklär mir mal Deadlocks...).


Nebenläufig heisst eben dass 2 oder mehrere Threads gleichzeitig arbeiten, wenn einer die anderen blockiert, arbeitet eben nur ein Thread. Ziemlich blöd wenn du einen Quadcore hast bei dem 3 Cores nur warten 



> Ich hab jetzt nichts dazu gefunden, aber kannst Du mir hier bitte sagen, wie die Algorithmen da wartefrei arbeiten? Ganz ehrlich, würde mich interessieren! Ich kenne hier einfach keinen Ansatz der funktionieren würde, der komplett ohne blockierendes Warten auskommt. Oder arbeiten die nur asynchron, kehren also ggf. sofort zurück, während intern immer noch blockierend gewartet wird?


Steht in der JavaDoc zu den Concurrent Collections, zB ConcurrentLinkedQueue:
ConcurrentLinkedQueue (Java 2 Platform SE 5.0)


> ...
> This implementation employs an efficient "wait-free" algorithm based on one described in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.
> ...


Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms


----------



## Icke_ (8. Jan 2011)

maki hat gesagt.:


> Der Unterschied ist doch offensichtlich: Echte Nebenläufigkeit vs. Sequenzierung


Sequenzierung hast Du in der Biologie, ich denke Du meinst Serialisierung  Wenn etwas offensichtlich ist, dann würde ich nicht fragen, aber gut.



maki hat gesagt.:


> Ein Vector ist nicht Nebenläufig, sondern synchronisiert, und da gibt es eben einen Unterschied.



50% richtig, Nebenläufig und Synchronisiert (das werde ich nicht nochmal wiederholen) ist was unterschiedliches. Natürlich ist auch eine Klasse nicht nebenläufig (wie auch?!). Nebenläufig ist eine Anwendung, wenn hier mehrere Threads arbeiten. Synchronisation dient (wie zig mal gesagt) zur Steuerung der nebenläufigen Zugriffe. Ist schön dass wir uns einig sind, dass das Unterschiedliche Dinge sind. 



maki hat gesagt.:


> Denke dass du hier die Neuerungen in Java 6 verpasst hast, seitdem gibt es eben nicht nur "nicht threadssafe" und "threadsafe weil synchronisiert", sondern eben auch "threadsafe weil Nebenläufig-(concurrent)fähig"


Ja, ich würde davon ausgehen, dass die viele verpasst haben. 



maki hat gesagt.:


> Nebenläufig heisst eben dass 2 oder mehrere Threads gleichzeitig arbeiten, wenn einer die anderen blockiert, arbeitet eben nur ein Thread. Ziemlich blöd wenn du einen Quadcore hast bei dem 3 Cores nur warten


Ich lasse außen vor, dass Du hier eine Milchmädchenrechnung aufmachst und 4 Threads nicht auf 4 CPU Kerne verteilt werden oder dies müssten um nebenläufig zu laufen (selbst eine Single Core CPU wird nebenläufiges Verhalten emulieren, dass zu Problemen führen kann). 

Deine Definition von Nebenläufigkeit ist einfach falsch. Nach Wikipedia (such gerne auch eine andere) heißt Nebenläufig:


			
				Wikipedia hat gesagt.:
			
		

> Nebenläufigkeit (engl. concurrency) liegt vor, wenn mehrere Ereignisse in keiner kausalen Beziehung zueinander stehen, sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursache des anderen ist. Oder anders ausgedrückt: Aktionen können nebenläufig ausgeführt werden (sie sind parallelisierbar), wenn keine das Resultat der anderen benötigt.


Wo finde ich jetzt, dass irgendwas laufen muss? Gehen wir zu Oracle und schauen uns an, was die zum Thema Concurrency sagen, explizit zum Schlafen legen:


			
				Oracle hat gesagt.:
			
		

> Thread.sleep causes the current thread to suspend execution for a specified period. This is an efficient means of making processor time available to the other threads of an application or other applications that might be running on a computer system.


Das findet sich unter Concurrency! Explizit wird hier darauf verwiesen, dass es sogar gründe gibt einen (nebenläufigen/concurrent) Thread zu pausieren (genauer seine Ausführung). 

Das was Du meinst nennt man blocking bzw. non-blocking, bei Datenbanksystemen kennst Du vielleicht Pesimistic Locks und Optimistic Locks. Synchronisation ist einfach ein Pessimistic lock. Du gehst davon aus, dass etwas passieren wird und holst Dir deshalb vorab eine Sperre die sicherstellt, dass keine gleichzeitigen Zugriffe erfolgen. 
Der Algorithmus in dem Paper, dass Du verlinkt hast verwendet einfach einen Optimistic lock. Man geht davon aus, dass wahrscheinlich nichts passiert und prüft bei Abschluss der Operation ob das Objekt zwischenzeitlich verändert wurde (z.B. durch Vergleich des letzten Änderungsdatums). Kam es zu einer zwischenzeitlichen Änderung verwirft man die eigene und versucht es nochmal. 
In Deinem Beispiel würde es so im worst-case dazu kommen, dass drei CPUs in einer Schleife festhängen und wieder und wieder ihre Änderungen ausführen und rückgängig machen.

Optimistic locks bieten sich vor allem da an, wo viel gelesen und selten geschrieben wird. Eine Queue ist geradezu predestiniert, weil man hier die Enden von einander trennen kann. Gelesen wird an einem Ende, geschrieben am anderen. Der Thread der das Dinge leert steht also nicht wirklich in Konkurrenz zum Schreibenden (außer die Queue ist fast leer). 
Natürlich kostet auch das Verwerfen von Änderungen und das Durchlaufen der Schleife Zeit, irgendwann ist die teurer als ein Pessimistic lock (hier sollte man den Anwendungsfall prüfen). 

Nichts desto trotz hat sich an dem Begriff der Nebenläufigkeit nichts geändert. Java war schon in der 1.4 geeignet nebenläufige Programme zu schreiben (auch davor) und bietet (unter anderem mit der Synchronisation) Möglichkeiten konkurriende Zugriffe auf Ressourcen zu steuern und thread-safety sicherzustellen. Ob ein Thread irgendwann mal warten muss oder nicht hat nichts mit der Nebenläufigkeit einer Anwendung zu tun.


----------



## Herr K. (8. Jan 2011)

maki hat gesagt.:


> Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms



Nebenbei findest Du im Two-Lock Verfahren (z.B. in der Abbildung 2 auf Seite 5) auch Locks, rate mal wie man sowas in Java implementieren würde ;-)


----------



## maki (8. Jan 2011)

> 50% richtig, Nebenläufig und Synchronisiert (das werde ich nicht nochmal wiederholen) ist was unterschiedliches.


Dann sind wir uns ja (jetzt) einig, hatte sich bei dir noch anders angehört:


> Das Gegenteil von synchronisiert ist unsynchronisiert, das Gegenteil von nebenläufig ist sequentiell (oder nacheinander). Eine synchronisierte Liste macht keinen Sinn, wenn Du keine Nebenläufigkeit hast, denn es gibt keinen konkurrierenden (zeitgleichen) Zugriffe auf eine Ressource.


Synchronisation führt zur eben Serialisierung der Threads.
Wie hattest du eigentlich das "sequentiell" gemeint?
Etwa falsch??  


> Sequenzierung hast Du in der Biologie, ich denke Du meinst Serialisierung Wenn etwas offensichtlich ist, dann würde ich nicht fragen, aber gut.


"Offensichtlich" bin ich nicht der erste bzw. einzige der diesen "Fehler" begangen hatte...



> Ja, ich würde davon ausgehen, dass die viele verpasst haben.


Eben, und seit dem gibt es nunmal den Unterschied zwischen den Collections, die sich nebenläufig nutzen lassen und solchen, die eben "nur" synchronisiert nutzbar sind.



> Ich lasse außen vor, dass Du hier eine Milchmädchenrechnung aufmachst und 4 Threads nicht auf 4 CPU Kerne verteilt werden oder dies müssten um nebenläufig zu laufen (selbst eine Single Core CPU wird nebenläufiges Verhalten emulieren, dass zu Problemen führen kann).


Die Vereinfachung diente dazu den Unterschied klarzustellen, das Prinzip sollte klar sein.



> Deine Definition von Nebenläufigkeit ist einfach falsch...


Ach wirklich, dann sehen wir uns doch mal deine Definition an:


> Syncronized vermeidet auch keinesfalls die Nebenläufigkeit, allein die Auswirkungen werden geändert.


Soso, jetzt nochmals dein Wikipedia zitat:


> Nebenläufigkeit (engl. concurrency) liegt vor, wenn mehrere Ereignisse in keiner kausalen Beziehung zueinander stehen, sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursache des anderen ist. Oder anders ausgedrückt: Aktionen können nebenläufig ausgeführt werden (sie sind parallelisierbar), wenn keine das Resultat der anderen benötigt.


Synchronized macht eben genau das: Verhindert das Dinge parallel (nebenläufig) abgearbeitet werden.

Was du mit deinem "Optimistic Locks" Beispiel zeigen willst bleibt mir schleierhaft, es soll ja gerade nichts "gelockt" werden.



> Optimistic locks bieten sich vor allem da an, wo viel gelesen und selten geschrieben wird. Eine Queue ist geradezu predestiniert, weil man hier die Enden von einander trennen kann. Gelesen wird an einem Ende, geschrieben am anderen. Der Thread der das Dinge leert steht also nicht wirklich in Konkurrenz zum Schreibenden (außer die Queue ist fast leer).
> Natürlich kostet auch das Verwerfen von Änderungen und das Durchlaufen der Schleife Zeit, irgendwann ist die teurer als ein Pessimistic lock (hier sollte man den Anwendungsfall prüfen).


Den Anwendungsfalls muss man immer prüfen, aber synchronisation ist auch teuer was die Rechenzeit betrifft, die Concurrent Collections "kosten" zwar auch, aber eher Speicher als Laufzeit.



Herr K. hat gesagt.:


> Nebenbei findest Du im Two-Lock Verfahren (z.B. in der Abbildung 2 auf Seite 5) auch Locks, rate mal wie man sowas in Java implementieren würde ;-)


Ich tippe mal auf Locks, da diese feingranularer zu steuern sind als es das synchronized Schlüsselwort es erlaubt.
Aber das Thema waren nicht die Two-Locks Verfahren


----------



## fastjack (8. Jan 2011)

Ich denke Icke_ und Herr K. sind Resultate der clone()-Methode 

Zur Aufklärung: Nebenläufig ist eine sprachliche Neuschöpfung der letzten Jahre und heißt normalerweise Nichtsequentiell. Das Gegenteil davon heißt sequentiell.


----------



## icke_ (8. Jan 2011)

maki hat gesagt.:


> Wie hattest du eigentlich das "sequentiell" gemeint?



Sequentiell liegt bei single threads vor. Sequenitell hat nicht mit Sequenzierung zu tun sondern mit Sequentialisierung. 


maki hat gesagt.:


> Etwa falsch??


Ergo nein  

Um es aber einmal klar zu machen: 

Sequentiell heißt echt hintereinander in einer gegebenen Reihenfolge. Hier kann man von einer Kausalitätskette ausgehen, bei der ein Ereignis eine feste Reihenfolge von Schritten nach sich zieht.
Nicht-Sequentiell (auch nebenläufig) hatten wir schon, hier liegt keine Ordnung für solche Ereignisse vor, die nicht von einander abnhängen.
Serialisiert nennt man nun die nicht-sequentielle Ausführung, bei der das Ergebnis das gleiche wäre, als ob die Ausführung sequentiell erfolgt wäre. Das heißt die Ausführung kann weiterhin nebenläufig erfolgen, solange nur das Endergebnis dem endspricht, was beim nacheinander ausführen passiert wäre. 
 


maki hat gesagt.:


> "Offensichtlich" bin ich nicht der erste bzw. einzige der diesen "Fehler" begangen hatte...


Hm, in diesem Thread schon, aber bestimmt haben schon anderen den Fehler begangen...



maki hat gesagt.:


> Synchronized macht eben genau das: Verhindert das Dinge parallel (nebenläufig) abgearbeitet werden.


Überhaupt nicht. Es serialisiert die Ausführung, wenn der gleiche Synchronisationsmonitor verwendet wird. Zwei Ereignisse mit unterschiedlicher Ursache können parallel abgearbeitet werden, die Nebenläufigkeit ist eine Eigenschaft der Anwendung, synchronized sind nur Blöcke in der Programmausführung. Alle Teile der Anwendung mit unterschiedlichen oder keinem Synchronsiationsmonitor können gleichzeitig betreten werden. 
Die Unterscheidung ob Dein Programm sequentiell oder nebenläufig (auch serialisiert) läuft kannst Du daran festmachen ob Du nur den Hauptthread hast (hier ist keine Gleichzeitigkeit möglich) oder mindestens zwei Threads verwendet werden. 



maki hat gesagt.:


> Was du mit deinem "Optimistic Locks" Beispiel zeigen willst bleibt mir schleierhaft, es soll ja gerade nichts "gelockt" werden.


Man nennt die Dinger nur Optimistic Lock (ich hab den Namen ja nun nicht erfunden). Nenn es meinetwegen Optimistic Concurrency Control und Pessimistic Concurrency Control, wenn Dir die Namen generischer/lieber sind (findet man denke ich beides).



maki hat gesagt.:


> Den Anwendungsfalls muss man immer prüfen, aber synchronisation ist auch teuer was die Rechenzeit betrifft, die Concurrent Collections "kosten" zwar auch, aber eher Speicher als Laufzeit.


Kommt auf den Anwendungsfall an. Bei sehr vielen Gleichzeitigen Änderungen dreht sich das Laufzeitverhalten. Beide (optimischtische und pessimistische Verfahren) haben ihre Vor- und Nachteile.


----------



## fastjack (8. Jan 2011)

Icke_ hat gesagt.:
			
		

> Natürlich ist auch eine Klasse nicht nebenläufig (wie auch?!)



Ganze einfach: Sie erweitert Thread oder benutzt Threads...


----------



## F.S.WhiTeY (9. Jan 2011)

> Nebenläufigkeit (engl. concurrency) liegt vor, wenn mehrere Ereignisse  in keiner kausalen Beziehung zueinander stehen, sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursache des anderen ist. Oder anders ausgedrückt: Aktionen können nebenläufig ausgeführt werden (sie sind parallelisierbar), wenn keine das Resultat der anderen benötigt. Eine Modellierungssprache, die diese Abhängigkeiten sehr gut wiedergibt, sind Petri-Netze.




Ich kann 5 mal den selbe Algorithmus im selben Programm ausführen ohne das sich die 5 Threads gegenseitig beeinfluss... der eine Thread wartet also nicht auf Ergebnisse des anderen. Dann ist es Nebenläufig.



> Serialisierung ist eine Abbildung von Objekten auf eine externe sequenzielle Darstellungsform in der Informatik. Serialisierung kann für das Erreichen von Persistenz für ein Objekt verwendet werden, aber auch in verteilten Softwaresystemen spielt Serialisierung eine bedeutende Rolle.
> 
> Übliche Speichermedien sind nur in der Lage, Datenströme zu speichern. Um Persistenz für ein Objekt zu erreichen, kann es serialisiert werden. Hier wird der komplette Zustand des Objektes, inklusive aller referenzierten Objekte, in einen Datenstrom umgewandelt, der anschließend auf ein Speichermedium geschrieben wird.
> 
> ...




Das beides aus Wikipedia... und wer nun sagt wiki ist unzuverlässig weil da jeder ran darf ... GUT :



> Serialisierung beschreibt den Vorgang des Konvertierens des Zustands eines Objekts in eine Form, die erhalten oder transportiert werden kann. Das Gegenstück zur Serialisierung ist die Deserialisierung, bei der ein Stream in ein Objekt konvertiert wird. Anhand dieser beiden Vorgänge können Daten problemlos gespeichert und übertragen werden.



Zitat Serialisierung


Haben wir es jetzt ?


----------



## sklafdsljkjf (9. Jan 2011)

ArrayList, Vector und Array sind das gleiche. ArrayList und Vector haben neben gleichen Grundprinzip aber die Möglichkeit, zu vergrößern. Das resize-Verhalten zwischen ArrayList und Vector ist aber unterschiedlich. Man kann sich darüber streiten, welches besser ist. Mit neueren Klassen kann ArrayList (so wie Vector bereits ist) Thread-sicher gemacht werden. Wenn die Elemente fest stehen, ist ein Array klar schneller. Leichte Abzüge muss man machen, weil ArrayList und Vector nicht mit primitiven Datentypen umgehen.

Wenn die Elemente nicht feststehen oder wenn Elemente nicht bei letzten Index eingefügt oder entfernt werden sollen, sind Listen/dynamische Datenstrukturen schneller.

Am schnellsten biste mit ArrayDeque, wenn die maximale Anzahl Elemente feststeht und als Queue oder Stack eingesetzt wird (kleiner Tipp).


----------



## sklafdsljkjf (9. Jan 2011)

Und ein Kausaler Zusammenhang verschiedener Threads besteht erst dann, wenn die Ausführung des einen mit der Beendigung des anderen einhergeht - nicht wenn eine Teilausführung beider nicht gleichzeitig erfolgen darf.

Thread-sicher heißt zudem nicht das man die Vermeidung solcher gleichzeitiger Ausführungen an bestimmten Stellen vernachlässigen kann.


----------

