Der schnellste Weg, einen durch Trennzeichen getrennten String in Java zu teilen

10

Ich erstelle einen Komparator, der mehrspaltige Sortierfunktionen für eine begrenzte Zeichenfolge bietet. Ich verwende derzeit die Split-Methode aus der String-Klasse als meine bevorzugte Wahl für die Aufteilung des rohen Strings in Token.

Ist dies die leistungsstärkste Methode, um den rohen String in ein String-Array zu konvertieren? Ich werde Millionen von Zeilen sortieren, also denke ich, dass der Ansatz wichtig ist.

Es scheint gut zu laufen und ist sehr einfach, aber unsicher, ob es in Java einen schnelleren Weg gibt.

So funktioniert die Sortierung in meinem Komparator:

public int compare(String a, String b) {

    String[] aValues = a.split(_delimiter, _columnComparators.length);
    String[] bValues = b.split(_delimiter, _columnComparators.length);
    int result = 0;

    for( int index : _sortColumnIndices ) {
        result = _columnComparators[index].compare(aValues[index], bValues[index]);
        if(result != 0){
            break;
        }
    }
    return result;
}

Nach dem Benchmarking der verschiedenen Ansätze, ob Sie es glauben oder nicht, war die Split-Methode mit der neuesten Version von Java die schnellste. Sie können meinen fertigen Komparator hier herunterladen: https://sourceforge.net/projects/multicolumnrowcomparator/

Constantin
quelle
5
Ich werde darauf hinweisen, dass die Art der Antwort auf diese Frage von der Umsetzung des JVM abhängt. Das Verhalten von Zeichenfolgen (die ein gemeinsames Backing-Array in OpenJDK, jedoch nicht in OracleJDK verwenden) ist unterschiedlich. Dieser Unterschied kann erhebliche Auswirkungen auf das Aufteilen von Zeichenfolgen und die Erstellung von Teilzeichenfolgen sowie auf die Speicherbereinigung und Speicherlecks haben. Wie groß sind diese Arrays? Wie machst du das jetzt? Würden Sie eine Antwort in Betracht ziehen, die eher einen neuen Stringish-Typ als tatsächliche Java-Strings ergibt?
Die Arraygröße hängt von der Anzahl der Spalten ab und ist daher variabel. Dieser mehrspaltige Komparator wird wie folgt als Parameter übergeben: ExternalSort.mergeSortedFiles (fileList, neue Datei ("BigFile.csv"), _comparator, Charset.defaultCharset (), false); Die externe Sortierroutine sortiert die gesamte
Constantin
Ich würde mir überlegen, mir Lucens Tokenizer anzusehen. Lucene kann nur als leistungsstarke Textanalysebibliothek verwendet werden, die sowohl für einfache als auch für komplexe Aufgaben eine gute Leistung erbringt
Doug T.
Betrachten Sie Apache Commons Langs StringUtils.split[PreserveAllTokens](text, delimiter).
Stellen Sie Monica

Antworten:

19

Ich habe dafür einen schnellen und schmutzigen Benchmark-Test geschrieben. Es werden 7 verschiedene Methoden verglichen, von denen einige spezifische Kenntnisse der zu teilenden Daten erfordern.

Für die allgemeine allgemeine Aufteilung ist Guava Splitter 3,5-mal schneller als String # split (), und ich würde empfehlen, dies zu verwenden. Stringtokenizer ist etwas schneller und das Aufteilen mit indexOf ist doppelt so schnell wie wieder.

Für den Code und weitere Informationen siehe http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/

Tom
quelle
Ich bin nur neugierig, welches JDK Sie verwendet haben ... und wenn es 1.6 wäre, wäre ich am meisten daran interessiert, eine Zusammenfassung Ihrer Ergebnisse in 1.7 zu sehen.
1
es war 1,6, denke ich. Der Code dient als JUnit-Test, wenn Sie ihn in 1.7 ausführen möchten. Hinweis String.split führt einen Regex-Abgleich durch, der immer langsamer ist als das Aufteilen auf ein einzelnes definiertes Zeichen.
Tom
1
Ja, jedoch ruft der StringTokenizer-Code (und ähnlicher Code) für 1.6 einen String.substring () auf, der die O (1) -Erstellung des neuen Strings unter Verwendung desselben Hintergrundarrays ausführt. Dies wurde in 1.7 geändert, um eine Kopie des erforderlichen Teils des Hintergrundarrays anstelle von O (n) zu erstellen. Dies könnte einen deutlichen Einfluss auf Ihre Ergebnisse haben und den Unterschied zwischen dem Split und dem StringTokenizer verringern (was alles verlangsamt, was zuvor Teilzeichenfolgen verwendet hat).
1
Sicherlich wahr. Die Funktionsweise von StringTokenizer hat sich von "Erstellen einer neuen Zeichenfolge mit 3 Ganzzahlen" zu "Erstellen einer neuen Zeichenfolge, Erstellen einer Array-Kopie der Daten" geändert, wodurch sich die Geschwindigkeit dieses Teils ändert. Der Unterschied zwischen den verschiedenen Ansätzen ist jetzt möglicherweise geringer und es wäre interessant (wenn auch aus keinem anderen Grund als dem, der interessant ist), eine Nachverfolgung mit Java 1.7 durchzuführen.
1
Danke für diesen Artikel! Sehr nützlich und wird zum Benchmarking verschiedener Ansätze verwendet.
Constantin
5

Wie @Tom schreibt, ist ein Ansatz vom Typ indexOf schneller als String.split(), da letzterer reguläre Ausdrücke behandelt und viel zusätzlichen Aufwand für sie hat.

Eine Änderung des Algorithmus kann jedoch zu einer erheblichen Beschleunigung führen. Angenommen, dieser Komparator wird zum Sortieren Ihrer ~ 100.000 Zeichenfolgen verwendet, schreiben Sie die nicht Comparator<String>. Denn im Laufe Ihrer Art, wird die gleiche String wahrscheinlich verglichen werden mehrere Male, so werden Sie es aufgeteilt mehrere Male, etc ...

Teilen Sie alle Strings einmal in String [] und Comparator<String[]>sortieren Sie den String []. Am Ende können Sie sie dann alle miteinander kombinieren.

Alternativ können Sie auch eine Map verwenden, um den String -> String [] zwischenzuspeichern oder umgekehrt. zB (skizzenhaft) Beachten Sie auch, dass Sie Speicher gegen Geschwindigkeit eintauschen und hoffen, dass Sie viel RAM haben

HashMap<String, String[]> cache = new HashMap();

int compare(String s1, String s2) {
   String[] cached1 = cache.get(s1);
   if (cached1  == null) {
      cached1 = mySuperSplitter(s1):
      cache.put(s1, cached1);
   }
   String[] cached2 = cache.get(s2);
   if (cached2  == null) {
      cached2 = mySuperSplitter(s2):
      cache.put(s2, cached2);
   }

   return compareAsArrays(cached1, cached2);  // real comparison done here
}
user949300
quelle
Das ist ein guter Punkt.
Tom
Es würde eine Änderung des externen Sortiercodes
Constantin
1
Dann ist es wahrscheinlich am einfachsten, eine Karte zu verwenden. Siehe Bearbeiten.
user949300
Da dies Teil einer externen Sortiermaschine ist (um mit weit mehr Daten umzugehen, als möglicherweise in den verfügbaren Speicher passen), habe ich mich wirklich für einen effizienten "Splitter" entschieden (ja, es ist verschwenderisch, denselben String wiederholt zu teilen, daher mein ursprüngliche Notwendigkeit, dies so schnell wie möglich zu tun)
Constantin
Wenn Sie den ExternalSort-Code kurz durchsuchen, sieht es so aus, als ob Sie am Ende (oder am Anfang) jedes sortAndSave()Aufrufs Ihren Cache geleert haben. Dann sollte Ihnen aufgrund eines riesigen Caches nicht der Speicher ausgehen. IMO sollte der Code einige zusätzliche Hooks enthalten, z. B. das Auslösen von Ereignissen oder das Aufrufen von Do-Nothing-geschützten Methoden, die Benutzer wie Sie überschreiben könnten. (Außerdem sollten nicht alle statischen Methoden vorhanden sein, damit sie dies tun können.) Möglicherweise möchten Sie die Autoren kontaktieren und eine Anfrage einreichen.
user949300
2

Gemäß diesen Benchmarks ist StringTokenizer schneller zum Teilen von Zeichenfolgen, gibt jedoch kein Array zurück, was es weniger bequem macht.

Wenn Sie Millionen von Zeilen sortieren müssen, würde ich die Verwendung eines RDBMS empfehlen.

Tulains Córdova
quelle
3
Das war unter JDK 1.6 - Dinge in Strings sind in 1.7 grundlegend anders - siehe java-performance.info/changes-to-string-java-1-7-0_06 (insbesondere ist das Erstellen eines Teilstrings nicht mehr O (1), sondern eher O (n)). Der Link weist darauf hin, dass in 1.6 Pattern.split eine andere Zeichenfolgenerstellung als in String.substring () verwendet wurde - siehe Code im obigen Kommentar, um dem StringTokenizer.nextToken () und dem privaten Paketkonstruktor zu folgen, auf den es Zugriff hatte.
1

Dies ist die Methode, die ich zum Parsen großer (1 GB +) tabulatorgetrennter Dateien verwende. Es hat weit weniger Overhead als String.split(), ist aber charals Trennzeichen beschränkt. Wenn jemand eine schnellere Methode hat, würde ich sie gerne sehen. Dies kann auch über CharSequenceund erfolgen CharSequence.subSequence, erfordert jedoch eine Implementierung CharSequence.indexOf(char)( String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex)bei Interesse siehe Paketmethode ).

public static String[] split(final String line, final char delimiter)
{
    CharSequence[] temp = new CharSequence[(line.length() / 2) + 1];
    int wordCount = 0;
    int i = 0;
    int j = line.indexOf(delimiter, 0); // first substring

    while (j >= 0)
    {
        temp[wordCount++] = line.substring(i, j);
        i = j + 1;
        j = line.indexOf(delimiter, i); // rest of substrings
    }

    temp[wordCount++] = line.substring(i); // last substring

    String[] result = new String[wordCount];
    System.arraycopy(temp, 0, result, 0, wordCount);

    return result;
}
vallismortis
quelle
Haben Sie dies mit String.split () verglichen? Wenn ja, wie ist der Vergleich?
Jay Elston
@JayElston Bei einer 900-MB-Datei wurde die Zwischenzeit von 7,7 Sekunden auf 6,2 Sekunden reduziert, was etwa 20% schneller ist. Es ist immer noch der langsamste Teil meiner Gleitkomma-Matrix-Analyse. Ich vermute, dass ein Großteil der verbleibenden Zeit die Array-Zuweisung ist. Es könnte möglich sein, die Matrixzuordnung mithilfe eines Tokenizer-basierten Ansatzes mit einem Offset in der Methode auszuschneiden - dies würde eher der Methode ähneln, die ich über dem Code zitiert habe.
Vallismortis