Liste auf gegebene Länge zurechtstutzen

Mein Kollege hat immer Sachen in eine Liste gestopft, und wenn sie zu lang geworden ist, mit subList wieder verkleinert. Und das sehr oft, äquivalent zu…

   List<String> list = new ArrayList<>();
    for(int i = 0; i < 100000; i++) {
        list.add("x");
        list.add("a");
        list.add("s");
        list.add("b");
        list.add("y");
        list = list.subList(0, 4);
    }

Nun erzeugt subList (jedenfalls in Java 8) eine neue Listen-Instance, die auf die vorhandene verweist. Was auch die StackOverflowException erklärt, die dieses Code-Snippet erzeugt.

Was ist der eleganteste Weg, das zu vermeiden? Einfach list = new ArrayList<>(list.subList(0, 4)); tut es, aber da kräuseln sich mir die Fußnägel. list = list.stream().limit(4).collect(Collectors.toList()); ist ein wenig mit Kanonen auf Spatzen.

Das sollte doch besser gehen?

Passiert den zwischendrin auch was mit den „weggeworfenen“ Daten? Oder wird die Liste tatsächlich nur gefüllt und dann abgeschnitten?

Falls letzteres, dann wäre es imho besser sowas zu verwenden: https://stackoverflow.com/questions/1963806/is-there-a-fixed-sized-queue-which-removes-excessive-elements

In C++ gibt es resize: http://www.cplusplus.com/reference/vector/vector/resize/, das Ressourcen schonend einen Vektor neubegrößt.
In Java gibt es so etwas aber nicht.
Ich kann mir nicht ganz erklären, wieso bei ersterem eine SOE auftritt.
Der wirklich naive Weg wäre: Neue Liste gegebener Länge erstellen und elementeweise kopieren. Ähnlich machen das whrs auch die Lambdas.

Guava’s EnvictingQueue sieht gut aus, danke!

Es wird ein neues Objekt erzeugt, das eine Referenz auf das alte hält, und das immer wieder, bis die Kette so lang ist, dass der Stack voll ist.

Nun, es geht besser und eine Vorlage dafür liefert die NIO-API und unmodifiableList. Die Frage ist nur, ob das auch elegant ist oder in irgendeiner Form eleganter wird, wenn man statt Start- und Endindex Start- und Endelement in der Sublist speichert.

Eine unmodifiableList ist nur ebenso unmodifiable wie die Instanz (Member list), mit welcher sie initialisiert wird. Wenn man sich die Instanz der Referenzliste aufhebt, kann man sie weiterhin modifizieren und damit modifiziert man auch die unmodifiableList. Das bedeutet, wenn man auf die selbe Art Sublists erstellt, gilt all dies analog. Das macht wohl nur dann Sinn, wenn zur Referenzliste nur Elemente hinzugefügt werden dürfen und diese Referenzliste auch nicht sortiert werden kann. Mit Linked-Lists lässt sich da eine Menge mit anstellen.

Mit immutable Listen wie von vavr oder Guava oder so hätte es jedenfalls kein Problem gegeben.

Oh doch! Kopieren ohne Ende. soweit ich weiß, kann man immutable Lists nicht mal etwas hinzufügen, ohne eine neue Liste mit den alten Elementen plus den neuen Elementen zu erstellen.

Das Problem ist ja erst durch Referenzieren statt Kopieren aufgetreten. Kopieren ist hier nicht die effizienteste Lösung (das wäre EvictingQueue oder ähnliches), aber es funktioniert wenigstens.

Ich verstehe das immernoch nicht. Wird eine Referenz nicht aufgeräumt, wenn sie von keiner Variablen mehr gehalten wird, jedoch das referenzierte Ziel noch existiert?

also wir haben a, b, c und d.
a der Variablenname, b der Wert/die Referenz, c die Liste, d die zweite Liste.
b, worauf a zeigt, wird ersetzt durch b_new, das auf d zeigt. Dann kann b doch aufgeräumt werden, da a b_new hält?

list ist eine Membervarable von UnmodifiableList und sofern die Instanz von UnmodifiableList noch referenziert ist, wird list auch nicht abgeräumt, weil es ja auch noch eine Referenz hat.

Es funktioniert auch mit Referenzieren, nur müsste man dazu halt, wie gesagt, nicht Anfangs- und Endindex in der Sublist speichern, sondern Anfangs- und Endelement. Zusätzlich kann man diese Elemente auch noch in der Referenzliste mappen und wenn eines der gemappten Elemente aus der Referenzliste entfernt wird, wird auch gleich die gesamte Sublist ungültig. Werden in der Referenzliste Elemente zwischen Anfangs- und Endelement der Subliste eingefügt, werden diese auch in der Subliste eingefügt - Selbiges gilt auch für das Entfernen. Ein Sortiervorgang würde ad hoc alle Sublisten ungültig machen, weil nicht gewährleistet ist, dass die Reihenfolge der gespeicherten Elemente noch stimmt. Solange die Referenzliste also nur Hinzufügen zulässt, funktioniert Sublist sowohl über Index als auch über Element. Sobald sie auch Einfügen zulässt, funktioniert nur noch Element.
Kopieren ist hier nicht nur sehr ineffizient, sondern hat auch noch den Nachteil, dass wenn Elemente aus der Referenzliste entfernt werden, diese auch händisch aus allen Sublisten entfernt werden müssten… es sei denn Alle Sublisten wären vom Typ „WeakHashList“ (also WeakHashMap<E, E>).

Achso, die Ursprungsliste wird durch die Subliste noch referenziert und kann somit nicht aufgeräumt werden. Aber es gibt doch 100_000 solcher Sublisten, welche nicht alle von einer Variablen gehalten werden? Ergo können sie doch aufgeräumt werden?

Andernfalls… ist das ein bekanntes Phänomen?

Was mir noch einfallen würde, wären geschachtelte Listen. Dazu werden Sublisten durch Elementverschiebungen (in die Subliste kopieren und aus der Referenzliste löschen) erzeugt und anschließend in der Referenzliste auch als Solche in einer Liste aller Sublisten geführt.

Die Diskussion hab’ ich verpasst, aber … das was in dem Beispielsnippet steht, macht ja „fachlich“ keinen Sinn. Um eine sinnvolle Lösung vorzuschlagen, wäre es gut, zu wissen, was eigentlich das Ergebnis sein soll…

1 „Gefällt mir“

Im Prinzip stimmt das Beispiel schon, alles ist eine große Schleife, es werden dabei irgendwelche Ausgaben erzeugt, und die letzten 20 sollen immer in der UI angezeigt werden. Okay, ein kleiner Unterschied ist, dass im Original die Werte immer vorn eingefügt werden, um ein FIFO-Verhalten zu bekommen. Aber das Kernproblem war eben der Aufruf list = list.subList(0, n);

Die EvictingQueue funktioniert übrigens prima und vereinfacht den Code.

Ich verstehe nicht, wieso

wirklich eine SOE auslösen sollte…

Theoretisch existiert immer nur zur gleichen Zeit eine gültige Referenz…

Und ist subList() wirklich modifiable?

Erst einmal: Du kannst ja gerne glauben, was du willst, aber wenn du es wissen willst, probiere den Schnipsel doch einfach mal aus, statt darüber zu philosophieren.

List.subList ist sowohl in ArrayList wie auch in ArrayList.SubList (in Java 8) so implementiert:

   public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, offset, fromIndex, toIndex);
    }

ArrayList.SubList kopiert die Daten nicht, es verweist aufs Original und merkt sich die Bounds. Es wird also bei jedem Aufruf ein neues Objekt erzeugt, das weiterhin eine Referenz auf das aktuelle Objekt (das this im Konstruktoraufruf) hält. Am Ende hast du eine riesige Kette von SubList → SubList → … → SubList → ArrayList, die der GC nicht wegräumen kann. Und ein Stacktrace kann nicht beliebig tief werden, die JVM „denkt“, dass eine Endlosschleife oder eine außer Kontrolle geratene Rekursion vorliegt und zieht die Reißleine.

1 „Gefällt mir“

:+1: Danke für diese Erklärung, jetzt ist es einleuchtend…

Also das ist „suboptimal“, also ich würde, wenn ich Guava nicht verwenden möchte, manuell Elemente in eine neue Liste kopieren, und dafür eine Helper-Methode schreiben.

Aber evtl. gehst du noch auf Marco13s Frage ein und schreibst etwas mehr über den Anwendungsfall…

Das geschriebene reicht eigentlich. Wichtig war, dass immer vorn eingefügt wird. Der Aufruf von subList ist da natürllich … häm… naja, „bequem“, und vielleicht auch „nahe liegend“ für Leute, die andere Programmiersprachen/Libs gewohnt sind und die genaue Semantik von subList nicht kennen, und vielleicht ist er auch „theoretisch elegant“, aber… der Unterschied zwischen Theorie und Praxis ist in der Praxis größer, als in der Theorie. Ich hätte das vielleicht ganz pragmatisch gemacht, vielleicht mit einem list.subList(5, list.size()).clear() oder so…

1 „Gefällt mir“