© Excellent backgrounds/Shutterstock.com
Java Magazin
Teil 1: Brownies Collections: GapList und BigList

High-Performance Lists für Java

Jede Applikation benötigt Daten. Diese werden mit dem (Java) Collections Framework verwaltet, das deshalb zu den wichtigsten Teilen des JDK gehört. Es definiert Interfaces und stellt Klassen mit Standardimplementierungen bereit. Gerade für das am häufigsten verwendete Interface java.util.List fehlt aber eine problemlos einsetzbare Implementierung, denn auch die typischerweise genutzte Klasse ArrayList hat bei gewissen Operationen Schwächen. Die Brownies Collections Library stellt deshalb Alternativen bereit, die in allen Fällen schnell sind und gut skalieren.

Thomas Mauch


ArtikelserieTeil 1: Brownies Collections: GapList und BigListTeil 2: Key Collections

Die Brownies Collections Library [1] besteht aus zwei Hauptteilen. In diesem ersten Teil der zweiteiligen Artikelserie stellen wir GapList und BigList mit zugehörigen Klassen vor, die das List-Interface implementieren. Ein zweiter, separater Artikel stellt dann die Key Collections vor, die es erlauben, Collections mit konfigurierbarer Funktionalität zur Laufzeit zu erzeugen.

Um das Problem mit der vom JDK zur Verfügung gestellten List-Implementierung zu illustrieren, sehen wir uns folgendes Beispiel an: Wir schreiben eine Applikation, die ankommende Ereignisse analysieren soll. Die Analyse geschieht immer in einem Fenster von fixer Größe, das die zuletzt angekommenen Elemente enthält. Um dieses Fenster zu unterhalten, brauchen wir also eine Liste, in der wir am Ende neue Elemente hinzufügen und am Anfang nicht mehr benötigte Elemente wieder löschen können. Die eigentliche Analyse wird dann mit Funktionen durchgeführt, die Zugriff auf die Elemente per Index benötigen. Das JDK bietet uns folgende zwei Klassen, die das List-Interface implementieren:

ArrayList ist ideal für die Analysefunktionen, aber das Löschen von Elementen am Anfang der Liste ist – wie wir gleich sehen werden – problematisch. Bei LinkedList ist es genau entgegengesetzt: schnell beim Hinzufügen und Löschen von Elementen, aber nicht geeignet für effizienten Zugriff per Index.

Welche Implementierung man nun wählen soll, ist für einen Entwickler keine einfache Entscheidung. Schließlich weiß man, dass die gerade entwickelte Lösung nicht in jedem Fall performant sein wird – insbesondere, wenn sich auch die Größe des Analysefensters ändern kann. Um das schlechte Gewissen zu beruhigen, macht man vielleicht Performancemessungen, schreibt ein paar Worte in das Designdokument oder wenigstens einen Javadoc-Kommentar, damit die Kollegen auch sehen, dass zumindest die Problematik erkannt worden ist. Vielleicht fragt man sich aber auch, ob es denn keine Implementierung gibt, die beide Anforderungen erfüllt. Genau diese Lücke füllt GapList.

ArrayList

Was sind die Probleme, die beim Einsatz von ArrayList entstehen? Wie bereits in den Java-Tutorials erklärt wird, wird typischerweise die Klasse ArrayList als generell einsetzbare Implementierung verwendet, da sie meistens schneller ist und weniger Speicher braucht als LinkedList [2].

Das Tutorial erwähnt aber auch, dass Operationen, die nicht am Ende der Liste durchgeführt...

Java Magazin
Teil 1: Brownies Collections: GapList und BigList

High-Performance Lists für Java

Jede Applikation benötigt Daten. Diese werden mit dem (Java) Collections Framework verwaltet, das deshalb zu den wichtigsten Teilen des JDK gehört. Es definiert Interfaces und stellt Klassen mit Standardimplementierungen bereit. Gerade für das am häufigsten verwendete Interface java.util.List fehlt aber eine problemlos einsetzbare Implementierung, denn auch die typischerweise genutzte Klasse ArrayList hat bei gewissen Operationen Schwächen. Die Brownies Collections Library stellt deshalb Alternativen bereit, die in allen Fällen schnell sind und gut skalieren.

Thomas Mauch


ArtikelserieTeil 1: Brownies Collections: GapList und BigListTeil 2: Key Collections

Die Brownies Collections Library [1] besteht aus zwei Hauptteilen. In diesem ersten Teil der zweiteiligen Artikelserie stellen wir GapList und BigList mit zugehörigen Klassen vor, die das List-Interface implementieren. Ein zweiter, separater Artikel stellt dann die Key Collections vor, die es erlauben, Collections mit konfigurierbarer Funktionalität zur Laufzeit zu erzeugen.

Um das Problem mit der vom JDK zur Verfügung gestellten List-Implementierung zu illustrieren, sehen wir uns folgendes Beispiel an: Wir schreiben eine Applikation, die ankommende Ereignisse analysieren soll. Die Analyse geschieht immer in einem Fenster von fixer Größe, das die zuletzt angekommenen Elemente enthält. Um dieses Fenster zu unterhalten, brauchen wir also eine Liste, in der wir am Ende neue Elemente hinzufügen und am Anfang nicht mehr benötigte Elemente wieder löschen können. Die eigentliche Analyse wird dann mit Funktionen durchgeführt, die Zugriff auf die Elemente per Index benötigen. Das JDK bietet uns folgende zwei Klassen, die das List-Interface implementieren:

ArrayList ist ideal für die Analysefunktionen, aber das Löschen von Elementen am Anfang der Liste ist – wie wir gleich sehen werden – problematisch. Bei LinkedList ist es genau entgegengesetzt: schnell beim Hinzufügen und Löschen von Elementen, aber nicht geeignet für effizienten Zugriff per Index.

Welche Implementierung man nun wählen soll, ist für einen Entwickler keine einfache Entscheidung. Schließlich weiß man, dass die gerade entwickelte Lösung nicht in jedem Fall performant sein wird – insbesondere, wenn sich auch die Größe des Analysefensters ändern kann. Um das schlechte Gewissen zu beruhigen, macht man vielleicht Performancemessungen, schreibt ein paar Worte in das Designdokument oder wenigstens einen Javadoc-Kommentar, damit die Kollegen auch sehen, dass zumindest die Problematik erkannt worden ist. Vielleicht fragt man sich aber auch, ob es denn keine Implementierung gibt, die beide Anforderungen erfüllt. Genau diese Lücke füllt GapList.

ArrayList

Was sind die Probleme, die beim Einsatz von ArrayList entstehen? Wie bereits in den Java-Tutorials erklärt wird, wird typischerweise die Klasse ArrayList als generell einsetzbare Implementierung verwendet, da sie meistens schneller ist und weniger Speicher braucht als LinkedList [2].

Das Tutorial erwähnt aber auch, dass Operationen, die nicht am Ende der Liste durchgeführt...

Neugierig geworden?


    
Loading...

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang