LinkedList indexOf() - geht des irgendwie schneller?

[Spade]

Hallo zusammen,
Ich hab recht viele Objekte (ca 500.000) in einer LinkedList gespeichert und diese nach einem Member sortiert.
Jetzt stehe ich vor folgenden Problem: Ich muss oft zu einem Objekt das nächste in der LinkedList finden...
Das mache ich so in der Art

// sei "o" das Objekt von dem ich den Nachfolger in der Liste suche
int index = Listenname.indexOf(o);
return Listenname[index+1];

Des ganze wird jetzt nur bei großen Liste sehr langsam.
Deshalb meine Frage: fällt euch da was ein wie das schneller geht, besonders vor dem Hintergrund, dass die ja Liste sortiert ist...
Also vielleicht irgendeine andere Datenstruktur mit der sich mein Problem besser lösen lässt oder so...


Danke und Gruß,
Spade

 

[SlaterB]

da könnte dir das helfen, was man unter google als TreeList in anderen APIs findet, z.B.
TreeList (Collections 3.1 release API)
Koders Code Search: TreeList.java - Java - AL20

in Java fällt mir auf die Schnelle nur eine zusätzliche Map <Element , Index erstes Vorkommen > ein,
aufwendig parallel aktuell zu halten,
na da lohnt sich eher noch die TreeList nachzubauen , in einem oder obigen Links ist auch Quellcode

Doppelte in der Liste wären übrigens generell schlecht

------

edit:
bei einer sortierten Liste reicht vielleicht auch die Collections.binarySearch()-Methode,
da jeder Index-Zugriff bei einer LinkedList aber Wahnsinn ist, lohnt sich das wohl nur bei ArrayList

und obige TreeList hilft bestimmt auch nur, wenn generell Sortierung vorliegt, habe ich nicht getestet, recht vager Vorschlag von mir

 

[nrg]

LinkedList ist dafür nicht das Richtige...

nimm ne ArrayList (oder für eine "Key/Value Beziehung" eine Map). Die sind für einen indexierten Zugriff geeignet.

edit:

besonders vor dem Hintergrund, dass die ja Liste sortiert ist...

das hatte ich übersehen aber dazu hat ja Slater schon gepostet. Wenn du die Liste einmal initialisiert und danach nurnoch darauf zugreifst, könntest du aber trotzdem eine ArrayList nehmen und einfach Collections.sort aufrufen.

 

[maki]

Wenn du navigieren möchtest bzw. eine Untermenge brauchst, kannst du dir auch mal das Interface NavigableSet ansehen, wird von TreeSet und ConcurrentSkipListSet implementiert.

 

[Andi_CH]

Der Zugriff über den [] Operator dürfte der langsame Teil sein. Das ist bei einem Array viel schneller - jetzt kommt es darauf an wie dynamisch deine Liste ist. Wenn sich der Inhalt nur relativ selten ändert und es sehr viel mehr Lesezugriffe gibt würde ich die LinkedList nach jedem Schreibzugriff mit Listenname.toArray in einen solchen konvertieren und darauf lesend zugreifen. Die Linked List hat nämlich gegenüber dem Array den Vorteil dass sehr "billig" Elemente eingefügt werden können.

Es ist abzuwägen ob der Konversionsaufwand den Gewinn nicht auffrisst.

Ich bin gespannt ob jemand konkret weiss was sich ab wann lohnt

Andi

 

[Gast2]

Es ist abzuwägen ob der Konversionsaufwand den Gewinn nicht auffrisst.

Warum dann nicht gleich ne ArrayList nutzen die intern ein Array verwendet?
Wenn du abschätzen kannst wie groß die ArrayList wird und diese direkt mit dieser konkreten Größe erstellst muss im späteren Verlauf auch nicht die größe verändert werden was dir ziemlich viel Zeit erspart.

Der Zugriff über den [] Operator dürfte der langsame Teil sein.

Ich wüsste nicht das man den Operator auf eine LinkedList anwenden kann ^^ Das wird wohl nur pseudocode sein

 

[Spade]

...
Ich wüsste nicht das man den Operator auf eine LinkedList anwenden kann ^^ Das wird wohl nur pseudocode sein

Ja, sorry war mein Fehler, ich meinte Listenname.get(index+1)


Ansonsten, vielen Dank an alle für den vielen Input in der kurzen Zeit...
Dann stürtze ich mich mal in die bunte Welt der API-Dokus und schau mir eure Vorschläge mal im Detail an...

 

[Andi_CH]

Warum dann nicht gleich ne ArrayList nutzen die intern ein Array verwendet?
Wenn du abschätzen kannst wie groß die ArrayList wird und diese direkt mit dieser konkreten Größe erstellst muss im späteren Verlauf auch nicht die größe verändert werden was dir ziemlich viel Zeit erspart.

Die Linked List sei sortiert - einfügen bei einem Array bzw nachträgliches sortieren eines solchen ist teuer. Wie das bei der von dir erwähnten ArrayList ist, weiss ich nicht.

Ich wüsste nicht das man den Operator auf eine LinkedList anwenden kann ^^ Das wird wohl nur pseudocode sein

Hm, jetzt finde ich auch nicht mehr was ich meinte gefunden zu haben - ach dabei wollte ich doch als Ausrede bringen, dass meines auch nur Pseudocode sei

Was sicher geht ist:

listenName.get(x)

was möglicherweise intern daselbe macht wie

listenName.toArray[x]

und da kam mir die Idee das Einfügen neuer Elemente an die richtige Postion in der LinkedList zu erledigen, die dann einmal in einen Array zu konvertieren und diesen zu behalten...

 

[maki]

...
Was sicher geht ist:

listenName.get(x)

was möglicherweise intern daselbe macht wie

listenName.toArray[x]

..

Nö, macht LinkedList sicherlich nicht.
Ergibt sich aus der Doku, und natürlich aus den Sourcen, da wird durchiteriert und gezählt, bei jedem Lookup ein Array zu erstellen wäre auch wenig sinnvoll.

 

[nrg]

es war doch nie die Rede davon, dass der TO mittendrin Objekte einfügen will. Er möchte sie indexiert lesen. Für ersteres ist eine LinkedList natürlich zu bevorzugen aber für letzteres die ArrayList. Weiß auch grad nicht, was es für einen Unterschied bzgl. der Sortierung machen sollte, ob eine ArrayList oder eine LinkedList vorliegt.

 

[faetzminator]

Naja, wenn man eine [c]LinkedList[/c] hat, kann man immerhin so was machen

int result = Collections.binarySearch(new ArrayList<T>(list), key);

 

[maki]

Naja, wenn man eine [c]LinkedList[/c] hat, kann man immerhin so was machen

int result = Collections.binarySearch(new ArrayList<T>(list), key);

Wie umständlich

Macht doch die binarySearch Methode schon von Haus aus etwas ähnliches

 

[Andi_CH]

Ich hab wieder mal nur die Hälfte gelesen Zugriff auf x+1 ist natürlich nicht optimal wenn man schon ein verlinkte Liste hat gibt es sicher effzientere Zugriffsarten
Wo versteckt sich der next-Operator?

Die Frage ist aber auch wie wird das aktuelle Element gefunden von dem der Nachfolger gelesen werden soll ...

 

[Spade]

Die Frage ist aber auch wie wird das aktuelle Element gefunden von dem der Nachfolger gelesen werden soll ...

Also ich mach das momentan wie gesagt über die indexOf() Funktion... ich glaub aber, dass die intern auch nur einfach durch die Liste durchläuft und jedes Element überprüft. Wir haben als Komplexität die linear von N abhängt - was ja bei ner Suche auch normal ist. Aber des ganze muss halt schneller gehn wenn des Ding sortiert ist...

 

[maki]

Wo versteckt sich der next-Operator?

Im Iterator, wie immer.

was ja bei ner Suche auch normal ist. Aber des ganze muss halt schneller gehn wenn des Ding sortiert ist...

Du hast wohl die falsche Datenstruktur gewählt

 

[Spade]

Wo versteckt sich der next-Operator?

Ja also man kann sowas machen:

int index = objectList.indexOf(o);
return objectList.listIterator(index).next();

Aber des macht die Sache leider nicht schneller...

 

[Spade]

Du hast wohl die falsche Datenstruktur gewählt

Ja - des glaub ich so langsam auch

Naja, ich denk ich werd da noch was schöneres finden - ihr habt mir ja einige Möglichkeiten genannt.

Also vielen Danke nochmal an alle!

 

[andiv]

Folgendes sollte die Liste maximal einmal durchlaufen:

public static <E> E getElementAfter(Iterable<E> iterable, E e) {
    Iterator<E> iter = iterable.iterator();
    while(iter.hasNext()) {
        E obj = iter.next();
        if(obj.equals(e)) {
            if(iter.hasNext()) {
                return iter.next();
            } else {
                return null;
            }
        }
    }
    return null;
}

Trotzdem würd ich an deiner Stelle auch über andere (evtl. geeigneteren) Datenstrukturen nachdenken.

 

[Andi_CH]

Ja also man kann sowas machen:

int index = objectList.indexOf(o);
return objectList.listIterator(index).next();

Aber des macht die Sache leider nicht schneller...

Ob indexOf() oder oder get() mach sicher keinen Unterschied - die Zeit bis das Element gefunden ist dauert lange. Der Zugriff über einen index ist definitv im Array am schnellsten, das Suchen eines Elementes ist afaik in einer map am schnellsten und für den Zugriff auf den Nachfolger ist die Verkettete Liste (linked List) am besten geeignet.

Allerdings brauchen wir hier ja gar keinen Zugriff über einen index - das ist nur ein Hilfskonstrukt.

Wenn es nichts passendes gibt (ich weiss es echt nicht), würde ich den "next" pointer in meine Objekte einbauen und diese in eine Map packen. Das ist in weniger als einer halben Stunde implementiert.

 

[maki]

Wenn es nichts passendes gibt (ich weiss es echt nicht),

Tipp:

kannst du dir auch mal das Interface NavigableSet ansehen, wird von TreeSet und ConcurrentSkipListSet implementiert.

 

[Spade]

noch mal ne kurze Anschlussfrage: Seh ich es richtig, dass das "normale" Array also im Sinne von int[] myArray = new int[100]; die einzige Datenstruktur ist, bei der wirklich im physikalischem Sinne im Speicher umsortiert wird?
Also wo dann nach dem sortieren die Objekte auch wirklich hintereinander im Speicher liegen (also in der Form, dass man z.B. in C/C++ mit Pointerarithmetik die Speicherstellen nacheinander ablaufen könnte). Bei allen anderen Datanstrukturen werden ja im Prinzip beim sortieren nur Zeiger (jaja ich weiß im Javakontext nicht ganz korrekt - aber ihr wisst was ich mein) umgesetzt, aber nichts wirklich umkopiert.
Hintergrund ist, dass geplant ist das Projekt für größere Datensets so zu erweitern, so daß dann Teile des Datensets im Sekundärspeicher liegt und da wäre es vom Vorteil, wenn man immer Blöcke in den Arbeitspeicher laden könnte die auch wirklich benachbarte Elemente beinhalten...

 

[faetzminator]

Wenn ein Array keine primitiven Datentypen beinhaltet, werden auch dort nur die Referenzen umgebogen. Man könnte also sagen, dass nur bei primitiven Datentypen die Daten an sich kopiert werden

 

[Spade]

ah ok - hab ich nicht gewusst...
Ja, gut dann muss ich auf dieses Kriterium schon mal keine Rücksicht nehmen bei der Auswahl...

Also nochmal vielen Dank an alle die mitgeholfen haben...
Ich war in Sachen Programmierung schon in recht vielen Foren unterweges (hauptsächlich Webdevelopment und C/C++) und muss echt sagen, dass ich selten auf eine so aktive und kompetente Community gestoßen bin.
Macht echt Spass mit euch :toll:
ich sag dann die Tage nochmal bescheid für was ich mich entschieden habe...

 

[Spade]

So, nur der Vollständigkeit halber:
Ich habe mit jetzt für die ArrayList entschieden.

Gründe hierfür waren (LinkedList und ArrayList jeweil mit 1.000.000 Objekten):

- Sortieren: kaum langsamer als die LinkedList
LinkedList: 1,560 s vs ArrayList: 1,964 s


- get(index): extrem viel schnell als die LinkedList
5000 mal get(index) mit Zufallsindex: LinkedList 66,595s vs ArrayList 0,02 s

- indexOf() deutlich schneller:
100.000 mal indexOf(): LinkedList: 154,337 vs ArrayList: 5,087


Tests auf DualCore 1,7 GHz mit 2Gb RAM.


Insgesamt hat sich die betreffende Funktion mit dem Wechsel von LinkedList auf ArrayList nen Speedup um den Faktor 42.8 bekommen - des nenn ich mal sportlich

Interessant ist noch, in den Objekten direkt noch ein int index einzubauen, das den Index des Objekts in der ArrayList hält.
Hier müsste man die ArrayList dann nach dem sortieren noch einmal durchlaufen und die den passenden Index in das jeweilige Objekt schreiben - geht dann auch ohne indexOf() z.B. so:

int count = 0;
for(Object o : objectList){
	o.setIndex(count);
	count++;
}

des dauert bei einem ArrayList mir 1.000.000 Objekte ca 0,2s bringt aber für die betreffende Funktion nochmal einen Speedup um den Faktor 3,5, da man nicht immer erst nach dem Index des Objekts suchen muss, sondern den direkt zu Verfügung hat.
Nachteil ist halt, dass bei 1.000.000 Objekten auch 1.000.000 Integer also 4Mb mehr im Speicher liegen...

Naja, jedenfalls sind ArrayLists super :toll:

Viele Grüße,
Spade