Schnellste Pad-Left-Funktion in Java

Da Java von Haus aus keine Funktion mitbringt, um Strings rechts- oder linksseitig aufzufüllen, muss man sich diese entweder selber programmieren oder auf eine bestehende Bibliothek wie zum Beispiel Apache Commons zurückgreifen. Da ich vor kurzem eine Funktion brauchte, die einen numerischen String linksseitig (=padLeft) auf 8 Stellen mit Nullen auffüllt, jedoch für solch eine simple Funktion keine ganze Library einbinden wollte, blieb also nur die Option selber eine padLeft-Funktion zu schreiben.

Beim recherchieren und der Umsetzung bin ich jedoch auf diverse Lösungsansätze gestoßen, sodass ich am Ende mit sechs verschiedenen padLeft-Implementierungen da stand. Um nun die beste padLeft-Funktion für mich zu finden, habe ich alle sechs Implementierungen einem kleinen Performance-Test unterzogen und die schnellste padLeft-Funktion ermittelt. Bevor ich auf die Ergebnisse eingehe, möchte ich jedoch erst die einzelnen Funktionen kurz darstellen.

padLeft in Java – sechs Varianten

Die erste Version (padLeftFormat) ist eine der kürzesten Implementierungen und arbeitet mit der format-Methode der String-Klasse. Die format-Methode nimmt hierbei die komplette Arbeit ab und füllt den String um beliebig viele 0 auf. Nachteil: Die Funktion kann nur Nullen auffüllen.

private static String padLeftFormat(String input, int padUpTo){
	return String.format("%0" + padUpTo + "d", Integer.parseInt(input));
}

Die zweite Version (padLeftLoopRaw) basiert auf einer Schleife, die so oft durchlaufen wird, wie es Zeichen aufzufüllen gilt. Die String-Bearbeitung geschieht mittels “+=”-Operator. Vorteil: Diese Implementierung kann beliebig viele beliebige Zeichen auffüllen.

private static String padLeftLoopRaw(String input, char padChar, int padUpTo){
	String out = new String();
	for (int toPrepend=padUpTo-input.length(); toPrepend>0; toPrepend--) {
		out += padChar;
	}
	return out + input;
}

Die dritte Version (padLeftLoopSB) ähnelt stark der zweiten Version. Sie basiert ebenfalls auf einer Schleife, verwendet statt dem “+=”-Operator zum konkatenieren der Strings jedoch die StringBuilder-Klasse. Vorteile: Flexibel in Anzahl der aufzufüllenden Stellen sowie des aufzufüllenden Zeichens.

private static String padLeftLoopSB(String input, char padChar, int padUpTo){
	StringBuilder sb = new StringBuilder();
	for (int toPrepend=padUpTo-input.length(); toPrepend>0; toPrepend--) {
	    sb.append(padChar);
	}
	sb.append(input);
	return sb.toString();
}

Die vierte Version (padLeftSBInsert) arbeitet mit einem Array sowie der insert-Methode der StringBuilder-Klasse. Zuerst wird ein Array mit den aufzufüllenden Zeichen erstellt, welches dann per insert-Methode vor den Eingabe-String gesetzt wird. Vorteile: Variable Anzahl der aufzufüllenden Stellen sowie freie Wahl des aufzufüllenden Zeichens.

private static String padLeftSBInsert(String input, char padChar, int padUpTo){
	StringBuilder sb = new StringBuilder(input);
	int filler = padUpTo-input.length()<0?0:padUpTo-input.length();
	char[] myarray = new char[filler];
	Arrays.fill(myarray, padChar);
	sb.insert(0, myarray);
	return sb.toString();
}

Die fünfte Implementierung (padLeftFixed) ist die einfachste, jedoch auch die “starrste”. Ein Muster (String aus Nullen, der in der Länge der gewünschten aufgefüllten Länge entspricht) wird per substring-Methode auf die aufzufüllende Länge gekürzt und mit dem Eingabe-String verbunden. Nachteil: Keine Flexibilität bei Anzahl der aufzufüllenden Stellen sowie aufzufüllendem Zeichen.

private static String padLeftFixed(String input){
	return input.length() < 3 ? "00000000".substring(input.length()) + input : input;		
}

Die sechste Methode (padLeftArray) ähnelt ein wenig der vierten Methode. Anstelle eines Arrays mit aufzufüllenden Zeichen wird hier jedoch ein Array in der Ziellänge erstellt und mit dem Eingabe-String sowie den Füll-Symbolen aufgefüllt und schlussendlich in einen String umgewandelt. Vorteile: Volle Flexibilität bei Anzahl der aufzufüllenden Stellen sowie des aufzufüllenden Zeichens.

private static String padLeftArray(String input, char padChar, int padUpTo){		
	int filler = padUpTo-input.length()<0?0:padUpTo-input.length();
	char[] temp = (new String(new char[filler]) + input).toCharArray();
	Arrays.fill(temp, 0, filler, padChar);
	return new String(temp);
}

Auch wenn einige der Implementierungen starrer bzw. weniger flexibel als andere sind, erfüllen alle 6 Funktionen meine Anforderung einen String auf 8-Stellen mit dem Symbol “0” aufzufüllen.

padLeft – Performancevergleich

Für den Performance-Test habe ich ein kleines Testprogramm geschrieben, welches jede der sechs Funktionen für die Zahlen 1 bis 10.000.000 ausführt und die Zeit für die Ausführung misst. Um Schwankungen auszugleichen, habe ich diesen Lauf insgesamt 5 mal ausgeführt und das arithmethische Mittel der Ausführungszeit in Millisekunden errechnet. (Wer einen Blick auf das Testprogramm werfen möchte, kann dies in folgendem Code-Block tun.)

import java.util.ArrayList;
import java.util.Arrays;

public class StringPadTester {

	public static void main(String[] args) {
		
		ArrayList<String> samples = new ArrayList<String>();
		for (int i = 1; i <= 10000000; i++)
			samples.add(""+i);
		
		long start = System.currentTimeMillis();
		long time = System.currentTimeMillis();
		long[] averages = new long[6];
		int numRuns = 5;
		
		for (int i = 0; i < numRuns;i++){	
			System.out.println("Run "+(i+1)+":");
		
			start = System.currentTimeMillis();
			for (String str : samples){
				padLeftSBInsert(str, '0', 8);
			}
			time = System.currentTimeMillis() - start;
			System.out.println("padLeftSBInsert: " + time + "ms");
			averages[0] += time;
			
			
			start = System.currentTimeMillis();				
			for (String str : samples){
				padLeftFormat(str, 8);			
			}
			time = System.currentTimeMillis() - start;
			System.out.println("padLeftFormat: " + time + "ms");
			averages[1] += time;
			
			
			start = System.currentTimeMillis();				
			for (String str : samples){			
				padLeftLoopSB(str, '0', 8);			
			}
			time = System.currentTimeMillis() - start;
			System.out.println("padLeftLoopSB: " + time + "ms");
			averages[2] += time;
			
			
			start = System.currentTimeMillis();				
			for (String str : samples){		
				padLeftLoopRaw(str, '0', 8);			
			}
			time = System.currentTimeMillis() - start;
			System.out.println("padLeftLoopRaw: " + time + "ms");
			averages[3] += time;
			
			
			start = System.currentTimeMillis();				
			for (String str : samples){
				padLeftFixed(str);
			}
			time = System.currentTimeMillis() - start;
			System.out.println("padLeftFixed: " + time + "ms");
			averages[4] += time;
			
			
			start = System.currentTimeMillis();				
			for (String str : samples){
				padLeftArray(str, '0', 8);
			}
			time = System.currentTimeMillis() - start;
			System.out.println("padLeftArray: " + time + "ms");
			averages[5] += time;	
			
			System.out.println("----------------------------");
		}
		
		System.out.println("padLeftSBInsert: " + (averages[0]/numRuns) + "ms");
		System.out.println("padLeftFormat: " + (averages[1]/numRuns) + "ms");
		System.out.println("padLeftLoopSB: " + (averages[2]/numRuns) + "ms");
		System.out.println("padLeftLoopRaw: " + (averages[3]/numRuns) + "ms");
		System.out.println("padLeftFixed: " + (averages[4]/numRuns) + "ms");
		System.out.println("padLeftArray: " + (averages[5]/numRuns) + "ms");
	}
	
}

Das Ergebnis des Performance-Vergleichs ist relativ eindeutig. Mit Abstand am schnellsten in der Ausführung ist die padLeftFixed-Funktion. Mit 93ms pro 10.000.000 Ausführungen ist sie ca. 100x schneller als die padLeftFormat-Funktion. Jedoch ist die padLeftFixed-Funktion auch nicht so flexibel. Die schnellste, voll-parametrisierbare Funktion ist die padLeftLoopSB-Funktion mit 475ms, welche somit noch rund 20x schneller als die padLeftFormat-Funktion ist. Auch interessant – die Funktion padLeftLoopRaw ist mehr als doppelt so langsam wie die Funktion padLeftLoopSB. Der StringBuilder verdoppelt also die Geschwindigkeit im Vergleich zum “+=”-Operator.

In der zweiten Grafik habe ich einmal die Ausführungszeit in ms pro 10.000.000 Aufrufe für die 5 einzelnen Runs geplottet. Hier lässt sich sehen, dass die padLeftSBInsert-Funktion im ersten Lauf gut doppelt solange braucht wie in allen Folgeläufen. Da sie jedoch immer noch recht langsam ist, habe ich nicht weiter nach der Ursache für dieses Phänomen gesucht.

Fazit

“1000 Wege führen nach Rom…” – aber nur einer ist der schnellste! Auch wenn es zig Arten gibt, eine padLeft-Funktion in Java zu implementieren, kann es durchaus Sinn machen, einen Performance-Vergleich zu machen. Die schnellste padLeft-Funktion ist um den Faktor 20x schneller als die langsamste. Abschließend würde ich gerne noch wissen, ob ihr eure padLeft-/padRight-Funktionen selber schreibt oder ob ihr fertige Libraries nutzt?