Ich muss eine Möglichkeit implementieren, Teilstrings (Nadeln) in einer Liste von Strings (Heuhaufen) mit Java zu suchen.
Genauer gesagt enthält meine App eine Liste von Benutzerprofilen. Wenn ich einige Buchstaben eingeben, zum Beispiel "Ja", und dann suche, dann sollten alle Benutzer, deren Name "ja" enthält, angezeigt werden. Zum Beispiel könnte das Ergebnis "Jack", "Jackson", "Jason", "Dijafu" sein.
In Java gibt es, wie ich weiß, drei eingebaute Methoden, um den Such-Teilstring in einem String zu sehen.
string.contains ()
string.indexOf ()
regulärer Ausdruck. es ist etwas wie string.matches ("ja"))
Meine Frage ist: Wie lauten die Laufzeiten der oben genannten Methoden? welches ist die schnellste oder effizienteste oder am weitesten verbreitete Art und Weise zu überprüfen, ob die Liste der Zeichenkette eine gegebene Teilkette enthält.
Ich weiß, dass es einige Algorithmen gibt, die dasselbe tun, wie den Boyer-Moore-String-Suchalgorithmus, den Knuth-Morris-Pratt-Algorithmus und so weiter. Ich möchte sie nicht verwenden, weil ich nur eine kleine Liste von Strings habe, und ich denke, die Verwendung von ihnen ist im Moment eine Art Overkill für mich. Außerdem muss ich viel extra Codierung für einen solchen nicht integrierten Algorithmus eingeben. Wenn Sie denken, dass meine Gedanken nicht korrekt sind, können Sie mich gerne korrigieren.
Die angenommene Antwort ist nicht korrekt und nicht vollständig.
indexOf() führt eine naive String-Suche mit Rückverfolgung bei Nichtübereinstimmungen durch. Dies ist ziemlich schnell bei kleinen Mustern / Texten , zeigt aber eine schlechte Leistung bei großen Texten contains("ja") sollte mit indexOf vergleichbar sein (weil es an es delegiert) matches("ja") liefert nicht das korrekte Ergebnis, da nach einer genauen Übereinstimmung gesucht wird (nur die Zeichenkette "ja" wird genau übereinstimmen) Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find(); wäre der richtige Weg, um Texte mit regulären Ausdrücken zu finden. In der Praxis (mit großen Texten) ist es der effizienteste Weg, nur die Java API zu verwenden. Dies liegt daran, dass ein konstantes Muster (wie "ja" ) nicht von der Regex-Engine (die langsam ist), sondern von einem Boyer-Moore-Algorithmus (der schnell ist) Soweit die drei Fragen gestellt wurden, wird ein regulärer Ausdruck viel langsamer sein, da es erforderlich ist, einen vollständigen Zustandsautomaten zusammenzusetzen, wenn Sie ein viel einfacheres Ziel haben. Für contains vs indexOf ...
(dh contains ruft nur indexOf auf, aber es könnte bei jedem Aufruf eine zusätzliche String -Erzeugung auftreten. Dies ist nur eine Implementierung von contains , aber da der Vertrag von contains eine Vereinfachung darstellt von indexOf , dies ist wahrscheinlich, wie jede Implementierung funktioniert.)
Wenn Sie eine große Anzahl von Strings suchen, habe ich den Aho-Corasick -Algorithmus gelesen , aber es ist nativ in Java implementiert. Es ist derselbe Algorithmus, der von GREP in Unix-basierten Systemen verwendet wird, wenn das hilft und es ziemlich effizient ist. Hier ist eine Java-Implementierung von Berkley.
Siehe auch: Ссылка
Aus dem Beispiel in Ihrer Frage gehe ich davon aus, dass Sie Vergleiche ohne Berücksichtigung der Groß- und Kleinschreibung durchführen wollen. Diese verlangsamen den Prozess erheblich. Wenn Sie also mit einigen Ungenauigkeiten leben können, die von dem Gebietsschema abhängen, in dem Sie den Vergleich durchführen müssen, und Ihr langer Text immer wieder durchsucht wird, kann es sinnvoll sein, den langen Text einmal in Großbuchstaben umzuwandeln auch die Suchzeichenfolge und dann die Groß- / Kleinschreibung nicht.
Dies hängt von JRE (und sogar JDK) make / version ab. Es hängt auch von Faktoren wie Stringlänge, Wahrscheinlichkeit ab, in welcher Position enthalten zu sein, usw. Die einzige Möglichkeit, genaue Leistungsdaten zu erhalten, erfordert die Einrichtung Ihres genauen Kontextes.
Im Allgemeinen sollten aString.contains() und aString.indexOf() jedoch genau gleich sein. Und selbst wenn ein regulärer Ausdruck hervorragend optimiert wäre, würde er die Leistung der ersten beiden nicht überschreiten.
Nein, Java verwendet auch keine extrem spezialisierten Algorithmen.
Tags und Links java regex search search-engine substring