Performance beim Ermitteln von Elementen aus einer Liste

Gestern schrieb ich einen Artikel über die Möglichkeiten ein Element aus einer Liste unter Java zu ermitteln. Dort wurde unter anderem eine Lösung mittels der Stream-API aufgezeigt. In einem Kommentar zu dem Artikel kam die Frage nach der Performance dieser Methode auf. Aus diesem Grund habe ich einen kleinen Benchmark geschrieben, welcher die Unterschiede in der Performance ermitteln sollte. Der Testfall bestand daraus ein Element aus einer Liste zu ermitteln. Dazu wird eine Liste mit knapp 125.000 Elementen erzeugt. Nun wurde mit unterschiedlichen Methoden versucht das entsprechende Element zu ermitteln. Das gesuchte Element befindet sich in den Testfällen immer an der Position 75.004 der Liste. Erzeugt wird die Liste mit der Methode getElements:

private List<Element> getElements() {

	List<Element> elements = new ArrayList<>();

	// Add 75000 elements
	for (int i = 0; i < 75000; i++) {
		elements.add(new Element(String.valueOf(i), String.valueOf(i)));
	}

	elements.add(new Element("Suppe", "Löffel"));
	elements.add(new Element("Wasser", "Flüssigkeit"));
	elements.add(new Element("Käse", "Gelb"));
	elements.add(new Element("Huhn", "Ei"));

	// Add 50000 elements
	for (int i = 0; i < 50000; i++) {
		elements.add(new Element(String.valueOf(i), String.valueOf(i)));
	}

	return elements;
}

Vom Gefühl her hätte ich vermutet, das die Stream-API immer langsamer ist als die klassische Iteration durch die Liste. Vier unterschiedliche Methoden wurden für das Benchmark implementiert. Beim Benchmark Iterate list wird die Liste über eine foreach-Schleife iteriert und beim entsprechenden Element abgebrochen:

for (Element element : elements) {

	if ("Huhn".equals(element.Key)) {
		specificElement = element;
		break;
	}
}

Die nächste Variante iteriert die Liste ebenfalls durch, nutzt aber die klassische Variante über den Index:

for (int j = 0; j < elements.size(); j++) {

	Element element = elements.get(j);

	if ("Huhn".equals(element.Key)) {
		specificElement = element;
		break;
	}
}

Anschließend folgt eine Variante über die Stream-API, bei welcher die Methode findFirst genutzt wird:

specificElement = elements.stream()
		.filter(element -> "Huhn".equals(element.Key))
		.findFirst()
		.orElse(null);

Bei der letzten Variante wird ebenfalls die Stream-API genutzt, nur diesmal wird findAny genutzt:

specificElement = elements.stream()
		.filter(element -> "Huhn".equals(element.Key))
		.findAny()
		.orElse(null);

Die Idee bei der Nutzung der Methode findAny ist, dass diese schneller ist, da die Suche theoretisch parallelisiert werden kann. Im JavaDoc zu der Methode wird das Ganze so beschrieben:

The behavior of this operation is explicitly nondeterministic; it is
* free to select any element in the stream. This is to allow for maximal
* performance in parallel operations; the cost is that multiple invocations
* on the same source may not return the same result.

Der Benchmark selber führt für jeden Testfall 75.000 mal durch, damit sich Ungenauigkeiten bei einzelnen Läufen wegmitteln und etwaige Optimierung zum tragen kommen können. Wird die Ausführungszeit über alle 75.000 Durchläufe betrachtet ergibt sich folgendes Bild:

Die Durchführungszeiten über alle Durchläufe

Bei der Betrachtung der einzelnen Durchläufe ergibt sich ein ähnliches Bild:

Die Durchführungszeiten pro Durchlauf

Die ermittelten Werte sehen wie folgt aus:

Iterate list
Time in seconds (total): 58.621323501
Time in seconds (per run): 0.00078161764668

Iterate list (without for each)
Time in seconds (total): 51.9264994
Time in seconds (per run): 0.0006923533253333333

Stream list and find first
Time in seconds (total): 55.3019915
Time in seconds (per run): 0.0007373598866666667

Stream list and find any
Time in seconds (total): 90.196209799
Time in seconds (per run): 0.0012026161306533333

Die schnellste Variante scheint die klassische Iteration über den Index zu sein, anschließend folgt die Variante mit der Stream-API und der Methode findFirst. Danach kommt die Iteration mittels einer foreach-Schleife und am Ende folgt weit abgeschlagen die Stream-API-Variante mit der Methode findAny. Das diese so schlecht abschneidet hat mich überrascht. Natürlich sollten Zahlen aus einem Benchmark immer mit Vorsicht genoßen werden, da es sich immer um eine künstliche Gegenüberstellung handelt. Das komplette Benchmark befindet sich auf GitHub und ist unter der MIT-Lizenz lizenziert und damit freie Software.

Element einer Liste unter Java mittels des Stream-API ermitteln

Unter Java kommt es öfter vor, das ein bestimmter Eintrag in einer Liste gesucht werden soll. Gegeben sei in diesem Beispiel folgende Liste:

// List of elements
List elements = new ArrayList();

elements.add(new Element("Suppe", "Löffel"));
elements.add(new Element("Wasser", "Flüssigkeit"));
elements.add(new Element("Käse", "Gelb"));
elements.add(new Element("Huhn", "Ei"));

Die Klasse, welche die Elemente hält ist wie folgt definiert:

class Element {
    public final String Key;
    public final String Value;

    public Element(String key, String value) {
        Key = key;
        Value = value;
    }
}

Soll nun ein bestimmtes Element der Liste ermittelt werden, so kann dies auf dem klassischen Weg wie folgt erledigt werden:

// Get element
Element specificElement = null;

for (Element element : elements) {

    if ("Huhn".equals(element.Key)) {
        specificElement = element;
        break;
    }
}

Mit der seit Java 8 eingeführtes Stream-API kann das Problem eleganter gelöst werden:

// Get element via stream api
Element specificElement = elements.stream()
        .filter(element -> "Huhn".equals(element.Key))
        .findFirst()
        .orElse(null);

In diesem Fall werden die Elemente durchgegangen und überprüft ob in element.Key die Zeichenkette Huhn enthalten ist. Ist dies der Fall, wird das entsprechende Element zurückgegeben. Wird das Element in diesem Fall nicht gefunden, so ist die Variable specificElement null.

Maps unter Java mit computeIfAbsent nutzen

Wenn eine Map unter Java etwas komplexer wird, wie z.B. folgende Map:

Map<String, List<String>> testMap = new HashMap<>();

wird das befüllen derselbigen interessant. In diesem Beispiel soll ein Key und ein neuer Value für die Liste vom Typ String hinzugefügt werden. Damit dies funktioniert muss überprüft werden ob der Key bereits existiert und wenn dies nicht der Fall ist, ein neuer Key angelegt werden. Im kompletten Beispiel sieht das Ganze so aus:

String key = "ABC";
String valueForList = "DEF";

Map<String, List<String>> testMap = new HashMap<>();

if(!testMap.containsKey(key)) {
    testMap.put(key, new ArrayList<>());
} 

testMap.get(key).add(valueForList);

Einfacher und unkomplizierter ist es die Methode computeIfAbsent zu nutzen, welche seit Java 8 in der Definition des Map-Interfaces enthalten ist. Mit der Nutzung der Methode verkürzt sich das Beispiel wie folgt:

String key = "ABC";
String valueForList = "DEF";

Map<String, List<String>> testMap = new HashMap<>();
testMap.computeIfAbsent(key, s -> new ArrayList<>()).add(valueForList);

Damit wird automatisch eine neue ArrayList angelegt, wenn der entsprechende Schlüssel noch nicht hinterlegt ist. Anschließend kann der entsprechende Wert für die Liste hinzugefügt werden.

Konvertierungen zwischen alter und neuer Datums- und Zeit-API

Seit Java 8 verfügt die Programmiersprache über eine sinnvolle Datums- und Zeit-API. In den meisten Fällen kann diese API ohne weitere Probleme genutzt werden. Problematisch wird es nur, wenn die neue API im Zusammenhang mit Legacy-Code genutzt werden soll. Meist wird dort die Klasse Date aus dem Package java.util genutzt. Damit werden Methoden benötigt, um eine Brücke von der alten zur neuen API und umgekehrt zu schlagen. Um ein Date in eine LocalDateTime umzuwandeln, kann folgende Methode genutzt werden:

public static LocalDateTime convertToLocalDateTime(Date date) {
    return date.toInstant().atZone(ZoneId.systemDefault()).toLocalDateTime();
}

Soll der Wert, welcher in der LocalDateTime gespeichert ist, wieder in ein Date-Objekt konvertiert werden, kann folgende Methode genutzt werden:

public static Date convertToDate(LocalDateTime localDateTime) {
    return Date.from(localDateTime.atZone(ZoneId.systemDefault()).toInstant());
}

Bei diesen Konvertierungsmethoden ist zu beachten, dass die Zeitzonen bei der Konvertierung ignoriert werden. Stattdessen wird die Konvertierung mit der Standardzeitzone des Systems durchgeführt. Für die Konvertierung unter Berücksichtigung und Speicherung der Zeitzonen kann die Klasse ZonedDateTime genutzt werden. Die entsprechenden Methoden zur Konvertierung wären folgende:

public static ZonedDateTime convertToZonedDateTime(Date date, ZoneId zoneId) {
    return date.toInstant().atZone(zoneId);
}

public static Date convertToDate(ZonedDateTime zonedDateTime) {
    return Date.from(zonedDateTime.toInstant());
}

Bei der Konvertierung einer Date-Instanz in eine ZoneDateTime muss die entsprechende Zeitzone als ZoneId mitgegeben werden.