Schnellster Container

[AED2]

Hallo

ich bin relativ neu in Java und verliere den Überblick über die gesammten Container die es gibt.
Da gibt es Listen und Collections wenn ich das richtig verstanden habe.
Nur wie finde ich den richtigen für mich? Die Javadoc hilft mir überhaupt nicht weiter und Google liefert auf der einen Seite zum Beispiel Ergebnisse wo geschrieben wird eine LinkedList wäre völlig unbrauchbar bspw. und auf der anderen irgendwas von double LinkedLists.

Wie gesagt ich hab keine Ahnung.
Ich möchte eine Schleife ständig hintereinander durchlaufen lassen von Objekten um sie abzurufen.

for(  ) {
     objekt.tuWas();
}

Dabei spielt es keine Rolle in welcher Reihenfolge dies geschieht, hauptsache jedes Objekt kommt 1mal pro Schleifendurchlauf an die Reihe. Das hinzufügen und entfernen von Objekten kommt vor spielt dabei aber eine eher untergeordnete Rolle.

Kennt da jmd. etwas?
Oder wenigstens irgendeine Methode wie ich jetzt/in Zukunft herausfinden kann, was ich brauche?

Gruß
AED2

 

[nillehammer]

Eigentlich ist die Auswahl des richtigen Container-Typs nur von ganz wenigen einfachen Fragen abhängig:
- Soll die Collection Duplikate ausschließen? Wenn ja, dann Set.
- Soll auf die Elemente per Index zugegriffen werden? Wenn ja, dann List.
(- Soll beides gehen? Wenn ja, gibt's leider im Collections-Framework nicht, also 3rd-Party Libs oder selbst bauen)
- Soll ein Key einem Value zugeordnet sein? Wenn ja, dann Map

Wenn mit Hilfe dieser Fragen schon mal der richtige Typ ausgewählt wurde, stellt sich die Frage: "Welche Implementierung?" Da gibt es in der Tat einiges zu schreiben. Aber bei kleineren Collections (Elementanzahl höchstens im vier stelligen Bereich) ist eigentlich jede Implementierung geeignet. Also da einfach die simplen Implementierungen ArrayList, HashSet, HashMap

Wie geht es weiter? Neben den groben Anforderungen, kann es noch Feinheiten geben wie:
- Mein Set soll sortiert sein
- Auch bei einem Set soll beim Iterieren die Reihenfolge der Elemente immer gleich sein
etc. Wenn Du auf ein solches konkretes Problem stößt, schreib es hier.

 

[AED2]

Vielen Dank für die Anleitung
- Nur von was kann ich ausgehen, ist es schneller bei einem HashSet oder bei einer Liste alle Elemente einmal abzufragen?
- Fals Liste shcneller: Bei einer Liste kann man ja auch anscheinend durchiterieren nach der Javadoc, ist dass dann schneller als die normale Variante derren Namen ich nicht kenne?

for( int i = 0; i < al.size(); i++ )

Mir stellt sich halt gerade die Frage ob ich jetzt ein HashSet oder eine ArrayList verwenden soll wie von deiner Anleitung vorgeschlagen.
Ein Objekt "muss nicht" nur einmal in der Liste stehen, das System drumherum sorgt bereits dafür, dass das überhaupt nicht erst passiert, andererseits ist es auch völlig egal ob die Elemente einen Index.
Ich tendiere im Moment zum HashSet da ich mir denke, dass durch das zusätzliche indizieren der Objekte bestimmt rechenzeit vergeht.

Gruß
AED2

 

[maki]

Nach deiner Beschreibung würde ich dir Collection empfehlen.

Du brauchst keine Reihenfolge/Sortierung, keine Wahlfreien Zugriff per Index, Duplikate kann es an sich nicht geben > Collection und gut ist.

 

[AED2]

Danke

 

[bygones]

- Soll auf die Elemente per Index zugegriffen werden? Wenn ja, dann List.

dann viel Spass bei der LinkedList ;-)

indexbasierter Zugriff sollte man nur machen wenn man weiss dass sich hinter der Liste eine Array basierte Loesung befindet

 

[maki]

... oder wenn man weiss, dass die Liste so klein ist und so selten per Index zugegriffen wird, dass es egal ist

 

[faetzminator]

Braucht man doch gar nicht, wenn man immer nur durch alle Elemente will

for( int i = 0; i < al.size(); i++ ) {
    Foo foo = al.get(i);
    // ...
}

Da tuts auch das Iterable-Interface bzw. die enhanced for loop:

for (Foo foo : al) {
   // ...
}

 

[nillehammer]

dann viel Spass bei der LinkedList

indexbasierter Zugriff sollte man nur machen wenn man weiss dass sich hinter der Liste eine Array basierte Loesung befindet

Index-basierter Zugriff ist auch bei der LinkedList möglich. Wenn auch nicht sehr effizient. In dem Teil meines Posts ging es aber auch erst um die Auswahl des richtigen ContainerTyps. Die Auswahl der Implementierung habe ich erst später erklärt.

Und nochmal zur Ursprungsfrage. Da überhaupt keine Anforderungen gestellt sind außer, dass über die Elemente iteriert werden soll, reicht -wie maki schon schrieb- der Typ/Interface Collection oder sogar noch allgemeiner -wie faetzminator schrieb- das Interface Iterable. Aber auch dahinter muss sich eine konkrete Implementierung verbergen. Ich habe mal einen kleinen Test zur Ermittlung der Iterationsgeschwindigkeit geschrieben. Bei kleineren Elementzahlen nehmen sich die Implementierungen nichts. Bei größeren (ab 1Mio) gewinnt die ArrayList. Code zum Ausprobieren:

public class TestApp {

  public static void main(String[] args) throws Exception {

    final int elemCount = 10_000_000;

    final List<Object> objList = new ArrayList<>(elemCount);

    final Set<Object> objSet = new HashSet<>(elemCount);

    for (int i = 0; i < elemCount; i++) {

      final Object element = new Object();

      objList.add(element);

      objSet.add(element);
    }

    outputIterationDuration(objList);

    outputIterationDuration(objSet);

  }

  private static void outputIterationDuration(final Collection<?> collection) {

    final long startMillis = System.currentTimeMillis();

    for (Object element : collection) {
      // do nothing, we just want to iterate;
    }

    final long durationMillis = System.currentTimeMillis() - startMillis;

    System.out
        .println(String
            .format(
                "Duration for iterating over %d elements in implementation '%s' is %d miliseconds",
                collection.size(), collection.getClass().getCanonicalName(),
                durationMillis));
  }
}

 

[JCODA]

Warum beschlecht mich mal wieder das Gefühl, dass

for (Object element : collection) {
      // do nothing, we just want to iterate;
    }

eh wegoptimiert wird?

 

[nillehammer]

Warum beschlecht mich mal wieder das Gefühl, dass

 for (Object element : collection) {
      // do nothing, we just want to iterate;
    }

eh wegoptimiert wird?

Könnte man denken. Aber wenn man es ausführt, ändern sich die gemessenen Werte je nach Anzahl der Elemente. Also kann man den Zusammenhang zwischen Implementierung/Anzahl der Elemente und Iterationsgeschwindigkeit schon herstellen. Aber wie gesagt, signifikant wird das eh erst bei einer Anzahl, die bei den meisten Anwendungsfällen überhaupt nicht erreicht wird.

 

[Ark]

Warum beschlecht mich mal wieder das Gefühl, dass […] eh wegoptimiert wird?

Ich denke nicht, dass das wegoptimiert wird (und wenn, dann auf keinen Fall "einfach so"). Grund: Es könnte ja sein, dass beim Zugriff auf ein nächstes Element eine Exception fliegt.

Compiler müssen sehr vorsichtig beim Optimieren vorgehen, und das führt sehr häufig dazu, dass eben nicht optimiert wird. Man braucht schon Einiges an Hintergrundwissen über optimierende Compiler, wenn man Code so schreiben will, dass ein (JIT-)Compiler Optimierungen vornehmen könnte.

Ark

 

[AED2]

Danke für den Test nillehammer,

ich habe jetzt nicht deinen ausgeführt, aber einen sehr angelehnten Code, bei mir kam aber überaschenderweise folgende Werte heraus:

Objekte hinzufügen
Objektanzahl: 10.000 - Anzahl der Durchläufe(Für einen Mittelwert): 1.000
Geordnet nach kürzeste Zeit

Container - Zeit
HashSet - 290235
ArrayList - 475826
LinkedList - 1231318

Iterieren
Objektanzahl: 10.000 - Anzahl der Durchläufe(Für einen Mittelwert): 1.000
Geordnet nach kürzeste Zeit

Container - Zeit
HashSet - 88588
ArrayList - 32874507
LinkedList - 112833565

(Nebenbei, hab ich keine Ahnung wie man die Tabelle hier verwendet, gibt keine Anleitung, deswegen etwas behilfmäßig)

Spoiler: Verwendeter Code

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;


public class TestArea {
	private long start, end, total, count, objects;
	
	public static void main(String[] args) {
		new TestArea();
	}
	public TestArea() {
		count = 1000;
		objects = 10000;
		
		System.out.println( "----- Test started -----" );
		HashSet<Long> hs = new HashSet<Long>();
		total = 0;
		for(long i = 0; i < count; i++) {
			start = System.nanoTime();
			testHashSetAdding(hs);
			end = System.nanoTime();
			total += end-start;
		}
		System.out.println( "HashSetAddingTime: " + (total/count) );
		total = 0;
		for(long i = 0; i < count; i++) {
			start = System.nanoTime();
			testHashSetIterating(hs);
			end = System.nanoTime();
			total += end-start;
		}
		//hs = null;
		System.out.println( "HashSetIterationTime: " + (total/count) );
		
		ArrayList<Long> al = new ArrayList<Long>();
		total = 0;
		for(long i = 0; i < count; i++) {
			start = System.nanoTime();
			testArrayListAdding(al);
			end = System.nanoTime();
			total += end-start;
		}
		System.out.println( "ArrayListAddingTime: " + (total/count) );
		total = 0;
		for(long i = 0; i < count; i++) {
			start = System.nanoTime();
			testArrayListIterating(al);
			end = System.nanoTime();
			total += end-start;
		}
		//al = null;
		System.out.println( "ArrayListIterationTime: " + (total/count) );
		
		LinkedList<Long> ll = new LinkedList<Long>();
		total = 0;
		for(long i = 0; i < count; i++) {
			start = System.nanoTime();
			testLinkedListAdding(ll);
			end = System.nanoTime();
			total += end-start;
		}
		System.out.println( "LinkedListAddingTime: " + (total/count) );
		total = 0;
		for(long i = 0; i < count; i++) {
			start = System.nanoTime();
			testLinkedListIterating(ll);
			end = System.nanoTime();
			total += end-start;
		}
		//ll = null;
		System.out.println( "LinkedListIterationTime: " + (total/count) );
		
	}
	public void testHashSetIterating( HashSet<Long> c ) {
		for( long i: c );
	}
	public void testHashSetAdding( HashSet<Long> c ) {
		for( long i = 0; i < objects; i++ ) c.add(i);
	}
	public void testArrayListIterating( ArrayList<Long> c ) {
		for( long i: c );
	}
	public void testArrayListAdding( ArrayList<Long> c ) {
		for( long i = 0; i < objects; i++ ) c.add(i);
	}
	public void testLinkedListIterating( LinkedList<Long> c ) {
		for( long i: c );
	}
	public void testLinkedListAdding( LinkedList<Long> c ) {
		for( long i = 0; i < objects; i++ ) c.add(i);
	}
}

[EDIT]Wenn ich die Anzahl der Objekte auf meinem Computer erhöhe (1Mio+) hängt er sich annähernd auf bei ArrayList und LinkedList, was mich daraus schließen lässt, dass es mit mehr Objekten nicht besser sondern schlimmer wird.[/EDIT]

 

[nillehammer]

Das liegt an Deinem Messverfahren, welches leider aus den zwei folgenden Punkten ungeeignet ist:
- System.nano liefert nicht unbedingt wirklich die richtige nano-Zeit.
- Um die Zeit für eine einzelne Operation zu messen, ist das Messverfahren viel zu ungenau.

[EDIT]Sorry, Punkt 2 ist Quatsch. Ich habe Deinen Code nicht richtig verstanden. :autsch:[/EDIT]
[EDIT]10.00 ist für eine valide Aussage schlicht zu klein. Da kommen einfach zu viele Faktoren hinzu, die im Verhältnis zur eigenlichen Ausführungszeit das Ergebnis zu sehr verfälschen. Fang mal mit ner Million an und vergleiche dann. Wenn wegen OutofMemoryError nicht möglich, teile die Tests auf (musste ich auch machen, als ich noch die anderen Implementierungen hinzugenommen habe).[/EDIT]
[EDIT]Obwohl ich seh grad, dass Du immer zur selben Instanz addest. D.h., wenn ich mich nicht wieder verlesen habe, hast Du am Ende garnicht 10.000 sondern jeweils 1.000 * 10.000 Elemente in den Collections. Das sollte zumindest für den Iterationstest ja eine genügend große Zahl sein.[/EDIT]
Hach ja, Testcode. Ich hör jetzt auf, mit den ganzen Edits

 

[Kjubert]

[OT]

[/OT]

 

[AED2]

Das letzte Edit hat mir den Fehler in meinem Code eröffnet warum der PC hängt bei 1Milliarde (vorher 1Billionen) Iterationen.
Egal ich schmeiß jetzt mit Danke um mich und dann verwende ich HashSet

Danke

 

[nillehammer]

Gute Idee.

 

[TP@Urlaub]

Gute Idee.

Inwiefern ist das eine gute Idee? Du hast den inhaltlich groben Fehler des "Benchmarks" selbst erwähnt, nämlich das immer die selbe Instanz der Datenstrukturen verwendet wird. Somit wird ein Hashset mit einer stabilen Anzahl von 10k Elementen gegen Listen mit 10 Mio. Einträgen verglichen. Über das Ergebnis braucht man sich dann auch nicht wundern. Und, ich weiß nicht ob das aktuell noch so ist, eine Iteration mit dem forEach-Konstrukt über eine ArrayList hatte mal ordentlich Geschwindigkeitseinbußen.

 

[faetzminator]

Und, ich weiß nicht ob das aktuell noch so ist, eine Iteration mit dem forEach-Konstrukt über eine ArrayList hatte mal ordentlich Geschwindigkeitseinbußen.

Egal ob List oder Set, es wird jeweils der Iterator verwendet... Du könntest auch [c]while (it.hasNext()) { ... }[/c] schreiben. Warum sollte da explizit die ArrayList langsamer sein?

 

[maki]

AED2,

zu versuchen Performance zu optimieren ohne eigentlich zu wissen ob sie zu langsam ist, ist irgendwie... hm, nicht so sinnvoll

Lies dir doch mal stattdessen das Colelctions Tutorial durch: Trail: Collections (The Java™ Tutorials)
"Container" gibt es nicht

 

[TP@Urlaub]

Egal ob List oder Set, es wird jeweils der Iterator verwendet... Du könntest auch [c]while (it.hasNext()) { ... }[/c] schreiben. Warum sollte da explizit die ArrayList langsamer sein?

Bei ArrayLists erzeugt der Iterator mehr Overhead als ein simpler Direktzugriff mit get(index) über das Standard-For-Konstrukt.

Ich habe den Testcode etwas umgefrickelt, bei mir (auf der alten Kiste hier mit aktuellsten Java 1.6 -server Flag) ist die Iteration über eine ArrayList per Standard-For immer schneller als ForEach implizit über den Iterator.

import java.util.ArrayList;
import java.util.Collection;
 
public class TestArea {
    public static void main(String[] args){
        new TestArea();
    }
    
    public TestArea() {
    	long start, end, runs;
        runs = 1000;
        
        System.out.println( "----- Test started -----" );
        ArrayList<Long> al = new ArrayList<Long>();
        populate(al);
        
        start = System.nanoTime();
        for(long i = 0; i < runs; i++) {
            iterate((Collection<Long>)al);
        }
        end = System.nanoTime();
        System.out.println( "ArrayListIterationTime-ForEach: " + ((end-start)/runs) );
        
        start = System.nanoTime();
        for(long i = 0; i < runs; i++) {
            iterate(al);
        }
        end = System.nanoTime();
        System.out.println( "ArrayListIterationTime-For: " + ((end-start)/runs) );
    }
    
    public void populate(Collection<Long> collection){
    	final long objects  = 10000;
    	for( long i = 0; i < objects; i++ ) collection.add(i);
    }
    
    public void iterate(Collection<Long> collection){
    	for( long l: collection );
    }
    
 public void iterate(ArrayList<Long> collection){
    	for (int j = 0; j < collection.size(); j++) {
			Long value = collection.get(j);
		}
    }
}

 

[faetzminator]

Bei ArrayLists erzeugt der Iterator mehr Overhead als ein simpler Direktzugriff mit get(index) über das Standard-For-Konstrukt.

Das ist mir auch klar, auch ohne diese (sinnfreien) Laufzeittests. Aber ein Objekt [c]Mensch[/c] zu verwenden, ist auf der JVM auch langsamer, als all seine Daten in einem [c]Object[][/c] zu speichern. Trotzdem schreibt man OO Code. Fazit: Solange man keine Probleme hat, muss man sich auch nicht darum kümmern. Lieber einen Quicksort mit etwas Overhead als einen Bubblesort, welcher "optimiert" wurde.