Warum implementiert die String-Klasse von Java kein effizienteres indexOf ()?

9

Befolgen Sie die folgende Frage zum Stapelüberlauf

/programming/5564610/fast-alernative-for-stringindexofstring-str

Ich habe mich gefragt, warum Java (mindestens 6) keine effizientere Implementierung verwendet.

Es folgt der Code:

java.lang.String # indexOf (String str)

1762    static int indexOf(char[] source, int sourceOffset, int sourceCount,
1763                       char[] target, int targetOffset, int targetCount,
1764                       int fromIndex) {
1765        if (fromIndex >= sourceCount) {
1766            return (targetCount == 0 ? sourceCount : -1);
1767        }
1768        if (fromIndex < 0) {
1769            fromIndex = 0;
1770        }
1771        if (targetCount == 0) {
1772            return fromIndex;
1773        }
1774
1775        char first  = target[targetOffset];
1776        int max = sourceOffset + (sourceCount - targetCount);
1777
1778        for (int i = sourceOffset + fromIndex; i <= max; i++) {
1779            /* Look for first character. */
1780            if (source[i] != first) {
1781                while (++i <= max && source[i] != first);
1782            }
1783
1784            /* Found first character, now look at the rest of v2 */
1785            if (i <= max) {
1786                int j = i + 1;
1787                int end = j + targetCount - 1;
1788                for (int k = targetOffset + 1; j < end && source[j] ==
1789                         target[k]; j++, k++);
1790
1791                if (j == end) {
1792                    /* Found whole string. */
1793                    return i - sourceOffset;
1794                }
1795            }
1796        }
1797        return -1;
1798    }
Yaneeve
quelle
3
Beachten Sie, dass dies im Allgemeinen nicht Java 6 ist, sondern OpenJDK-Code.
Péter Török
1
@ Péter Török, wahr genug, aber das Entpacken der src.zip von jdk1.6.0_23 und das Betrachten der String.java-Datei sehe ich den gleichen genauen Code
Yaneeve
1
@ Yaneeve, hmmm, interessant ... wenn ich ein Oracle-Anwalt wäre, hätte ich sicherlich einige Gedanken dazu :-)
Péter Török
2
Diese Routine wird unter den Deckblättern (sofern verfügbar) über SSE4.2-Anweisungen optimiert. Wenn Ihre Hardware dies unterstützt, aktivieren Sie die Unterstützung einfach mit dem entsprechenden JVM-Flag.
Nim
2
@ Peter - warum? Er hat den Java 6-Code nicht kopiert oder gegen eine Geschäftsgeheimnis- / Geheimhaltungsvereinbarung verstoßen. Er hat gerade gesagt, dass die beiden Dateien in diesem Bereich gleich sind.
Stephen C

Antworten:

26

Bei "Effizienz" dreht sich alles um Kompromisse, und der "beste" Algorithmus hängt von vielen Faktoren ab. Im Fall von indexOf()ist einer dieser Faktoren die erwartete Größe der Zeichenfolgen.

Der JDK-Algorithmus basiert auf einer einfachen indizierten Referenz in vorhandene Zeichenarrays. Der Knuth-Morris-Pratt, auf den Sie verweisen, muss eine neue erstellen int[], die dieselbe Größe wie die Eingabezeichenfolge hat. Für Boyer-Moore benötigen Sie mehrere externe Tabellen, von denen mindestens eine zweidimensional ist (ich glaube, ich habe BM nie implementiert).

Die Frage lautet also: Werden die Zuweisung der zusätzlichen Objekte und das Erstellen von Nachschlagetabellen durch die gesteigerte Leistung des Algorithmus ausgeglichen? Denken Sie daran, wir sprechen nicht von einem Wechsel von O (N 2 ) zu O (N), sondern lediglich von einer Verringerung der Anzahl der für jedes N durchgeführten Schritte.

Und ich würde erwarten, dass die JDK-Designer so etwas wie "Für Zeichenfolgen mit weniger als X Zeichen ist der einfache Ansatz schneller, wir erwarten keine regelmäßige Verwendung von Zeichenfolgen, die länger sind, und Leute, die längere Zeichenfolgen verwenden, wissen, wie man optimiert." ihre Suche. "

kdgregory
quelle
11

Der standardmäßige effiziente String-Suchalgorithmus, den jeder kennt, ist Boyer-Moore . Unter anderem muss eine Übergangstabelle erstellt werden , die dieselbe Größe wie Ihr Zeichensatz hat. Im Fall von ASCII ist dies ein Array mit 256 Einträgen. Dies ist ein konstanter Overhead, der sich bei langen Zeichenfolgen auszahlt und kleine Zeichenfolgen nicht so stark verlangsamt, dass es niemanden interessiert. Java verwendet jedoch 2-Byte-Zeichen, wodurch diese Tabelle 64 KB groß ist. Im normalen Gebrauch übersteigt dieser Overhead die erwartete Beschleunigung von Boyer-Moore, sodass sich Boyer-Moore nicht lohnt.

Natürlich wird der größte Teil dieser Tabelle denselben Eintrag haben, sodass Sie vielleicht denken, dass Sie Ausnahmen nur auf effiziente Weise speichern und dann Standardeinstellungen für alles angeben können, was nicht in Ihren Ausnahmen enthalten ist. Leider sind die Möglichkeiten dafür mit einem Suchaufwand verbunden, der sie zu teuer macht, um effizient zu sein. (Denken Sie bei einem Problem daran, dass ein unerwarteter Zweig einen Pipeline-Stillstand verursacht und diese tendenziell teuer sind.)

Bitte beachten Sie, dass dieses Problem bei Unicode stark von Ihrer Codierung abhängt. Als Java geschrieben wurde, passte Unicode in 64 KB, sodass Java nur 2 Bytes pro Zeichen verwendete und die Länge der Zeichenfolge einfach die Anzahl der durch 2 geteilten Bytes war. (Diese Codierung wurde UCS-2 genannt.) Dies machte es schnell zu Springe zu einem bestimmten Zeichen oder extrahiere einen bestimmten Teilstring und die Ineffizienz fürindexOf()war kein Problem. Leider ist Unicode inzwischen gewachsen, sodass ein Unicode-Zeichen nicht immer in ein Java-Zeichen passt. Dies brachte Java in die Größenprobleme, die sie zu vermeiden versuchten. (Ihre Codierung ist jetzt UTF-16.) Aus Gründen der Abwärtskompatibilität konnten sie die Größe eines Java-Zeichens nicht ändern, aber jetzt gibt es ein Mem, dass Unicode-Zeichen und Java-Zeichen dasselbe sind. Sie sind es nicht, aber nur wenige Java-Programmierer wissen es, und noch weniger werden es wahrscheinlich im täglichen Leben antreffen. (Beachten Sie, dass Windows und .NET aus denselben Gründen denselben Pfad eingeschlagen haben.)

In einigen anderen Sprachen und Umgebungen wird stattdessen UTF-8 verwendet. Es hat die schönen Eigenschaften, dass ASCII Unicode gültig ist und Boyer-Moore effizient ist. Der Nachteil ist, dass die Nichtbeachtung von Problemen mit variablen Bytes Sie viel offensichtlicher trifft als in UTF-16.

Übrigens
quelle
IMO, die behauptet, dass eine 64K-Zuweisung "die erwartete Beschleunigung überschreitet", macht keinen Sinn. Eine ist die Speichergröße, die anderen CPU-Zyklen. Sie sind nicht direkt vergleichbar.
Jerry Coffin
1
@ Jerry-Sarg: Ein direkter Vergleich ist sinnvoll. Es sind nicht zu vernachlässigende CPU-Zyklen erforderlich, um Daten zuzuweisen und eine 64K-Datenstruktur zu initialisieren.
Btilly
1
+1 für die ausführliche Beschreibung der Kosten von Boyer-Moore
kdgregory
Die Initialisierung ist offensichtlich linear in Bezug auf die Größe, aber zumindest in einem typischen Fall ist die Zuordnung ungefähr konstant.
Jerry Coffin
1

Es kommt hauptsächlich darauf an: Die offensichtlichste Verbesserung ist von Boyer-Moore oder einer Variante davon. BM und Varianten wollen jedoch wirklich eine völlig andere Oberfläche.

Insbesondere Boyer-Moore und Derivate arbeiten wirklich in zwei Schritten: Zuerst führen Sie eine Initialisierung durch. Dies erstellt eine Tabelle basiert rein auf der Saite Sie suchen nach . Dadurch wird eine Tabelle erstellt, mit der Sie so oft nach dieser Zeichenfolge suchen können, wie Sie möchten.

Sie sicherlich könnte passen diese in die bestehende Schnittstelle durch die Tabelle memoizing und es für die nachfolgende Durchsuchung von der gleichen Zielzeichenfolge verwenden. Ich denke nicht, dass dies sehr gut zu Suns ursprünglicher Absicht für diese Funktion passen würde: dass es sich um einen Baustein auf niedriger Ebene handelt, der nicht von viel anderem abhängt. Wenn Sie es zu einer übergeordneten Funktion machen, die von vielen anderen Infrastrukturen abhängt, müssen Sie (unter anderem) sicherstellen, dass keine der verwendeten Memo-Infrastrukturen jemals die Teilstringsuche verwenden kann.

Ich denke, das wahrscheinlichste Ergebnis davon wäre einfach, so etwas (dh eine eigenständige Suchroutine) unter einem anderen Namen erneut zu implementieren, mit einer übergeordneten Routine unter dem vorhandenen Namen. Alles in allem denke ich, dass es wahrscheinlich sinnvoller wäre, einfach eine neue übergeordnete Routine mit einem neuen Namen zu schreiben.

Die naheliegende Alternative dazu wäre die Verwendung einer abgespeckten Version des Memoisierens, bei der (zum Beispiel) nur eine Tabelle statisch gespeichert und erneut verwendet wird, wenn die Zielzeichenfolge mit der zum Erstellen der Tabelle verwendeten identisch ist . Das ist sicherlich möglich, wäre aber für viele Anwendungsfälle bei weitem nicht optimal. Es wäre auch nicht trivial, es threadsicher zu machen.

Eine andere Möglichkeit wäre, die zweistufige Natur der BM-Suche explizit aufzudecken. Ich bezweifle jedoch, dass irgendjemand diese Idee wirklich mögen würde - sie ist mit ziemlich hohen Kosten (Ungeschicklichkeit, mangelnde Vertrautheit) und wenig oder gar keinem Nutzen für viele Anwendungsfälle verbunden (die meisten Studien zu diesem Thema zeigen, dass die durchschnittliche Saitenlänge so etwas wie ist 20 Zeichen).

Jerry Sarg
quelle
1
Selbst wenn Sie die zweistufige Natur von BM offenlegen, bezweifle ich, dass Sie eine gute Leistung erzielen würden, da eine 64K-Sprungtabelle nicht in einen CPU-Cache der Stufe 1 passen kann. Die Kosten für einen langsameren Cache überwiegen wahrscheinlich die Tatsache, dass Sie weniger Vorgänge benötigen.
Btilly
@btilly: Das würde einen großen Unterschied machen , wenn Sie wirklich wahrscheinlich sind verwenden die gesamte Tabelle - aber zumindest in einem typischen Fall ~ 1 K die Tabelle in dem Cache sitzen wird, und der Rest wird nur während berührt erhalten Initialisierung.
Jerry Coffin
@ jerry-coffin: Es ist dir offensichtlich egal, ob du asiatischen Text verarbeiten kannst.
Btilly
1
@btilly: Nicht so - es ist nicht so, dass es mir egal ist; Es ist mir bewusst, dass es zumindest für viele Benutzer viel seltener ist. Selbst wenn Sie sich mit asiatischem Text beschäftigen, ist es selten, nach einer einzelnen Zeichenfolge zu suchen, die koreanische und 3 verschiedene Arten japanischer Schriftzeichen sowie 2 verschiedene Arten chinesischer Schriftzeichen usw. enthält. Ja, asiatische Alphabete sind größer als Englisch, aber nein , typisch Die Zeichenfolge enthält immer noch keine Zehntausende eindeutiger Zeichen. Für eine Zeichenfolge mit 20 Zeichen benötigen Sie niemals mehr als 20 Cache-Zeilen der Tabelle.
Jerry Coffin
Im schlimmsten Fall verwenden Sie eine Cache-Zeile pro eindeutigem Zeichen in der Suchzeichenfolge.
Jerry Coffin