Ich habe ein Problem, bei dem ich nach einer Teilzeichenfolge in einer Zeichenfolge suchen möchte. Diese Teilzeichenfolge kann in der Zeichenfolge enthalten sein oder nicht.
%Vor%Zwei Möglichkeiten, die ich kenne, sind:
string.indexOf("how are") Aber gibt es einen anderen "optimierten" Weg? Was hättest du getan?
Kann Ruby eine bessere Antwort geben? Da wir jRuby verwenden, kann die Antwort in Ruby oder Java sein.
"Was hättest du getan?"
Ich würde einen Benchmark machen und versuchen, verschiedene Wege zu vergleichen, um dasselbe zu erreichen, um zu lernen, was am schnellsten ist.
In älteren Ruby-Versionen würden die regexbasierten Suchvorgänge langsamer ausgeführt. Die neue Engine in 1.9.2, die ich für den Benchmark verwende, macht einen großen Unterschied. Vor allem waren unverankerte Suchanfragen viel langsamer als verankert. Jetzt ist es ein Waschvorgang, ob Sie Regex oder eine feste Zeichenkette zum größten Teil suchen. Die Verwendung von match () ohne Vorkompilieren der Regex ist ein schmerzhafter Treffer für die Geschwindigkeit. Wenn Sie also viele Schleifen mit demselben Muster erstellen, ist es sinnvoll, das Muster einer Variablen zuzuweisen und auf die Variable zu verweisen.
Die angezeigten Zeiten geben an, wie lange jeder Test dauerte, um "n" (750.000) Iterationen durchzuführen, daher sind niedrigere Zahlen besser.
%Vor%Mit der Ausgabe:
%Vor%Als Referenz hier einige Zahlen mit Ruby 1.8.7, das ist die Standardeinstellung für Snow Leopard:
%Vor%Ich habe zusätzliche Tests hinzugefügt, um einige Ideen zu den Auswirkungen der Verwendung von nicht verankerten und verankerten Regex zu geben:
%Vor%Da Fruity verwendet wird, sind die Ergebnisse nicht direkt mit den obigen Informationen korreliert, aber es ist immer noch nützlich.
Um einen Überblick über "andere Wege" zu erhalten, können Sie mit dem Wikipedia-Artikel über Algorithmen zur Suche von Strings beginnen:
Das Indizieren von Strings ist eine sehr offensichtliche Methode, um Dinge zu beschleunigen, wie von Martin erwähnt, was nur angemessen ist, wenn Sie mehrere Suchen über dieselbe Zeichenkette durchführen:
Nach meinem Wissen gibt es keine "magische" Möglichkeit, wirklich schnell nach Teilstrings zu suchen, es sei denn, Sie sind bereit, vorab eine Art von Suchmetadaten (think index) zu erstellen. Dies wird höchstwahrscheinlich mehr Zeit verschwenden als Sie speichern, es sei denn, Sie durchsuchen die gleiche Zeichenfolge häufig.
Da das Suchmuster einfach ist, würde ich keine Regex mehr haben.
Wenn Sie davon überzeugt sind, dass die Einrichtungen in Ihrem Laufzeitsystem (die String-in-String-Suche und ähnliches anbieten) für Ihre Anwendung nicht schnell genug sind, versuchen Sie, KMP -Algorithmus.
Aber die Implementierer moderner Laufzeitsysteme haben das wahrscheinlich schon für Sie getan.