Jak grep działa tak szybko?

Jestem naprawdę zdumiony funkcjonalnością GREP w powłoce, wcześniej używałem metody podciąg w Javie, ale teraz używam do tego GREP i wykonuje się w ciągu kilku sekund, jest niesamowicie szybszy niż kod Java, który pisałem. (z mojego doświadczenia mogę się jednak mylić)

Biorąc to pod uwagę, nie byłem w stanie dowiedzieć się, jak to się dzieje? niewiele jest też dostępnych w sieci.

Czy ktoś może mi w tym pomóc?

Zakładając, że Twoje pytanie dotyczy GNU grepkonkretnie. Oto uwaga od autora, Mike'a Haertela:

GNU grep jest szybki, ponieważ UNIKANIE PATRZENIA NA KAŻDY WPROWADZONY BIT.

GNU grep jest szybki, ponieważ WYKONUJE BARDZO KILKA INSTRUKCJI DLA KAŻDEGO BITTU, na który patrzy.

GNU grep używa dobrze znanego algorytmu Boyera-Moore'a, który najpierw szuka ostatniej litery ciągu docelowego i używa tabeli przeglądowej, aby powiedzieć, jak daleko do przodu może pominąć dane wejściowe, gdy znajdzie niepasujący znak.

GNU grep rozwija również wewnętrzną pętlę Boyer-Moore i ustawia wpisy tablicy delta Boyera-Moore'a w taki sposób, że nie musi wykonywać testu wyjścia pętli na każdym rozwiniętym kroku. Wynikiem tego jest to, że w ramach limitu GNU grep uśrednia mniej niż 3 instrukcje x86 wykonywane dla każdego bajtu wejściowego, na który faktycznie patrzy (i całkowicie pomija wiele bajtów).

GNU grep używa surowych wywołań systemowych systemu Unix i unika kopiowania danych po ich odczytaniu. Co więcej, GNU grep UNIKANIE ŁAMANIA WEJŚCIA NA LINIE. Szukanie nowych linii spowolniłoby grep kilka razy, ponieważ aby znaleźć nowe linie, musiałby spojrzeć na każdy bajt!

Więc zamiast korzystać z wejścia zorientowanego liniowo, GNU grep czyta surowe dane do dużego bufora, przeszukuje bufor używając Boyer-Moore i tylko wtedy, gdy znajdzie dopasowanie, idzie i szuka ograniczających znaki nowej linii (niektóre opcje wiersza poleceń, takie jak - n wyłącz tę optymalizację.)

Ta odpowiedź jest podzbiorem informacji zaczerpniętych stąd .

Aby dodać do doskonałej odpowiedzi Steve'a.

Być może nie jest to powszechnie znane, ale grep jest prawie zawsze szybszy podczas grepowania dłuższego wzoru niż krótkiego, ponieważ w dłuższym wzorze Boyer-Moore może przeskoczyć do przodu w dłuższych krokach, aby osiągnąć jeszcze lepsze prędkości podliniowe :

Przykład:

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

Dłuższa forma jest o 35% szybsza!

Dlaczego? Boyer-Moore konstruuje tablicę pomijania do przodu z łańcucha wzorca, a gdy występuje niedopasowanie, wybiera najdłuższe możliwe pominięcie (od ostatniego znaku do pierwszego) przed porównaniem pojedynczego znaku na wejściu do znaku w tabeli pominięcia.

Oto wideo wyjaśniające Boyer Moore (Credit to kommradHomer)

Innym powszechnym nieporozumieniem (w przypadku GNU grep) jest to, że fgrepjest szybszy niż grep. fin fgrepnie oznacza `` fast '', oznacza `` fixed '' (patrz strona podręcznika), a ponieważ oba są tym samym programem i oba używają Boyer-Moore , nie ma różnicy w szybkości między nimi podczas wyszukiwania ustalonych- ciągi bez znaków specjalnych wyrażenia regularnego. Jedynym powodem, dla którego użycie fgrepjest wtedy, gdy istnieje regexp specjalnym char (jak ., []lub *) Nie ma to być interpretowane jako takie. I nawet wtedy bardziej przenośna / standardowa forma grep -Fjest preferowana fgrep.