FastTraversalLinkedList (Thinking in Java)

[VPX78]

Hallo liebes Board,
ich arbeite gerade das besagte Buch von Bruce Eckel durch und hänge schon seit einiger Zeit bei Exercise 32 im Kapitel Containers in Depth.

Folgende Aufgabenstellung:
Create a FastTraversalLinkedList that interally uses a LinkedList for rapid insertions and removals, and an ArrayList for rapid traversals and get() operations. Test it by modifying ListPerformance.java.


Soweit so gut. Es geht also darum ein Zwitterding aus den beiden besagten Containern zu basteln. Nur ist mir völlig unklar, wie diese Wollmilchsau dann performanter sein soll als ihre beiden Einzelteile, da man die Lists ja synchron halten muss.

Hat jemand von euch eine Idee? Wäre dankbar für einen Hinweis, der mich auf die richtige Spur bringt. :?

besten Dank

Volkmar

 

[SlaterB]

eine Möglichkeit, dort was einzusparen, sehe ich im 'Nicht-synchron-halten'

also du gehst davon aus, dass Einfüge-Operationen immer im Block kommen,
hoffentlich 1000x hintereinander,
in der Zeit wird nur die LinkedList bearbeitet und die ArrayList gelöscht


danach kommen dann 10000 Lese-Operation ohne was einzufügen,
beim ersten wird die ArrayList aus der anderen erzeugt und danach wiederverwendet,

entspricht das dem Aufbau der ListPerformance.java?
oder wie sieht diese denn aus? vielleicht kann man es daraus erkennen

 

[VPX78]

Zunächst danke für die Antwort.

Es ist nicht Teil einer Uni-Hausübung oder so, sondern lediglich mein persönlicher Perfektionismus, dass ich die letzten 600 Übungen in dem Buch gelöst hab, da werd ich so kurz vorm Ende nicht aufgeben :lol:


Du bestätigst meine Vermutung, dass ich da nichts wesentliches übersehe. Performance.java ist im wesentlichen ein Testframework, das Objekte mit dem List-Interface übernimmt und dann verschiedene Operationen durchführt (Elemente einfügen etc.) um anschließend zurückzugeben, wie lange das gedauert hat.


Mein Zugang wäre auch gewesen, einzelne Operationen (z.B. addAll) auf die angesprochen Weise zu optimieren. Viel Spielraum hat man insofern nicht, da man an das List-Interface gebunden ist.