Wie lassen sich Zeichenketten in Java am schnellsten vergleichen?

Question

Wie lassen sich zwei Strings in Java am schnellsten vergleichen?

Gibt es etwas, das schneller ist als Gleiches?

EDIT: Ich kann nicht viel helfen, um das Problem zu klären.

Ich habe zwei Strings, die alphabetisch sortiert sind und EXAKT die gleiche Größe haben

Beispiel: abbcee und abcdee

Strings können bis zu 30 Zeichen lang sein

Answer 1

Das erwarte ich nicht. Sonne Oracle hat den Standard noch nicht optimiert String#equals() auf die Spitze getrieben. Ich erwarte also, dass es bereits der schnellste Weg ist. Werfen Sie einen Blick in den Quellcode, wenn Sie wissen wollen, wie sie es implementiert haben. Hier ist ein Auszug:

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}

Answer 2

Schnellerer Vergleich von Strings gleicher Länge mit Hilfe des Hashcodes:

public static boolean equals(final String s1, final String s2) {
return s1 != null && s2 != null && s1.hashCode() == s2.hashCode()
    && s1.equals(s2);
}

Sie können es testen, meine Ergebnisse sind für 4000000 Vergleichsoperationen einschließlich identischer, gleicher und unterschiedlicher Zeichenketten:

String.equals(String):  177081939
equals(String, String):  44153608

Nota: Die Berechnung des HashCodes eines neuen String-Objekts benötigt eine gewisse Rechenzeit, und anschließend wird der HashCode im Objekt gespeichert. Die von mir vorgeschlagene Verbesserung wird also nur dann schneller sein als der Standardvergleich, wenn String-Objekte wiederverwendet werden. In meiner Anwendung verwende ich String-Konstanten und speichere Strings in Collections. Mehrere Vergleiche von Strings mit meiner Methode sind tatsächlich schneller für mich, aber es kann nicht im Allgemeinen sein.

Wenn die Methode ständig mit neuen Zeichenketten verwendet wird, wie compare("a", "b") wird es keine Verbesserung sein.

Der schnellste Weg zum Vergleich von Zeichenketten hängt also davon ab:

• ob Ihre String-Objekte wiederverwendet werden (wie aus einer Sammlung) oder immer neu sind (wie aus einem Eingabestrom)
• Ob Ihre Saiten unterschiedliche Längen haben
• ob sich Ihre Zeichenfolgen am Anfang oder am Ende der Zeichenfolge unterscheiden
• Ihr Programmierstil, wie oft werden Konstanten verwendet
• Ihre Verwendung von String.intern()

Abgesehen von diesen Tatsachen werden die meisten Programme mit String.equals() zurechtkommen.

Answer 3

Ich habe verschiedene Kombinationen für den Stringvergleich ausprobiert ( Code hier ):

1. s1.equals(s2)
2. s1.length() == s2.length() && s1.hashCode() == s2.hashCode() && s1.equals(s2)
3. s1.hashCode() == s2.hashCode() && s1.equals(s2);
4. s1.length() == s2.length() && s1.equals(s2);

Ich habe Strings von 40 Zeichen Länge verwendet, in 10000000000L Iterationen und vor jeder Iteration habe ich die Strings reinitialisiert.

für gleiche Stiche, die ich bekam:

equal: 2873 milis ???
equal: 21386 milis
equal: 7181 milis
equal: 2710 milis ???

für die gleiche Größe Saiten, aber letzte Zeichen anders bekam ich:

different: 3011 milis
different: 23415 milis
different: 6924 milis
different: 2791 milis

für verschiedene Größen, fast die gleichen Zeichenketten, aber ein Zeichen am Ende für s2 hinzugefügt:

different size: 3167 milis
different size: 5188 milis
different size: 6902 milis
different size: 2951 milis

scheint mir, dass es am besten ist, zuerst einen string.length()-Vergleich vor equals() zu verwenden.

Aber dies wird fast überhaupt keine Rolle, weil dies der Fall ist, wo ich 10^10 String-Vergleiche mit 40 Zeichen Länge und was ist bizarr für mich ist der Fall, wo für gleiche Zeichenfolgen ich eine bessere Geschwindigkeit haben, wenn ich die String-Länge zuerst vergleichen.

Answer 4

Wenn Wenn Sie nachweisen können, dass es sich um einen erheblichen Engpass handelt, was mich überraschen würde, könnten Sie Versuchen Sie

s1.hashCode() == s2.hashCode() && s1.equals(s2)

Es könnte ein bisschen schneller gehen. Vielleicht aber auch nicht.

Answer 5

Es kommt darauf an, was Sie brauchen. Ich denke, equals() ist wirklich optimiert, aber vielleicht brauchen Sie etwas anderes, das schneller ist als equals(). Werfen Sie einen Blick auf diese Stelle .