Hledač v souborech

11.3.2011 00:00 | Přečteno: 1382× | Jiné | poslední úprava: 11.3.2011 00:34

Protože můj skriptík v bashi na hledání v obsahu souborů byl nechutně pomalý a už mě to štvalo, tak jsem upatlal narychlo jednu utilitku v C++. Je to trošku prasácky, ale pro mé účely to stačí. Ke stažení v příloze prvního komentáře, jak skriptík, tak program.

Pokud vynalézám kolo, tak sry, já na to žádnou utilitku ve svém systému neznám.

Rychlost hledání je na mém systému 0.6s vs. 13s v celém stromu téhle věci.

Ještě jedna věc, kompilujte buď s parametrem -std=c++0x, nebo vyhoďte ten static_assert (ale ujistěte se, že je podmínka splněna, jinak to bude chybovat u velkých souborů, např, na x86-32 při definování _FILE_OFFSET_BITS=64)

       

Komentáře

[Jardík]

Přílohy:

• findinfiles.cpp (3431 bytů)
• aaa.sh (246 bytů)

Tady

[Jardík]

BTW pod licencí Do What The Fuck You Want To Public License, version 2

[Jardík]

Koukám, že jsem v tom C++ souboru zapomněl pár include souborů, co byly z pokusů (nejdříve tam byl read() ale protože to bylo moc na logiku, tam jsem tam prsknul nakonec mmap()).

[Jardík]

Příloha:

• findinfiles.cpp (4246 bytů)

Aktualizovaný zdroják, několikanásobné zrychlení.

[Ladicek]

Hledá to v Jiných Objektech?

[Jardík]

Co? Hledá to jen v souborech (i binárních) text, co mu předáš jako argument.

[moira]

Tohle souvisí s těmi Objekty. Aspoň doufám. Člověk si nemůže být jist, až po důkladném zkoumaní, které nechci absolvovat.

[Pindal]

Hehe. To mi připomíná, že mistr Hejl asi pořád hledá programátora a Jardík je bez práce, ne? Z jejich spolupráce by jistě vzešlo veledílo. Sice nedodělané, ale nejmíň 64-bitové!

[manasekp]

hejlovi se nahodou celkem dari, posledne sem se dival na jeho web a uz mel hotove logo Novy Hledac vytvorene ve wordu

[disorder]

grep -r, alebo find a grep by postacil. alebo som to vobec nepochopil.

[David Watzke]

Měl by postačit grep s přepínači -r a -l.

[David Watzke]

A ještě asi -a pro hledání v binárních souborech.

[CET]

Pochopil jsi to zrejme naprosto spravne, jenom proste Jardik nezna linuxove utility, takze se snazil to v shellu napsat tak, jak by to napsal v C. No a to je samozrejme pomaly, protoze shell je interpretovany, takze kazdy prikaz se znovu a znovu interpretuje.

Samozrejme by ten shell skript mel byt pouze jeden grep prikaz grep -raliF 'hledany-text' directory, pripadne pokud Jardik zvlada regularni vyrazy, tak grep -raliE 'extended-regexp' directory.

Docela by me zajimal rozdil oproti tomu tvymu CPP. Udelej benchmark. Zkus to s tim -raliF to hleda plain-text, zadny regexp (regexp bude zrejme o trosku pomalejsi).

[Jardík]

time grep -raliF Sys_FullPath .
./branches/next_ghost/unix/system.cpp
./branches/next_ghost/unix/.svn/text-base/init.cpp.svn-base
./branches/next_ghost/unix/.svn/text-base/system.cpp.svn-base
./branches/next_ghost/unix/init.cpp
./branches/next_ghost/libs/system.h
./branches/next_ghost/libs/memman.cpp
./branches/next_ghost/libs/.svn/text-base/memman.cpp.svn-base
./branches/next_ghost/libs/.svn/text-base/system.h.svn-base
./branches/next_ghost/game/realgame.cpp
./branches/next_ghost/game/music.cpp
./branches/next_ghost/game/globmap.cpp
./branches/next_ghost/game/macros.cpp
./branches/next_ghost/game/gamesave.cpp
./branches/next_ghost/game/.svn/text-base/gamesave.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/skeldal.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/globmap.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/inv.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/dialogs.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/music.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/realgame.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/menu.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/book.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/macros.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/interfac.cpp.svn-base
./branches/next_ghost/game/interfac.cpp
./branches/next_ghost/game/dialogs.cpp
./branches/next_ghost/game/menu.cpp
./branches/next_ghost/game/inv.cpp
./branches/next_ghost/game/book.cpp
./branches/next_ghost/game/skeldal.cpp

real    0m4.747s
user    0m4.616s
sys     0m0.127s
[jardik@Jardik-ArchPC skeldal]$ time /home/jardik/Projects/FindInFiles/findinfiles Sys_FullPath
./branches/next_ghost/unix/system.cpp
./branches/next_ghost/unix/.svn/text-base/init.cpp.svn-base
./branches/next_ghost/unix/.svn/text-base/system.cpp.svn-base
./branches/next_ghost/unix/init.cpp
./branches/next_ghost/libs/system.h
./branches/next_ghost/libs/memman.cpp
./branches/next_ghost/libs/.svn/text-base/memman.cpp.svn-base
./branches/next_ghost/libs/.svn/text-base/system.h.svn-base
./branches/next_ghost/game/realgame.cpp
./branches/next_ghost/game/music.cpp
./branches/next_ghost/game/globmap.cpp
./branches/next_ghost/game/macros.cpp
./branches/next_ghost/game/gamesave.cpp
./branches/next_ghost/game/.svn/text-base/gamesave.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/skeldal.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/globmap.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/inv.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/dialogs.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/music.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/realgame.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/menu.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/book.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/macros.cpp.svn-base
./branches/next_ghost/game/.svn/text-base/interfac.cpp.svn-base
./branches/next_ghost/game/interfac.cpp
./branches/next_ghost/game/dialogs.cpp
./branches/next_ghost/game/menu.cpp
./branches/next_ghost/game/inv.cpp
./branches/next_ghost/game/book.cpp
./branches/next_ghost/game/skeldal.cpp

real    0m0.625s
user    0m0.560s
sys     0m0.063s
[jardik@Jardik-ArchPC skeldal]$

Můj se zdá být cca 7x rychlejší.

[Jardík]

Tak díky tomuto je mé řešení 55x rychlejší a to za to stojí

[disorder]

nepocitas do toho cas pisania programu

[disorder]

skus grep -m1 --mmap -ralF Sys_FullPath .

dalsi rozdiel je, ze preskakujes symlinky, preto som navrhoval find

[disorder]

(nie, ze by spustanie procesov cez find bolo rychlejsie)

[CET]

Samozrejme, clovek nesmi napsat neco jako find . -type f -exec grep ....., ale spis find -type f -print0 | xargs -0r grep .... - to se pak spusti jeden grep s vice souborama najednou, kdyz tam neni extremne moc souboru (nenarazi se na limit delky parametru prikazu), tak se to spusti opravdu pouze jednou.

[Jardík]

Oni v tom adresáři stejně symlinky nejsou (teda alespoň myslím).

[Jardík]

Aha, to "i" pro grep (jak psal člověk výše) když vynechám, tak mám 0m0.132s, ignore case jsem nechtěl. Tak to se omlouvám za nařčení grepu z pomalosti, je jen o kousíček pomalejší. Ten --mmap pro grep nemá žádný přínost, je to furt stejný.

[CET]

Tak samozrejme, zkus si jezte zmenit "F" na "E" a s tim "i" teprve uvidis pomalost Samozrejme, hledani regexpu bude pomalejsi nez porovnavani znak po znaku, a ignore-case to taky zpomaluje.

Na druhou stranu, grep ma mnoho dalsich funkci: puvodne grep vypisuje cely radek, kde se hledany vyraz vyskytuje, ale to jsem zablokoval pomoci "-l"; dale grep umoznuje vypsat radky, kde se hledany vyraz NEVYSKYTUJE "-v"; muzes si nechat zobrazit pouze pocet nalezenych radku; dale je mozne zobrazit X radku pred nalezenym a za nalezenym radkem "-B" a "-A" nebo "-C"; pak taky muzes zadat soubor, ktery obsahuje hledane texty "-F"; muzes si nechat vypsat cisla radek nebo byte offset radku s hledanym textem; muzes urcite, jestli se binarni soubory maji prohledavat nebo se maji brat jako ze text tam nelezen nebyl "-a" a "-I" resp. "--binary-files". Vetsina tehle prepinacu se musi behem behu nejakym zpusobem testovat, takze tam bude spousta dalsich "if" navic, nez ma tvuj programek, takze je samozrejme, ze tvuj program bude rychlejsi. Je to asi neco podobneho, jako kdybys zkousel srovna rychlost tveho programu, ktery spocita "1+1" a zobrazi vysledek a nejakeho jineho programu, ktery umi zpracovat a vypocitat jakykoliv zadany matematicky vyraz.

Takze rychlostne sice grep nepredci, ale kdyz budes chtit pokazde hledat trosku jinym zpusobem (rozumej implementovat nejakou grep funkcionalitu), tak na tom stravic o hodne vic casu a navic skoncis mozna na stejne rychlosti jako grep, nebo mozna jeste hur.

Lepsi nez neco zacnes bastlit, tak si projdi linuxove utilitky (tady tusim vychazel/vychazi nejakej serial o linuxovych utilitkach) a zkus najit nejakou, ktera umi to, co ty chces (v manu pak hledej detaily). Obcas musis svuj pozadavek rozlozit na mensi casti a pak to prohnat pres rouru nekolika utilitkama.

[CET]

A jeste jedna vec. Asi by bylo lepsi opravdu pouzit find, protoze hledat neco v .svn je docela zbytecny. Takze final bych osobne udelal find KDE_HLEDAT -type f -not -path '*/.svn/*' -print0 | xargs -0r grep -lFI HLEDANY bez "-i" a s "-I" (binarni soubory ignorovat).

[Radek Miček]

Pro normální texty a delší vzorky by šel čas zlepšit použitím algoritmu Boyer–Moore–Horspool.

[Jardík]

Super, dík:

real    0m0.141s

[Jardík]

A to jsem nezapnul optimalizace, s -O2 tam je skoro přesně 0.100s.