Implementation von Zugriffen auf Object[index] in der JVM

[max_ray]

Hallo!

Mich würde interessieren ob ich bei dem aufruf eines .get(index) einer java.util.LinkedList dieselbe Laufzeit habe als ob ich ein java.util.Array verwende (ebenfalls .get(index)).

Wenn ich die Methoden im JRE anschaue sehe ich leider nur die Implementation der LinkedList (die wie erwartet mit einer FOR Schleife durch die Elemente iteriert), die durch die Implementation eine lineare Laufzeit hat.

Bei einem Array endet meine Suche bei diesem Aufruf

public E get(int index) {
	    return (E)a[index];
	}

wobei a vom Typ Object ist.

Interessant wäre jetzt natürlich wie diese Index-Suche(a[index]) funktioniert bzw. implementiert ist. Wenn hier ebenfalls die Speicheradressen mit einer for schleife hinaufgezählt werden wäre das auch ein linearer Aufwand, falls die Speicheradresse 1x addiert nur konstant.

Meine Frage ist, wo finde ich die Implementation von Object[index] ?? Soweit ich bis jetzt herausgefunden habe ist das ein native Aufruf der eine Impementation in C der JVM aufruft.

Danke im vorraus für Hilfe!

 

[happy_robot]

interessante frage, aber ich glaube daß du dir die antwort vielleicht auch selber geben kannst.
fürden nativen teil (in was auch immer der implementiert worden ist) ist es doch ganz klar das der index die summe index x objektgrösse als adresse ist. die alternative wäre eine referenzierung die wohl aufgrund des ziels den java-interpreter performanter zu machen sicherlich als erstes ausgemerzt worden wäre.

warum willst du das wissen??

 

[Guest]

interessante frage, aber ich glaube daß du dir die antwort vielleicht auch selber geben kannst.
fürden nativen teil (in was auch immer der implementiert worden ist) ist es doch ganz klar das der index die summe index x objektgrösse als adresse ist.

Naja ich vermute es auch dass es so ist aber würde es gern mit eigenen Augen sehn. :wink:

die alternative wäre eine referenzierung die wohl aufgrund des ziels den java-interpreter performanter zu machen sicherlich als erstes ausgemerzt worden wäre.

Versteh nicht wirklich wie du das meinst mit referenzieren, wäre nett wenn dus mir kurz erklären kannst.

warum willst du das wissen??

Hab auf der Uni eine Übungsaufgabe abgegeben und dabei eine Liste mit b00lean (sorry wegen der 00 aber bolean richtig geschrieben mag das forum nicht) flags als Linked List implementiert, anstatt als Vector oder Array und der Tutor hat mir einen Punkt abgezogen (um den es mir nicht wirklich geht :wink.
Er meinte dass eben der Aufwand der Methode get(index) bei der LinkedList linear ist und bei einem Array konstant.
Mich interessiert ob es laufzeitmäßig wirklich einen Unterschied macht oder ob im Endeffekt es egal wäre weil beide entweder linear oder konstant sind.

 

[happy_robot]

die alternative wäre eine referenzierung die wohl aufgrund des ziels den java-interpreter performanter zu machen sicherlich als erstes ausgemerzt worden wäre.

Versteh nicht wirklich wie du das meinst mit referenzieren, wäre nett wenn dus mir kurz erklären kannst.

sorry, aber wenn du nicht weißt was es ist kannst du es auch nicht erkennen. es hilft dir also nicht.

Hab auf der Uni eine Übungsaufgabe abgegeben und dabei eine Liste mit b00lean (sorry wegen der 00 aber bolean richtig geschrieben mag das forum nicht) flags als Linked List implementiert, anstatt als Vector oder Array und der Tutor hat mir einen Punkt abgezogen (um den es mir nicht wirklich geht :wink.
Er meinte dass eben der Aufwand der Methode get(index) bei der LinkedList linear ist und bei einem Array konstant.
Mich interessiert ob es laufzeitmäßig wirklich einen Unterschied macht oder ob im Endeffekt es egal wäre weil beide entweder linear oder konstant sind.

da hätte ich dir mehr als einen punkt abgezogen wenn ich tutor wäre

Nur weil in der aufgabenstellung etwas von "Liste" steht ist nicht die erste Klasse die diese Buchstabenfolge im Klassennamen enthält auch gleich die beste Wahl.

Für die fehlende Transferleistung hat er dir einen punkt abgezogen. ist imho vollkommen ok.
und eine "Linked List" ist eine referenzierte folge von elementen, da in jedem element die referenz auf das folgeelement enthalten ist. man muss sich von dem element also erstmal die referenz des folgeelements holen um dann auch daran zu kommen. der vorteil einer LinkedList liegt nur in der performanteren weise des aufbaus, da sich die ordnung nicht durch die folge im speicher sondern durch die referenzen ergibt. wenn man in einem array 1 elemement in der mitte einfügen will müssen alle folgeelement nach hinten verschoben werden. bei einer linked-list werden nur die referenzen umgebogen.

 

[Guest]

sorry, aber wenn du nicht weißt was es ist kannst du es auch nicht erkennen. es hilft dir also nicht.

ich denke ich weis schon was eine referenzierung ist (verweis auf eine adresse), aber ich weis nicht wie du das im zusammenhang mit der implementierung meinst. Denn woher soll man ausser durch addition des vielfachen der objektgröße die Adresse kennen um direkt auf ein Element referenzieren zu können ? Das meinte ich mit erklären :wink:

da hätte ich dir mehr als einen punkt abgezogen wenn ich tutor wäre

Nur weil in der aufgabenstellung etwas von "Liste" steht ist nicht die erste Klasse die diese Buchstabenfolge im Klassennamen enthält auch gleich die beste Wahl.

Naja die Aufgabenstellung war ja nicht eine Liste zu implementieren sondern eine Breitensuche in einem Graphen die die Entfernung aller Knoten von einem Ausgangsknoten berechnet und bei dem jeweiligen Knoten vermerkt.

Die Verkettete-Liste hatte ich "nur" als Implementation der Liste gewählt die die bolean flags hält die anzeigen ob ein Knoten schon besucht wurde oder nicht. Ich hab darüber nicht bewusst nach gedacht ob das jetzt einen Unterschied macht wenn ich nur lesend darauf zugreife.

Für die fehlende Transferleistung hat er dir einen punkt abgezogen. ist imho vollkommen ok.
und eine "Linked List" ist eine referenzierte folge von elementen, da in jedem element die referenz auf das folgeelement enthalten ist. man muss sich von dem element also erstmal die referenz des folgeelements holen um dann auch daran zu kommen. der vorteil einer LinkedList liegt nur in der performanteren weise des aufbaus, da sich die ordnung nicht durch die folge im speicher sondern durch die referenzen ergibt. wenn man in einem array 1 elemement in der mitte einfügen will müssen alle folgeelement nach hinten verschoben werden. bei einer linked-list werden nur die referenzen umgebogen.

Ja war mir klar :wink:. Aber wie gesagt hab nicht bewusst darüber nachgedacht dass die Implementation einen Unterschied macht wenn ich lesend darauf zugreife, da ich eigentlich dachte dass Arrays auch "in Java" implementiert werden und somit auch mit Referenzen (wie LinkedLists) arbeiten. Aber man lernt ja nie aus ...

 

[Guest]

Ok, nachdem ich jetzt nicht einschlafen kann weil es mich nicht loslässt zurück zum eigentlichen Thema: macht es einen Laufzeit Unterschied ob ich Arrays.get(n) mache oder LinkedList.get(n).


Ich hab mir das jetzt so überlegt:

Wenn ich bei der LinkedList (wie sie in Java 5 implementiert ist) die for schleife habe um an mein Element zu kommen habe ich eine lineare Laufzeit.

Wenn ich Arrays verwende muss ich doch auch irgendwo eine lineare Laufzeit haben, denn irgendwie muss ich doch an die Adresse kommen wo mein Element gespeichert ist oder ?

Also entweder wieder durch eine schleife die mir solange die Elementgröße zu meiner Array Basisadresse dazuzählt oder eine eine Multiplikation der Elementgröße, die ja wieder lineare Laufzeit hat vermute ich mal, mit dem Index den ich haben will und danach zu der Basisadresse des Arrays dazugezählt.

Denk ich da falsch oder habe ich sowohl bei der Implementation beim Zugriff aud die Liste als auch beim Zugriff auf das Array eine lineare Laufzeit ?

 

[maki]

Du denkst falsch

Aus der Api Doku für LinkedList:

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Ansonsten hält google sehr viele gegenüberstellungen bereit: http://www.google.com.au/search?num...ct=result&cd=1&q=java+linkedlist+vs+arraylist

 

[ARadauer]

du könntest einen test schreiben, und einfach schaun wie sich die laufzeiten vergleichen

 

[Guest]

Ok jetzt seh ichs auch (danke für die google keywords, man muss einfach nur die richtigen keywords verwenden).
Danke für eure Bemühungen

 

[maki]

"linkedlist vs arraylist" als google suchwörter sind zwar gut, aber ich verwende grundsätzlich nur die englischsprachige Variante von Google (google.us oder google.com.au, letzteres aus gewohnheit), da gibt imho bessere ergebnisse