Leistungsaufwändiges Zeichenaufspalten und -manipulation in Java

Question

Was ist der effizienteste Weg, einen String anhand eines sehr einfachen Trennzeichens zu teilen?

Einige Hintergrundinformationen:

Ich portiere eine Funktion, die ich in C mit einer Menge Zeigerarithmetik geschrieben habe, nach Java und sie ist unglaublich langsam (nach etwas Optimierung immer noch 5 Mal langsamer). Nachdem ich es analysiert habe, stellt sich heraus, dass ein Großteil dieser Überlastung in String.split liegt.

Die betreffende Funktion nimmt einen Hostnamen oder eine IP-Adresse und macht sie generisch:

123.123.123.123->*.123.123.123

a.b.c.example.com->*.example.com

Dies kann regelmäßig über mehrere Millionen Elemente ausgeführt werden, daher ist die Leistung ein Problem.

Bearbeiten: Die Regeln für die Umwandlung sind wie folgt:

• Wenn es sich um eine IP-Adresse handelt, ersetzen Sie den ersten Teil
• Andernfalls finden Sie den Hauptdomainnamen und machen den vorangehenden Teil generisch.

foo.bar.com-> *.bar.com foo.bar.co.uk-> *.bar.co.uk

Ich habe jetzt umgeschrieben, indem ich lastIndexOf und substring verwendet habe, um mich von hinten heranzuarbeiten, und die Leistung hat sich deutlich verbessert.

Ich lasse die Frage weitere 24 Stunden offen, bevor ich mich für die beste Antwort zur zukünftigen Referenz entscheide.

Hier ist, was ich jetzt entwickelt habe (der IP-Teil ist eine unbedeutende Prüfung, bevor diese Funktion aufgerufen wird):

private static String hostConvert(String in) {
    final String [] subs = { "ac", "co", "com", "or", "org", "ne", "net", "ad", "gov", "ed" };

    int dotPos = in.lastIndexOf('.');
    if(dotPos == -1)
        return in;
    int prevDotPos = in.lastIndexOf('.', dotPos-1);
    if(prevDotPos == -1)
        return in;
    CharSequence cs = in.subSequence(prevDotPos+1, dotPos);
    for(String cur : subs) {
        if(cur.contentEquals(cs)) {
            int start = in.lastIndexOf('.', prevDotPos-1);
            if(start == -1 || start == 0)
                return in;
            return "*" + in.substring(start);
        }
    }

    return "*" + in.substring(prevDotPos);
}

Wenn es noch Raum für weitere Verbesserungen gibt, wäre es gut, davon zu hören.

Answer 1

So etwas ist ungefähr so schnell, wie du es machen kannst:

static String starOutFirst(String s) {
    final int K = s.indexOf('.');
    return "*" + s.substring(K);
}
static String starOutButLastTwo(String s) {
    final int K = s.lastIndexOf('.', s.lastIndexOf('.') - 1);
    return "*" + s.substring(K);
}

Dann kannst du folgendes tun:

    System.out.println(starOutFirst("123.123.123.123"));
    // gibt "*.123.123.123"

    System.out.println(starOutButLastTwo("a.b.c.example.com"));
    // gibt "*.example.com"

Vielleicht musst du Regex verwenden, um zu sehen, welcher der beiden Methoden für einen bestimmten String geeignet ist.

Answer 2

Ich würde versuchen, .indexOf(".") zu verwenden, und .substring(index)

Sie haben nicht näher ausgeführt, welches genaue Muster Sie finden wollten, aber wenn Sie auf split() verzichten können, sollte dies die Anzahl der neu allozierten Strings reduzieren (1 statt mehrere).

Answer 3

Von Ihrer Frage ist nicht genau klar, was der Code tun soll. Findet er das erste '.' und ersetzt alles bis dahin durch ein '*'? Oder steckt dahinter eine ausgefeiltere Logik? Vielleicht wird alles bis zum n-ten '.' durch '*' ersetzt?

Wenn Sie eine bestimmte Zeichenfolge suchen möchten, verwenden Sie etwas wie den Boyer-Moore-Algorithmus. Es sollte in der Lage sein, Ihr gewünschtes Muster zu finden, und Sie können dann ersetzen, was Sie möchten.

Beachten Sie, dass String in Java unveränderlich ist. Es könnte schneller sein, die Sequenz direkt zu ändern. Schauen Sie sich andere CharSequence-Implementierungen an, um zu sehen, was Sie tun können, z.B. StringBuffer und CharBuffer. Wenn keine Nebenläufigkeit erforderlich ist, könnte StringBuilder eine Option sein.

Durch die Verwendung eines veränderlichen CharSequence anstelle der Methoden auf String vermeiden Sie eine Menge Objekterzeugung. Wenn Sie nur einen Teil des zugrunde liegenden Zeichenarrays durch ein kürzeres Array (z.B. {'*'}) ersetzen, wird dies wahrscheinlich eine Beschleunigung bringen, da solche Arraykopien recht gut optimiert sind. Am Ende des Tages machen Sie immer noch eine Arraykopie, aber sie könnte schneller sein als neue String-Zuweisungen.

UPDATE

All das oben Gesagte ist ziemlicher Unsinn. Ja, vielleicht können Sie Ihre eigene CharSequence-Implementierung erstellen, die Ihnen besseres Slicing ermöglicht und das Array faul gestaltet (d.h. nichts abschneidet, bis es unbedingt muss), und Strings basierend auf Offset und Ähnlichem zurückgibt. Aber StringBuffer und StringBuilder laufen zumindest direkt nicht so gut wie die von Poly gepostete Lösung. CharBuffer ist völlig ungeeignet; Ich habe nicht erkannt, dass es eine nio-Klasse ist: es ist für ganz andere Dinge gedacht.

Es gibt einige interessante Dinge über Polys Code, die ich mich frage, ob er/sie sie vor dem Posten kannte, nämlich dass die Änderung von "*" in den letzten Zeilen der Methoden zu einem '*' zu einem signifikanten Verlangsamung führt.

Trotzdem hier mein Benchmark. Ich fand eine kleine Optimierung: Das Deklarieren der '.' und "*" Ausdrücke als Konstanten fügt ebenfalls etwas Beschleunigung hinzu, ebenso wie die Verwendung eines lokal begrenzten StringBuilder anstelle des binären Infix-String-Konkatenationsoperators.

Ich weiß, dass gc() bestenfalls beratend ist und schlimmstenfalls ein No-Op, aber ich dachte, es mit etwas Schlafzeit hinzuzufügen, könnte die VM nach dem Erstellen von 1M Strings etwas aufräumen lassen. Jemand mag mich korrigieren, wenn dies vollkommen naiv ist.

Einfaches Benchmark

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

public class StringSplitters {
    private static final String PREFIX = "*";
    private static final char DOT = '.';

    public static String starOutFirst(String s) {
        final int k = s.indexOf(DOT);
        return PREFIX + s.substring(k);
    }

    public static String starOutFirstSb(String s) {
        StringBuilder sb = new StringBuilder();
        final int k = s.indexOf(DOT);
        return sb.append(PREFIX).append(s.substring(k)).toString();
    }

    public static void main(String[] args) throws InterruptedException {
        double[] firstRates = new double[10];
        double[] firstSbRates = new double[10];
        double firstAvg = 0;
        double firstSbAvg = 0;
        double firstMin = Double.POSITIVE_INFINITY;
        double firstMax = Double.NEGATIVE_INFINITY;

        double firstSbMin = Double.POSITIVE_INFINITY;
        double firstSbMax = Double.NEGATIVE_INFINITY;

        for (int i = 0; i < 10; i++) {
            firstRates[i] = testFirst();

            firstAvg += firstRates[i];

            if (firstRates[i] < firstMin)
                firstMin = firstRates[i];
            if (firstRates[i] > firstMax)
                firstMax = firstRates[i];

            Thread.sleep(100);
            System.gc();
            Thread.sleep(100);
        }

        firstAvg /= 10.0d;

        for (int i = 0; i < 10; i++) {
            firstSbRates[i] = testFirstSb();

            firstSbAvg += firstSbRates[i];

            if (firstSbRates[i] < firstSbMin)
                firstSbMin = firstSbRates[i];
            if (firstSbRates[i] > firstSbMax)
                firstSbMax = firstSbRates[i];

            Thread.sleep(100);
            System.gc();
            Thread.sleep(100);
        }

        firstSbAvg /= 10.0d;

        System.out.printf("First:\n\tMin:\t%07.3f\tMax:\t%07.3f\tAvg:\t%07.3f\n\tRates:\t%s\n\n", firstMin, firstMax,
                firstAvg, Arrays.toString(firstRates));
        System.out.printf("FirstSb:\n\tMin:\t%07.3f\tMax:\t%07.3f\tAvg:\t%07.3f\n\tRates:\t%s\n\n", firstSbMin,
                firstSbMax, firstSbAvg, Arrays.toString(firstSbRates));

    }

    private static double testFirst() {
        ArrayList strings = new ArrayList(1000000);

        for (int i = 0; i < 1000000; i++) {
            int first = (int) (Math.random() * 128);
            int second = (int) (Math.random() * 128);
            int third = (int) (Math.random() * 128);
            int fourth = (int) (Math.random() * 128);

            strings.add(String.format("%d.%d.%d.%d", first, second, third, fourth));
        }

        long before = System.currentTimeMillis();
        for (String s : strings) {
            starOutFirst(s);
        }
        long after = System.currentTimeMillis();

        return 1000000000.0d / (after - before);
    }

    private static double testFirstSb() {
        ArrayList strings = new ArrayList(1000000);

        for (int i = 0; i < 1000000; i++) {
            int first = (int) (Math.random() * 128);
            int second = (int) (Math.random() * 128);
            int third = (int) (Math.random() * 128);
            int fourth = (int) (Math.random() * 128);

            strings.add(String.format("%d.%d.%d.%d", first, second, third, fourth));
        }

        long before = System.currentTimeMillis();
        for (String s : strings) {
            starOutFirstSb(s);
        }
        long after = System.currentTimeMillis();

        return 1000000000.0d / (after - before);
    }
}

Ausgabe

First:
    Min:    3802281,369 Max:    5434782,609 Avg:    5185796,131
    Rates:  [3802281,3688212926, 5181347,150259067, 5291005,291005291, 5376344,086021505, 5291005,291005291, 5235602,094240838, 5434782,608695652, 5405405,405405405, 5434782,608695652, 5405405,405405405]

FirstSb:
    Min:    4587155,963 Max:    5747126,437 Avg:    5462087,511
    Rates:  [4587155,963302752, 5747126,436781609, 5617977,528089887, 5208333,333333333, 5681818,181818182, 5586592,17877095, 5586592,17877095, 5524861,878453039, 5524861,878453039, 5555555,555555556]