String.split() - viel zu langsam

[Thunder2002]

Hi,

ich brauche z.Z. kurzum brutale String-Performance und am öftensten nutze ich eigentloch String.split. Daher habe ich mich mal daran gemacht das als erstes umzustellen, da es für meine Zwecke deutlich zu langsam ist.

Hier mal eine kleine Versuchsimplementation von mir, ist nach meinen Messungen zumindest schonmal um den Faktor 2.5x schneller als String.split, aber das geht doch sicher noch schneller oder? 😀 Ideen, Vorschläge etc. bitte hierher 🙂

Btw. mein Schwerpunkt liegt eher bei sehr langen Strings von 100kb bis 100mb

public class StringHelper {
    public static String[] split(String string, String splitter) {
        char[] stringChars = string.toCharArray();
        char[] splitterChars = splitter.toCharArray();
        ArrayList<String> list = new ArrayList<String>();
        
        int splitterLen = splitter.length();
        int k = 0, last = 0;
        for (int i = 0, j = string.length(); i < j; ++i) {
            if (stringChars[i] == splitterChars[k])
                ++k;
            else
                k = 0;
            if (k == splitterLen) {
                list.add(string.substring(last, i - --k));
                last = ++i;
                k = 0;
            }                
        }
        if (last < stringChars.length)
            list.add(string.substring(last));
        
        String[] result = new String[list.size()];
        return list.toArray(result);
    }
}

 

[NTB]

Ich steige natürlich nicht sofort durch Deinen Code durch, aber Du könntest in Zeile 6 die ArrayList mit einer sinnvollen Größe initialisieren, sonst wird beim adden ständig eine Kopie des internen Arrays erzeugt und das ist teuer.
Ich vermute, Du weißt vorher nicht, wie groß die Liste wird, aber vielleicht kannst Du es abschätzen. Ansonsten lieber einen hohen Wert benutzen, als einen zu kleinen.

 

[Thunder2002]

Der Default-Constructor von ArrayList initialisiert die Liste bereits mit 10 Elementen und ja ich kann leider nicht abschätzen wie viele Teile es werden kann ich auch nichts anderes vorgeben :?

 

[SlaterB]

wenn die ganze Aktion länger als 100ms dauert, was bei deinen Bemühungen offensichtlich ist,
dann kannst du doch locker 100.000 vorgeben,

Zeit spart das allerdings höchstens paar Promille,

 

[Guest]

oder gleich LinkedList verwenden.

 

[Marco13]

Hm. Nur mal so nebenbei: Was machst du nachher mit den Strings in dem Array? D.h. musst du die Substrings wirklich erstellen (DAS Ist teuer!) oder reicht es nicht vielleicht, wenn du dir die indizes merkst, und dir später dort, wo du sie brauchst, die Daten (mit Hilfe der indizes) direkt aus dem (ohnehin erstellten) char array holst?

 

[byte]

Btw. mein Schwerpunkt liegt eher bei sehr langen Strings von 100kb bis 100mb

Genau da liegt Dein Problem. Man sollte einfach nicht solch lange Strings im Speicher halten, denn Operationen darauf sind einfach furchtbar unperformant. Überlege Dir einfach Alternativen, Deine Probleme zu lösen, z.B. indem Du per Reader nur den Teil aus den Daten liest, den Du benötigst, und Du wirst wesentlich schneller damit fahren.

 

[Thunder2002]

wenn die ganze Aktion länger als 100ms dauert, was bei deinen Bemühungen offensichtlich ist,
dann kannst du doch locker 100.000 vorgeben,

Zeit spart das allerdings höchstens paar Promille,

Leider gibt es nicht zwangsweise soviele Teil es sind wohl normalerweise auch nur 10 oder meinetwegen 20 oder 30 aber keine so großen Mengen.

oder gleich LinkedList verwenden.

Hab ich auch schon versucht, die Liste ist aber langsamer als ArrayList beim Adden 🙁

Hm. Nur mal so nebenbei: Was machst du nachher mit den Strings in dem Array? D.h. musst du die Substrings wirklich erstellen (DAS Ist teuer!) oder reicht es nicht vielleicht, wenn du dir die indizes merkst, und dir später dort, wo du sie brauchst, die Daten (mit Hilfe der indizes) direkt aus dem (ohnehin erstellten) char array holst?

Genau da liegt Dein Problem. Man sollte einfach nicht solch lange Strings im Speicher halten, denn Operationen darauf sind einfach furchtbar unperformant. Überlege Dir einfach Alternativen, Deine Probleme zu lösen, z.B. indem Du per Reader nur den Teil aus den Daten liest, den Du benötigst, und Du wirst wesentlich schneller damit fahren.

Hätte vielleicht noch sagen sollen das es sich um sequenzielle POST-Data handelt die an einen WebServer geschickt werden, sorry. Ich kann leider nicht nur teilweise den InputStream lesen, da die einzelnen Elemente blöderweise nach Spezifikation einfach mit etwas wie "----------123456789" getrennt sind. Ich muss also doch den kompletten InputStream lesen und nach diesem Splitter aufbrechen oder habt ihr eine bessere Idee?

 

[byte]

Ich kann leider nicht nur teilweise den InputStream lesen, da die einzelnen Elemente blöderweise nach Spezifikation einfach mit etwas wie "----------123456789" getrennt sind. Ich muss also doch den kompletten InputStream lesen und nach diesem Splitter aufbrechen oder habt ihr eine bessere Idee?

Hä, verstehe nicht wo Dein Problem ist? Das kannst Du doch prima mit Streams/Readern lösen. Statt alles als String einzulesen und zu splitten, gehst Du den Stream halt sequentiell durch und betrachtest jedes "Element" (wie auch immer die getrennt sind, in Deinem Fall halt "----------123456789") einzelnd.
Genau für sowas gibt es Reader, weil Operationen auf großen Strings eben langsam und speicherintensiv sind.

 

[Thunder2002]

Thx byto, nutze jetzt nen BufferedReader, so funktionierts 😉 hatte vorher den kompletten inputstream einfach in ein großes byte[] gelesen und dann darauß einen string zum splitten gebaut.... 😉