Unterschied Arrays, Listen, Mengen

Bitte aktiviere JavaScript!
1. Kann ich die 3 Typen miteinander vergleichen?

Array:
- nicht erweiterbar (nur schwer mit Aufwand)
+ schnelle Zugriffszeit -> Aufwand O(1)
+/- ein Element kann mehrmals vorkommen

Listen:
- Aufwand O(n), muss immer komplett durchiterieren
+ kann beliebig erweitert werden
(ist sie doppelt verkettet, hat sie einen geringeren Aufwand, aber immer noch schlechter als Array)
+/- ein Element kann mehrmals vorkommen

Mengen: (Sets)
werden in einer Tabelle gespeichert. (Hash-Tabelle? oder auch andere Tabellen?)
+ ein Element kann nur einmal vorkommen
- fällt mir nichts ein

Falls das so richtig ist, was für Sachen gibt es noch die man miteinander mit denen vergleichen kann?
 
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
Listen:
- Aufwand O(n), muss immer komplett durchiterieren
Aufwand wofür denn? Normalerweise vergleicht man konkrete Datenstrukturen anhand ihrer Speicherplatzkomplexität und der Laufzeitkomplexitäten der auf ihnen definierten Operationen. Üblich sind Operationen wie etwa Einfügen, Entfernen und Suchen. Eine Liste ist allerdings noch keine konkrete Datenstruktur, sondern eine abstrakte Datenstruktur. Man kann Listen auf soooo vielen unterschiedlichen Weisen implementieren (ArrayList, LinkedList, SkipList, ...) und daraus ergeben sich dann die konkreten Speicherplatz- und Laufzeit-Komplexitäten.

Siehe z.B. rechts oben bei:
- https://en.wikipedia.org/wiki/Skip_list
- https://en.wikipedia.org/wiki/Hash_table
 
Ein Array ist normalerweise eine Aneinanderreihung von Objekten im Stack (Java ist hier eine Ausnahme, da liegen die meines Wissens auch im HEAP), während Listen prinzipiell im Heap liegen.
Die Arraygröße ist fest, allerdings kann man ein Array schon vergrößern, meistens indem man das Array in ein neues Array kopiert, z.B. mit System.arraycopy(), siehe https://www.tutorialspoint.com/java/lang/system_arraycopy.htm . Nutzt allerdings beides eig. (fast) keiner - mal abgesehen von der Spieleindustrie, wo du jede ns wegoptimieren willst.

Listen:
"Aufwand O(n), muss immer komplett durchiterieren"
Wie kommst du darauf? Wenn du ein list.get(0) aufrufst, erhälst du das erste Element. Listen sind unter der Haube auch nur Arrays in Java --> müsste wahrscheinlich auch O(1) sein. Lediglich das Iterieren über Listen ist Performance-lastiger, da hier die Verkettung zum Tragen kommt. Auch erzeugt das Iterieren (anscheinend durch den Iterator) mehr GC-Pressure (zumindest ergeben das meine eigenen Messungen), weshalb ich immer ein Array verwende, wenn es denn möglich ist.

Bezüglich Sets:
Nicht ganz. Lediglich HashSet nutzt eine Hash-Tabelle: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
Manche Implementierungen nutzen auch einen Baum: https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

Naja, das wichtigste hast du bereits abgedeckt.
Du könntest dir aber noch die anderen Java Collections anschauen und vergleichen:

Quelle: https://en.wikipedia.org/wiki/Java_collections_framework

EDIT:
@httpdigest war schneller.^^
 
Wenn du einer ArrayList ein paar Elemente hinzufüge und sie dir ausgeben lässt, dann siehst du, dass die Reihenfolge dieselbe ist. Bei einem HashSet hingegen kann keine Aussage über die Reihenfolge gemacht werden. Bei dem Hinzufügen eines Elementes ändert sich die Reihenfolge.
 
Ein Array ist normalerweise eine Aneinanderreihung von Objekten im Stack (Java ist hier eine Ausnahme, da liegen die meines Wissens auch im HEAP), während Listen prinzipiell im Heap liegen.
Das ist weder für Java richtig, noch generell ;)

Der JIT kann sowohl mit Arrays als auch mit Listen machen, was er will, und theoretisch (und zT praktisch) können die nachher auf'm Stack, im Heap oder auch nur in Registern existieren.

Und in allen anderen Sprachen kommt es jeweils auf die Sprache an, wie und wi Listen und Arrays da liegen

Auch erzeugt das Iterieren (anscheinend durch den Iterator) mehr GC-Pressure (zumindest ergeben das meine eigenen Messungen), weshalb ich immer ein Array verwende, wenn es denn möglich ist.
Welche Version, welcher JIT und welcher GC? ;)

Magst du bei Zeiten mal den Benchmark zeigen? Würde mich interessieren...
 
Der JIT kann sowohl mit Arrays als auch mit Listen machen, was er will, und theoretisch (und zT praktisch) können die nachher auf'm Stack, im Heap oder auch nur in Registern existieren
Der JIT ist eher so die letzte Instanz die etwas machen könnte (kein muss). spezifiziert, wo was (wann) wie liegt (in welcher form) ist es schon....

Aber ich betone auch wieder das es wichtig ist alle Grundlagen begriffen zu haben.:mad:
 
Der JIT ist eher so die letzte Instanz die etwas machen könnte (kein muss). spezifiziert, wo was (wann) wie liegt (in welcher form) ist es schon....
Welche Instanzen gibts denn da sonst noch so, außer des JIT, welche entscheiden, wo welcher Speicher alloziert wird?
Wo ist definiert, wo ein lokales Array oder Listen liegen müssen?
 
Mich an der Diskussion beteiligen und den Beitrag von @JuKu (partiell) korrigieren....

Hinaus wollte ich gar nicht. (Dunkel, kalt, nass und windig draußen <- Scherz!)
 
Was ich bei Liste von O(n) meinte war eine verkettete Liste. Da muss ich ja komplett durch iterieren um auf den letzten Eintrag zu kommen. Ist eine ArrayListe auch eine verkettet Liste wenn ich mit get(i) zugreifen kann? Eigentlich doch nicht oder?
 
Was ich bei Liste von O(n) meinte war eine verkettete Liste. Da muss ich ja komplett durch iterieren um auf den letzten Eintrag zu kommen.
Generell ist der Aufwand für einen Zugriff auf ein Element bei verketteten Listen O(n).

Ist eine ArrayListe auch eine verkettet Liste wenn ich mit get(i) zugreifen kann? Eigentlich doch nicht oder?
Nein, eine ArrayList ist keine verkettete Liste, sondern nutzt intern ein Array. Ist aber auch kein Array, sondern eben eine Liste.
Wenn es dir um abstrakte Datentypen geht, solltest du das deshalb aus der Betrachtung rausnehmen.

EDIT: O(1) zum korrekten O(n) geändert
 
Zuletzt bearbeitet:
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben