Czy uniks grep działa szybciej przy długich lub krótkich wyszukiwanych hasłach?

Czy szybciej jest wyszukiwać długie lub krótkie wyszukiwane hasła? Czy w ogóle wpływa to na prędkość? Innymi słowy, czy wyszukiwane hasła powinny być jak najbardziej dokładne?

Istnieje ponad 100 000 plików, a każdy plik zawiera od 20 do ponad 5000 wierszy danych. Zwykle grep służy do znalezienia tylko jednego wystąpienia wyszukiwanego terminu.

Powiedzmy, że szukany termin jest SEARCHTERMi będzie taki jak ten:

NAD+DP+1234567890:92++UNIQUE+NAME+SEARCHTERM++12345+FI'

Czy szybciej jest szukać „SEARCH” lub „SEARCHTERM”? Powiedzmy, że w tym przypadku nie obchodzi nas, czy znajdziemy również dopasowania w innych niepowiązanych liniach.

Oto jak obecnie to robię:

grep NAD+DP 123* | grep SEARCHTERM

Ale wciąż uważam to za dość powolne. Zazwyczaj znalezienie danych zajmuje około 3-5 minut, nawet gdy znam przybliżoną nazwę pliku, która ogranicza zakres do około 10 000 plików.

Czy pomocne byłoby dłuższe lub krótsze wyszukiwane hasło? O ile mi wiadomo, grep szuka „bloków” słów o określonej długości?

Niektóre materiały referencyjne:

GNU grep korzysta ze znanego algorytmu Boyera-Moore'a, który najpierw szuka ostatniej litery docelowego ciągu i korzysta z tabeli odnośników, aby powiedzieć, jak daleko może pominąć wejście, gdy znajdzie niedopasowany znak.

z Dlaczego GNU grep jest szybki .

Algorytm wstępnie przetwarza wyszukiwany ciąg (wzorzec), ale nie wyszukuje ciągu (tekst). [...] Ogólnie algorytm działa szybciej wraz ze wzrostem długości wzorca.

z algorytmu wyszukiwania ciągów Boyera – Moore'a .

Wniosek: używaj dłuższych ciągów .

Teraz trochę wzorca dla zabawy:

# Initialisation
cd $(mktemp -d) && dd if=/dev/urandom of=random bs=1M count=1000
# Version
grep --v` # grep (GNU grep) 2.9
# Benchmark
(for s in 'short' 'this is not so short and we could even consider this as pretty long'; do for t in {1..10}; do time grep "$s" random; done; done ) 2> result

Wyniki: 0,952 s to średnia dla krótkiego łańcucha, 0,244 to średnia dla długiego łańcucha.

Uwaga : długość nie jest jedynym kryterium, które należy wziąć pod uwagę.

Możesz spróbować użyć WYSZUKIWANIA lub WYSZUKIWANIA. Spróbuj także zmienić kolejność dwóch poleceń grep. W każdym razie jedyną przydatną opcją będzie najprawdopodobniej użycie kilku rdzeni procesora do jednego wyszukiwania. Zobacz parallelpolecenie.

Nie sądzę, aby podanie bardziej szczegółowego wyszukiwanego terminu znacznie przyspieszyło.

Przy tak wielu plikach do przeszukania musisz jakoś zindeksować swoje dane, aby wyszukiwanie było szybsze.

Mogę zasugerować kilka sposobów:

• Utwórz bazę danych (PostgreSQL lub MySQL), zaimportuj dane do bazy danych - jeden plik w jednym rzędzie, dodaj indeks FTS (wyszukiwanie pełnotekstowe). Utwórz narzędzie do przeszukiwania bazy danych.

• Zaimportuj dane do bazy danych w bardziej szczegółowy sposób, prawdopodobnie jeden wiersz w jednym rzędzie (lub może więcej niż w jednej tabeli), twórz indeksy, dzięki którym dane można przeszukiwać za pomocą indeksów. Utwórz narzędzie do przeszukiwania bazy danych.

• Dodaj swoje pliki do gitrepozytorium, skompresuj za pomocą git gc, użyj git grepdo wyszukiwania. Z mojego doświadczenia wynika, że git grepmoże być szybszy niż standardowy grep10x-100x.

Logicznie rzecz biorąc, krótszy okres będzie wymagał mniej czasu procesora, tak jak grepbędzie to robił

if (filechar[i] == pattern[i]) ...

mniej razy. W rzeczywistości zgaduję, że a grepbędzie związane z We / Wy, a nie z procesorem, więc to nie będzie miało znaczenia.