Iteration von Listen

[Sebastian G]

Hallo,

ich muss mich gerade zum ersten Mal mit groesseren Listen, deren Inhalt sich staendig aendert (hinzufuegen von Objekten am Ende, entfernen von Objekten irgendwo in der Liste).

Wenn ich das auf meiner bisherigen Suche mit Google richtig verstanden habe unterscheiden sich die LinkedList und ArrayList wie folgt:

Taetigkeit LinkedList ArrayList
einfuegen/loeschen O O
anfuegen/loeschen hinten O(1) O(1)
anfuegen/loeschen vorne O(1) O
Indexzugriff O O(1)
suchen O O

Da ich (wie oben beschrieben) hinten einfuegen und irgendwo loeschen will (ersten beiden Punkte meiner obigen Tabelle) und sich LinkedList und ArrayList hier in der Performance nicht unterscheiden, habe ich mich auf Grund des Vorteils der ArrayList beim Indexzugriff fuer die ArrayList entschieden.

Bisher "laufe" ich durch die Liste mit einer normalen for-Schleife [for(int index = 0, ...)].

Nun zu meinen zwei Fragen.

1. Stimmt die oben genannte Tabelle so?
2. Kann man einen Performancegewinn erzielen, wenn man Iterator oder for(Object elem : list) verwendet? Also z.B. die neue for-Schleife in Kombination mit der LinkedList ist schneller als ... (oder so aehnlich).



Habe bisher noch keine Erfahrungen mit Iterator und der neuen for-Schleife. Im Web habe leider nur gefunden, dass das eine besser als das andere ist, aber nicht warum (Performance, Stil, Sicherheit, ...).


Vielen Dank fuer Eure Muehe.


Gruss
Sebastian

 

[Dunas]

ja die liste stimmt

zu deiner for schleife:
durch das ändern der for-schleife in eine for( object a : liste) erhälst du keinen geschwindigkeits gewinn.
das selbe ist auch bei einem itterator.

wenn du etwas mehr zu der nutzung und zu der größe sagen könntest, könnte man sich das noch mal genauer ansehen und dir weitere tips geben.

lg dunas

 

[Sebastian G]

Danke fuer die schnelle Antwort.

Zu Groesse: 10.000 - einige 100.000
Zur Verwendung: Die Liste enthaelt Objekte, die sich duplizieren und vernichten koennen (oder nix machen). Daher werden staendig hinten an die Liste neue Objekte angehaengt und irgendwo in der Mitte welche geloescht. Mehr macht das Programm nicht. Von Interesse ist die Groesse der List nach n Durchlaeufen (also wie hat sich die Anzahl der Objekte nach n Durchlaeufen vergroessert / verkleinert).

Da die Reihenfolge der Objekte keine Rolle spielt, habe ich gerade ein HashSet ausprobiert. War im Testlauf um ein Faktor 60 schneller als die ArrayList.
Ist das der richtige Ansatz?


Ich habe da noch ein anderes Problem. Ich lasse den oben beschriebenen Prozess m mal ablaufen (also noch eine for-Loop eine Ebene hoeher). Hierbei ist mir aufgefallen, dass sehr viel mehr Arbeitsspeicher verbraucht wird, als wenn ich den oben beschrieben Prozess nur einmal ablaufen lasse (ca. 200 MB gegen 1.4 GB). Ich rufe vor jedem neuen Schleifendurchlauf System.gc() auf, aber das scheint nicht viel zu helfen.
Vielleicht einen Tipp hierzu?


Nochmal Danke fuer die Antwort.


Gruss
Sebastian

 

[zeja]

Ohne zu wissen wie deine Schleife aussieht kann ich zu dem Speicherproblem nicht viel sagen.

Ein for-each verwendet intern übrigens einen Iterator. Ein Iterator ist im falle von ArrayList aber langsamer als ein indizierter Zugriff (zur Zeit... muss nicht für immer und ewig so bleiben).

Schau dir mal die Javolution Collection Klassen an. Die könnten für deine Zwecke noch ein wenig schneller sein: http://javolution.org/

 

[Anime-Otaku]

Die O Liste stimmt so nicht ganz.

Methode|ArrayList | LinkedList
get() | O(1)| O| Da er durchiterieren muss um die Posi zu finden
add() | O(1)O(1)| ein einfaches anhängen
contains()|O|O| durch iterieren
next()|O(1)|O(1)| einfaches durchiterieren
remove(0)|O|O(1)| Eine ArrayList muss neu erstellt werden(zumindest teilweise), bei einer LinkedList müssen nur die Objektnachbarn angepasst werden
iterator.remove|O|O(1)| Beim iteriren muss bei der LinkedList nur die Nachbarn geändert werden

Also wäre in deinem Fall eine LinkedList klar besser.

 

[Dunas]

Die O Liste stimmt so nicht ganz.

Methode|ArrayList | LinkedList
get() | O(1)| O| Da er durchiterieren muss um die Posi zu finden
add() | O(1)O(1)| ein einfaches anhängen
contains()|O|O| durch iterieren
next()|O(1)|O(1)| einfaches durchiterieren
remove(0)|O|O(1)| Eine ArrayList muss neu erstellt werden(zumindest teilweise), bei einer LinkedList müssen nur die Objektnachbarn angepasst werden
iterator.remove|O|O(1)| Beim iteriren muss bei der LinkedList nur die Nachbarn geändert werden

Also wäre in deinem Fall eine LinkedList klar besser.

Bei einer Arraylist wird beim removen des ersten elements nichts neu erstellt. um das erste element in der liste zu löschen werden sicher nur die internen zeiger umgebogen. start zeigt dann nicht mehr auf den index 0 sondern auf index 1.

beim removen mit dem iterator hast du recht. da passt der aufwand nicht wirklich.
das element wird entfernt und alle elemente die danach stehen müssen eine stelle nach vorne kopiert werden.

Da die Reihenfolge der Objekte keine Rolle spielt, habe ich gerade ein HashSet ausprobiert. War im Testlauf um ein Faktor 60 schneller als die ArrayList.
Ist das der richtige Ansatz?

Das kann ich jetzt nicht nachvollziehen.
Wenn du mit einer for(int x = 0; x < liste.sice; x++) über die ArrayListe gehst, solltest du keinen unterschied zwischen der Geschwindigkeit haben.

Ich habe da noch ein anderes Problem. Ich lasse den oben beschriebenen Prozess m mal ablaufen (also noch eine for-Loop eine Ebene hoeher). Hierbei ist mir aufgefallen, dass sehr viel mehr Arbeitsspeicher verbraucht wird, als wenn ich den oben beschrieben Prozess nur einmal ablaufen lasse (ca. 200 MB gegen 1.4 GB). Ich rufe vor jedem neuen Schleifendurchlauf System.gc() auf, aber das scheint nicht viel zu helfen.
Vielleicht einen Tipp hierzu?

verstehe ich das richtig, dass du deine Testobjekte erstellst. deine forschleife drüber rennen lässt, dann alles zerstörst, die testobjekte neu erstellst und wieder die forschleife drüber laufen läst?
sollte das richtig implementiert sein, dürfte kein so großer unterscheid entstehen.

 

[Anime-Otaku]

Bei einer Arraylist wird beim removen des ersten elements nichts neu erstellt. um das erste element in der liste zu löschen werden sicher nur die internen zeiger umgebogen. start zeigt dann nicht mehr auf den index 0 sondern auf index 1.

beim removen mit dem iterator hast du recht. da passt der aufwand nicht wirklich.
das element wird entfernt und alle elemente die danach stehen müssen eine stelle nach vorne kopiert werden.

Auszug aus der API:

* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).

Und das macht er immer. Sieht man auch wenn man sich den Quellcode anschaut. Er kopiert alles was hinter dem Element kommt nach 1 nach vorne, danach wird das letzte Element des Arrays entfernt --> removes(0) ist am langsamsten und removes(size-1) am schnellsten.

(Das Performance Problem hatten wir schon festgestellt, als immer remove(0) auf einer ArrayList ausgeführt wurde)

 

[Dunas]

Auszug aus der API:


Und das macht er immer. Sieht man auch wenn man sich den Quellcode anschaut. Er kopiert alles was hinter dem Element kommt nach 1 nach vorne, danach wird das letzte Element des Arrays entfernt --> removes(0) ist am langsamsten und removes(size-1) am schnellsten.

(Das Performance Problem hatten wir schon festgestellt, als immer remove(0) auf einer ArrayList ausgeführt wurde)

sorry. dann war ich falsch informiert. ja ist klar das dann remove(0) am langsamsten ist.
ich sehe eigentlich keinen nachteil bei meiner version mit den zeigern. dann würde ich mal sagen kacke programmiert ^^

 

[Sebastian G]

Das kann ich jetzt nicht nachvollziehen.
Wenn du mit einer for(int x = 0; x < liste.sice; x++) über die ArrayListe gehst, solltest du keinen unterschied zwischen der Geschwindigkeit haben.

Hier meine Beispiel-Implementierung:

public static void main(String[] args) {
		
		HashSet<Integer> collection = new HashSet<Integer>();
	//	ArrayList<Integer> collection = new ArrayList<Integer>();
		
		for (int index = 0; index < 100000; index++) {
			collection.add(index);
		}
		
		double before = System.currentTimeMillis();
		for (int index = 0; index < 10000; index++) {
			collection.remove(new Integer(index*4));
		}
		double after = System.currentTimeMillis();
		
		System.out.println(after - before);

	}

Wenn ich das Hash-Set benutze kriege ich Zeiten von 8 - 15 mill sec, wenn ich dagegen die ArrayList verwende kriege ich Zeiten von ca. 1800 mill sec. Also die ArrayList ist um einen Faktor 200 langsamer.

verstehe ich das richtig, dass du deine Testobjekte erstellst. deine forschleife drüber rennen lässt, dann alles zerstörst, die testobjekte neu erstellst und wieder die forschleife drüber laufen läst?
sollte das richtig implementiert sein, dürfte kein so großer unterscheid entstehen.

Ja, das verstehst du richtig. Mein Code sieht wie folgt aus:

for(int i = 0; i < m; i++) {
      System.gc();
     //population enthaelt als Klassenvarivable die Collection
     Population population = new Population();
     for (int j = 0; j < n; j++) {
          //in diesem Schritt werden Objekte an die Collection angehaengt bzw. geloescht
          poplation.simulateNextTimeStep();
      }
      //hier wird noch in eine Datei geschrieben (BufferedWriter, flush() wird gerufen)
}

Gruss
Sebastian

 

[Anime-Otaku]

Das System.gc() sagt nicht explizit aus, dass der GC sofort alle alten Referenzen frei gibt. Viel mehr wird dem GC mitgeteilt, seine GC Anstrengen zu erhöhen. Aber genau bin ich da auch noch nicht schlau draus geworden.

http://java.sun.com/javase/6/docs/api/java/lang/System.html#gc()

Beim HashSet muss dir klar sein, dass der Hash-Wert deines Objektes als Key verwendet wird. Und das dieser Key eindeutig ist in deinem Set. Daher überschreibst du die Werte, wenn der Hash Wert gleich ist.

Der Hash-Wert wird durch die hashCode Methode des Objektes erzeugt. Wenn das Objekt keine hashCode Methode hat (wird die von Object verwendet), wird die SpeicherAdresse der Instanz als Hash Wert verwendet.