Najszybszy sposób sprawdzenia, czy ciąg zawiera inny podciąg w JavaScript?


163

Pracuję z problemem wydajności w JavaScript. Chcę tylko zapytać: jaki jest najszybszy sposób sprawdzenia, czy ciąg zawiera inny podciąg (potrzebuję tylko wartości logicznej)? Czy mógłbyś zasugerować swój pomysł i przykładowy fragment kodu?


Czy pytasz o ustalony podciąg, czy potrzebujesz wyrażenia regularnego (jestem trochę zdezorientowany użyciem regextagu)?
Tim Pietzcker,


Co powiesz na podzielenie ciągu znaków na tablicę wokół białych znaków i wykonanie przecięcia tablicy? stackoverflow.com/questions/1885557/…
giorgio79

Odpowiedzi:


315

Masz dwie możliwości:

  1. Wyrażenie regularne :

    (new RegExp('word')).test(str)
    // or
    /word/.test(str)
  2. indexOf:

    str.indexOf('word') !== -1

Wyrażenia regularne wydają się być szybsze (przynajmniej w Chrome 10).

Test wydajności - krótki stóg siana
Test wydajności - długi stóg siana


Aktualizacja 2011:

Nie można z całą pewnością stwierdzić, która metoda jest szybsza. Różnice między przeglądarkami są ogromne. Podczas gdy w Chrome 10 indexOfwydaje się być szybszy, w Safari 5 indexOfjest wyraźnie wolniejszy niż jakakolwiek inna metoda.

Musisz zobaczyć i spróbować samemu. To zależy od Twoich potrzeb. Na przykład wyszukiwanie bez rozróżniania wielkości liter jest znacznie szybsze w przypadku wyrażeń regularnych.


Aktualizacja 2018:

Aby uchronić ludzi przed samodzielnym przeprowadzaniem testów, oto aktualne wyniki dla większości popularnych przeglądarek, wartości procentowe wskazują wzrost wydajności w stosunku do następnego najszybszego wyniku (który różni się w zależności od przeglądarki):

Chrome: indexOf (~ 98% szybciej) <-- wow
Firefox: buforowany RegExp (~ 18% szybciej)
IE11: buforowany RegExp (~ 10% szybciej)
Edge: indexOf (~ 18% szybciej)
Safari: buforowany RegExp (~ 0,4% szybciej)

Zauważ, że buforowane wyrażenie RegExp to: var r = new RegExp('simple'); var c = r.test(str);w przeciwieństwie do:/simple/.test(str)


3
Może to być trochę szybsze tylko wtedy, gdy tekst do wyszukania jest znany wcześniej (tj. Nie jest przechowywany w zmiennej), ponieważ wyrażenie regularne jest tworzone przez silnik JavaScript w czasie parsowania. Jeśli chcesz wyszukać ciąg zawarty w zmiennej wewnątrz innej zmiennej łańcuchowej, indexOf jest najszybciej, ponieważ trzeba by utworzyć obiekt RegExp i przetwarza ciąg ucieczki znaków specjalnych itd.
Stephen Chung

z doświadczenia, indexOf może być szybsze wyszukiwanie bez uwzględniania wielkości liter w przypadku korzystania .toLowerCase na cokolwiek szukasz pierwszy
Hayk Saakian

Piszę aplikację Office 2013, używam interfejsu Microsoft Office Javascript API i używanie indexOfnie działa. Nie wiem dlaczego. Korzystanie z Regex jednak tak. Jest to skrajny przypadek, ale inni mogą napotkać ten sam problem.
Andy Mercer

Czy jest jakiś powód, dla którego substr () nie jest jednym z możliwych rozwiązań? Sądzę, że w wielu sytuacjach jest dużo szybszy niż rozwiązanie RegEx. Nie wiem jednak, jak wypada to w porównaniu z indexOf () (więc jeśli pominąłeś to, ponieważ zawsze działa gorzej niż indexOf (), to w porządku, może dodaj notatkę o tym efekcie.) EDYCJA: ten link JSperf pokazuje kilka interesujących wyniki. Krótka wersja: indexOf () jest najszybszą ze wszystkich metod, ale może się to różnić w zależności od długości łańcucha i powtarzających się wzorców.
Byson

1
@Bison: możesz użyć substr tylko, jeśli już wiesz, gdzie szukać. Skupiłem się tylko na ogólnych rozwiązaniach.
Felix Kling

17

Czy to działa dla Ciebie?

string1.indexOf(string2) >= 0

Edycja: może to nie być szybsze niż RegExp, jeśli ciąg 2 zawiera powtarzające się wzorce. W niektórych przeglądarkach indexOf może działać znacznie wolniej niż RegExp. Zobacz komentarze.

Edycja 2: RegExp może być szybsze niż indexOf, gdy ciągi są bardzo długie i / lub zawierają powtarzające się wzorce. Zobacz komentarze i odpowiedź @ Felix.


ale jak to się ma do innych metod? Czy jest to najszybsza, czy tylko jedna z wielu metod?
Chii,

Powinno to być szybkie, ponieważ jest implementowane przez sam JavaScript (tj. Uruchamia kod natywny). Każda inna metoda oparta na kodzie JavaScript będzie wolniejsza. Jeśli znasz dokładny ciąg, wyrażenie regularne może być nieco szybsze (ponieważ silnik JavaScript nie musi przechodzić przez łańcuch prototypów, aby znaleźć .indexOf).
Stephen Chung,

Jeśli potrzebujesz wyszukiwania bez rozróżniania wielkości liter, zdecydowanie musisz zbudować obiekt RegExp i wywołać test.
Stephen Chung,

3
Właśnie przeprowadziłem test w Safari. indexOfjest wielkością wolniejszą niż jakakolwiek inna metoda. Nie można więc powiedzieć, która metoda jest szybsza. To zależy od przeglądarki.
Felix Kling

@Felix, to dobra obserwacja (nigdy nie ufaj czemuś, dopóki sam tego nie spróbujesz)! Nie wiem dokładnie, pamiętając coś, co mówi, że w łańcuchach z wieloma powtarzającymi się wzorcami regexy powinny działać szybciej niż prosta implementacja porównania pętli, ponieważ wyrażenia regularne są kompilowane do maszyn stanu i mogą odtwarzać wstecz znacznie szybciej niż proste pętle - które zawsze muszą się cofać ścieżka do następnego znaku. +1 za wykonanie eksperymentu i wyciągnięcie tego!
Stephen Chung,

17

Najszybszy

  1. (ES6) obejmuje
    var string = "witaj",
    substring = "lo";
    string.includes (podciąg);
  1. ES5 i starsze wersje indexOf
    var string = "witaj",
    substring = "lo";
    string.indexOf (podciąg)! == -1;

http://jsben.ch/9cwLJ

wprowadź opis obrazu tutaj


8

W ES6 includes()metoda jest używana do określenia, czy jeden ciąg można znaleźć w innym ciągu, zwracając truelub falseodpowiednio.

var str = 'To be, or not to be, that is the question.';

console.log(str.includes('To be'));       // true
console.log(str.includes('question'));    // true
console.log(str.includes('nonexistent')); // false

Tutaj jest jsperf pomiędzy

var ret = str.includes('one');

I

var ret = (str.indexOf('one') !== -1);

Jak widać w jsperf, wydaje się, że oba działają dobrze.


Czy mogę używać wyrażenia „regex” w ramach argumentu include? Jak str.includes("x|y"):; wyszukaj literały „x” lub „y” w tym samym wywołaniu.
ptkato

@Patrick, zgodnie z dołączonym dokumentem, nie możesz regexw nim używać . Jedno obejście dla twojego pytaniastr.includes("x") || str.includes('y')
zangw

W wyniku ulepszeń JavaScript Chrome 59 indexOfjest znacznie szybszy niż includes(do 1600% szybciej). Nie jest jasne, w jaki sposób różnica 44 milionów iteracji / s i ponad 777 milionów i / s wpływa na rzeczywistą wydajność, jednak mobilność prawdopodobnie przynosi wystarczające korzyści, że indexOfpowinien być idealnym wyborem.
Chad Levy,

7

Zauważyłem, że używanie prostej pętli for, iterowanie po wszystkich elementach ciągu i porównywanie za pomocą charAtdziała szybciej niż indexOflub Regex. Kod i dowód są dostępne w JSPerf .

ETA: indexOfi charAtoba działają podobnie strasznie w Chrome Mobile zgodnie z danymi zakresu przeglądarki wymienionymi na jsperf.com


Dziwne, że ręcznie wykonana funkcja jest lepsza niż wbudowana, ale wydaje mi się, że to dlatego, że igła ma tylko jeden znak. Mimo to ...
Moss

Przetestowano w Chrome Mobile 36.0.1985.57 na Apple iPad (iOS 7.1.1). IndexOf jest szybszy. Przepraszamy
rpax

@rpax CharAt jest nadal znacznie szybszy na wszystkich platformach (w oparciu o historię z jsperf) z wyjątkiem Chrome Mobile, gdzie zarówno IndexOf, jak i CharAt działają bardzo słabo w porównaniu do komputerów stacjonarnych.
wpg4665

1
Chciałbym zobaczyć, jak to działa w NodeJS, a także nie jest to dobry przykład, ponieważ szukasz tylko jednego znaku zamiast podłańcucha.
qodeninja

To wcale nie jest prawidłowa odpowiedź. Nie szukasz podciągu, tylko wystąpienie jednego pojedynczego znaku
Henrik Myntti

3

Aby znaleźć prosty łańcuch, użycie metody indexOf () i użycie wyrażenia regularnego jest prawie takie samo: http://jsperf.com/substring - wybierz więc ten, który wydaje się łatwiejszy do napisania.



1

Jest to łatwy sposób na użycie .match()metody do stringów.

var re = /(AND|OR|MAYBE)/;
var str = "IT'S MAYBE BETTER WAY TO USE .MATCH() METHOD TO STRING";
console.log('Do we found something?', Boolean(str.match(re)));

Życzę miłego dnia, sir!


4
Nie ma powodu, matchkiedy istnieje testmetoda… Sprawdź najlepszą odpowiedź.
Bergi,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.