Dotaz: Rychle hľadanie či sa retazec nachadza v poli v C

[gsnak]

Mam konecne a nemenne pole 10 milionov retazcov, maju dlzku cca 30-35 znakov. Potrebujem vytvorit funkciu ktora by rychlo testovala ci sa nejaky retazec nachadza v tomto poli.

Najprv som to prehladaval sekvencne, to trvalo asi 1s. Potom som to zoradil a pouzivam bisekciu (zacnem v polovici, porovnam retazec, ak je mensi hladav v stvrtine, atd. az bud najdem co tam je alebo nie). No aj tak sa mi to zda dost pomale, jeden test trva asi 1ms.

Existuje v cistom C nejaka kniznica ktora by mi umoznila hladat rychlejsie ako tou bisekciou? Skusal som aj mysql ale je to pomale (kvoli rezii).

---

---

Odpovědi

[Michal Kubeček]

Můžete zkusit trie. Možná by na urychlení stačila i prostá hashovací tabulka, kde byste měl pověšené stromy pro jednotlivé hodnoty hashe.

[potato]

Jo, trie jmenuje ta věc, co jsem si nemohl vzpomenout... Pro pevné řetězce je DAFSA/DAWG ještě lepší z hlediska redukce velikosti dat (a v důsledku typicky zlepšení vzoru přístupu k paměti).

[gsnak]

No neviem ci ma zmysel setrit pamat, ma to len nejakych 300 MB v pamati.

[potato]

Má tvůj procesor L2 cache výrazně větší než 300 MB? V tom případě gratuluji, ale pro nás běžné smrtelníky výrazná redukce working set význam má.

[potato]

To se běžně dělá pomocí nějakého typu hashe. Pro předem známé řetezce lze vygenerovat perfektní hashovou tabulku (perfect hash table), tedy bez kolizí, pomocí gperf(1), s deseti miliony řetězců jsem to tedy nezkoušel. Kromě toho existují například specializované stromové struktury na takovéhle vyhledávání, které zároveň redukují velikost representace, ale pro začátek zkus ten hash...

[gsnak]

Nasiel som priamo v glibc funkciu hcreate a hsearch, pomocou toho je to o 20% rychlejsie ako bisekcia, este skusim napisat vlastnu implementaciu hash table.

[axel]

Nezda se mi byt mozne, ze by prohledani pulenim (rekneme 25 porovnani) bylo jen tisickrat rychlejsi nez sekvencni (10 milionu porovnani). Trivialne lze napriklad pridat pole o 1000 prvcich vybranych z pozic v poli, jehoz prohledanim (pulenim) zjistis jiz mensi cast pole o 10000 prvcich pro dalsi hledani - tim se vyhnes castemu preskakovani ve velkem rozsahu pameti, coz muze optimalizovat pristupove doby. Algoritmicky nic lepsiho nez puleni nehledej, spise bych se zameril na implementaci retezcu (jak jsou alokovane, jak se porovnavaji), zpusob reprezenatce a prochzeni pole apod., tzn. technologicke aspekty.

[gsnak]

Mas pravdu, je to 0.3us, nie 1ms, cize bisekcia je asi milion krat rychlejsia. Na porovnavanie pouzivam strcmp.

[axel]

Pokud ti takova rychlost opravdu nestaci, tak se to muzes pokusit poladit napr. nahradou strcmp za memcmp, zmenou reprezentace (nepises zda retezce jsou dynamicky alokovane) apod., jak se to projevi je vzdy otazka konkretni platformy. Vyznamne muze pomoct paralelizace.

[gsnak]

Retazce su dynamicky alokovane, pouzil som jednosmerny spojovy zoznam ktory obsahuje char *data, a void *next. Jak by to malo vyzerat staticky? Mam cely subor konvertovat na .h subor? To bi mala binarka 350 MB, znie to dost sialene, asi to vyskusam :D

[axel]

Psal jsi o poli a je to spojovy seznam? A jak se v nem realizuje to puleni???

Co by mela byt konverze na .h soubor nechapu, pole je samozrejme treba alokovat dynamicky, ale jde o to, zda to je pole odkazu na dynamicky alokovane retezce, nebo to je dvourozmerne pole (napr [1000000][35] - v takovem pripade by bylo asi vhodnejsi udelat treba 1000 mesich poli a na se odkazovat z predpripraveneho mesniho pole obahujiciho prvni prvek pole, jak jsem naznacoval vyse).

[gsnak]

Myslim ze v povodnej verzii som mal spojovy zoznam a ten som potom vymenil za pole (Vazne uz teraz si nie som isty ci je to pole, ale ked tam je [] tak snad ano, nieco ako "Delala jsem knedlik a vysel mi nok"). To pole nacitavam takto, myslim ze je to OK:

char **items = (char**)malloc(sizeof(char*)*POCET_ZAZNAMOV);
for (i=0; i<POCET_ZAZNAMOV; i++) {
  items[i] = (char*)malloc(sizeof(char)*35);
  ... nacitam items[i] zo suboru
}

Vecer asi skusim tie hashe.

[axel]

Takto bych to urcite nedelal. Alokoval bych si pamet naraz a pouzival to jako dvourozmerne pole. Spotrebujes mene pameti a usetris dereferenci - na pole[i] uz pak mas rovnou retezec, zatimco v tvem reseni tam mas pointer, ktery teprve smeruje na retezec. Samozrejme to znamena i omezeni, protoze tak velky souvisly blok pameti nemusi byt k dispozici (pak bych si alokoval vice mensich poli), zalezi ale k cemu to ma cele slouzit.

[potato]

Při těchto časech jsou kritické vzory přístupu do paměti. Jeden L2 cache miss stojí běžně přes 100 cyklů CPU, může stát i 200. Takže důležité je držet data kompaktní a/nebo omezit náhodný přístup po všech končinách paměti.

Z tohoto pohledu může vycházet perfektní (nebo skoro perfektní) hashová tabulka dobře. Sice skoro každé hledání znamená jeden L2 cache miss, protože je velká a přístup je náhodný, ale nemělo by jich být víc.

Paralalizace je v tom případě na nic. Na výpočtu hashe pro 30znakový řetězec (dělá se jednou) ani porovnání dvou 30znakových řetězců (dělá se typicky taky jednou) toho moc smysluplně nezparalelizuješ.

[gsnak]

Ok, ale to plati len ak robis jedine hladanie. Ak robis viac roznych hladani za sebou tak aj tak velmi skoro "osahas" aj tak celu pamat, takze nejake vyhybanie sa blokom pamate asi nema vyznam?

[axel]

Samozrejme jde o paralelismus ve smyslu vice hledani provadenych paralelne, pokud by delal jedno hledani, tak by mu asi 0,3us stacilo

[potato]

Předpokládal jsem, že to potřebuje sice často, ale postupně. Kdyby byl problém formulován: Mám jednu velmi velkou, ale známou množinu řetězců a druhou ne tak velkou, zato neznámou. Potřebuji v té druhé najít ty, které jsou prvky i první. Tak to by byla jiná úloha, i když by sekvenční testování přítomnosti nakonec třeba byl nejlepší postup.

[gsnak]

Ano formuloval si to presne.

[:::]

Pokud je to takhle tak bys to mohl optimalizovat tak ze bys tu druhou, mensi mnozinu seradil vzestupne. Potom prvni retezec bys hledal v celym prvnim poli. Druhy retezec bys hledal jenom od indexu prvniho retezce do konce pole, atd. Takze s kazdym dalsim retezcem bys prohledaval mensi cast toho velkyho pole.

Snad jsem to vysvetlil jasne

[potato]

Vzhledem k logaritmické složitosti bisekce se to těžko vyplatí (u hashování ani nemluvě). Pokud má velká pevná množina N prvků, hledaná M prvků, tak prosté testování potřebuje O(M log2(N)) porovnávacích operací. Postupným zkracováním se to sníží pouze trochu na O(M (log2(N) - 1)) [*], zato potřebuješ O(M log2(M)) operací navíc na to setřídění. Takže zaplatíš víc, než ušetříš, protože M < M log2(M). Ignoroval jsem teď konstantní faktory, ale ty by se zde neměly řádově lišit.

Celkově mě nenapadá žádný preprocessing, který by nestál víc, než pak dokáže ušetřit při testování přítomnosti v té velké pevné množině.

[*] Jak laskavý čtenář sám snadno ověří.

[:::]

K [*]: neni to tak protoze prumer z logaritmu != logaritmus z prumeru

Ale jinak mas pravdu a asi se to nevyplati.

[potato]

Tvrzení, že průměr z logaritmů není logaritmus průměru, je pravidvé, ale nijak nevyvrací, co jsem napsal.

∫ log(x) dx = x(log(x) - 1) + C

[:::]

To plati pro prirozeny log. U log2 to jeste bude nasobeny konstantou.

U O notace sice na konstantach nezalezi, ale kdyz uz je tam ta "- 1"...

[potato]

Některým lidem se nezavděčíš. Ano, máš pravdu, neměl jsem používat O-notaci, protože ‚asymptoticky a až na konstantu‘ tam rozdíl není žádný. Přiště asi budu muset v rámci takového příspěvku do diskuse napsat desetistránkový článek s kompletním důkazem a odvozením počtu operací včetně všech konstant...

[:::]

jak se na to divam tak ta "- 1" je tam dulezitejsi nez ta druha konstanta, protoze se s ni nasobi M.

Tu poznamku o nespravnosti jsem napsal po priblizne nasledujici uvaze:

log2(N) - 1 == log2(N/2) == log2(average of uniform distribution) ==> takhle to prece nemuze pocitat

uz jsem ale nezkontroloval ze i jinym zpusobem se nahodou dostanes ke stejnymu vysledku.

Takze to tady asi muzeme ukoncit s tim ze je to spravne.

[Michal Kubeček]

Když už takhle, tak už by (za předpokladu rovnoměrného rozložení řetězců) bylo efektivnější to menší pole také půlit, tj. nejdřív najít prostřední prvek a pak aplikovat totéž na levou a pravou polovinu kratšího pole.

Případně pokud sekvenčně, tak ale nepůlit, ale vycházet z toho, že má-li dlouhé pole n prvků a krátké k, měli bychom první prvek hledat spíš kolem pozice n/k (možná dokonce spíš n/2k, nechce se mi to teď počítat) než n/2. Obdobně pak v dalších krocích.

[potato]

Půlení menšího pole zkracuje čas z c*M*log2(N) na přibližně 2c*M*log2(N/M). Což je pěkné, ale v podstatě to akorát kompenzuje čas potřebný ke třídění, který je c'*M*log2(N/M). S ignorováním konstant (2c ≈ c') mám dohromady 2c*M*(log2(N/M) + log2(M)) = 2c*M*log(N), jsme tedy zase tam, co na začátku.

Odhad polohy ‚metodou sečen‘ je otázka, jak bude fungovat pro stringy...

[:::]

Good idea. Asymptoticka slozitost se asi nezlepsi oproti hledani prvku jednotlive, ale mohlo by se zlepsit chovani cache.

[Šangala]

Rozumím tomu dobře, že hledáš jen přesnou shodu položky pole s hledaným řetězcem a že to pole máš a řešíš jen rychlost vyhledání?

Jsem z toho trochu zmatený, píše se tady o haších apod., ale pokud vezmu takovouto zahrádku (rozuměj malé políčko 10M × 42 znaků ;)), pomocí qsort jej setřídím (náročné na čas ≈12sec), tak pomocí třeba bsearch hledám velmi hluboko pod 1 sec (0.000006) - vždyť je to jen 23 porovnání - co jsem nepochopil?

[trilobyte]

Uz to ma setrideny predem, ale 0.3 us na hledani je moc dlouho :).

[Šangala]

Teď už jsem to našel, nějak mi to v diskuzi uniklo :), v dotazu je 1sec a 1ms což mě zmátlo.

[Tomáš]

Jak již kdosi zmínil, prvním krokem je použití hashovací funkce. Řetězec přeložíte na číslo K, které vám přímo určí index do pole. V poli pak máte (druhé velmi malé) pole (možná spíše spojový seznam) řetězců, které již sekvenčně porovnáte se zadaným řetězcem. V zásadě je to místo bi-sekce ( dělení na půl ) dělení na N, kde N je počet různých K, které vylézají z hash funkce.

Asi bych zamířil směrem k perfect hash funkci a snažil se tak vyhnout prohledávání druhého (malého) pole. Můžete třeba zkusit gperf.

Pokud by vám hashování nestačilo a počet úspěšných testů na shodu byl malý (<20%), tak můžete zkusit nasadit Bloomův filter. Tím by jste si mohl ušetřit, 90% práce s pamětí a fungovat jen na úrovni CPU cache.

[Josef Kufner]

Pokud se ti množina prohledávaných řetězců nemění, můžeš mít kolizní řetězce také v poli a aplikovat v druhém kroku bsearch. Celková složitost hledání je pak cca. 1 + log_2(N/velikost hash tabulky), při rovnoměrném rozložení stringů v hash tabulce.

[Šangala]

Obecně věc takto napsaná pod 10µs už nemá rozhodně cenu řešit, protože pokud se to má používat jednou, tak je jedno jestli je to 10µs nebo 10ms (tedy v 99.99% případů). Obecně to lze zrychlit práci s pamětí nebo segmentací, 24 iterací je prostě nic, režie jsou jinde.

No a pokud se to má používat opakovaně ve velkém, tak jsou mnohem důležitější věci v tom opakovaně, které daleko zásadněji ovlivní výslednou rychlost. V tomto případě, i cache na CPU a jak se rozdělí vlákna na Multi-Core-HT CPU.

bsearch může klidně na 100 záznamech produkovat stejný čas jako na 10000 apod.

[gsnak]

Tak som skusil bloom filter a zrychlilo sa to asi o 20%. Ak bisekcia zabera 100%, tak hashtable 80% a bloom 60% nad mojimi datami. Este sa pohram s vyberom hashovacich funkcii.

[Šangala]

Jen pro zajímavost, jaké máš časy a na jakém CPU.
A jestli je to čas jednoho hledání nebo třeba 100-vky a následně podělené.
Dík.

[gsnak]

Je to jednojadrovy Intel Atom. Mal som milion retazcov dlzky cca 35 znakov, pri prvom teste som hladal kazdy retazec (t.j. milion hladani a kazdy sa ma najst). V druhom teste som hladal naopak retazce ktore sa tam nenachadzaju. Casy som potom podelil (celkovy cas testu / 1 milion). Druhy test: 0.8us bisekcia, 0.6us hashtable, 0.5us bloom+falback na bisekciu, 0.4 bloom+fallback na hashtable. Prvy test mal podobne casy len bloom bol cca 2x pomalsi ako bisekcia (lebo sa nasli vsetky takze to je ciste cas bloom + cas fallbacku).

[potato]

To je Atom tak pomalý, nebo máš pomalé hashování? Zkoušel jsem cvičně narvat 10M náhodných řetězců o délce 35 znaků do GHashTable se standardními GLib hashovacími funkcemi (výroba tabulky tedy chvíli trvala, částečně taky kvůli pomalému RNG). Test přítomnosti trvá v průměru asi 140 ns -- na Phenomu II. To je ale generický g_hash_table_lookup(), takže se přitom používá indirekce, volání funkcí tam a zpět, řetězce jsou alokované bokem, ... Hard-coded implementace musí IMO být pod 100 ns.

[Šangala]

No zas to nepřeháněj :), fčul jsem si jen rubnul na NTB i7 pod Cygwin-em bsearch nad 10M int-ů a mám 12 až 21nsec existujících a neexistujících 60 až 110nsec. Atom bude asi mít o kus nižší takt než Phenom II (a o ten tady jde), takže bych byl opatrnější s tím pod 100ns.

[potato]

Pravda, testoval jsem téměř výhradně neexistující. Existující jsou u stringů o něco pomalejší, protože vždy vyžadují alespoň jeden kompletní strcmp(). Neexistující se mohou trefit do prázdného místa tabulky, případě může strcmp() rychle skončit. Ale pořád někde lítá faktor rychlosti alespoň tak 3...

[Šangala]

Použl bych raději memcmp() když už se honí každý tick.
A doplním k mým číslům, a bsearch nad int, klasický bsearch má vždy plný počet kroků při neexistenci, při existenci jich může mít méně (záleží na implementaci, ale řekl bych, že se obecně používají tak dvě, které to dělají).

[potato]

Jak jsem psal, zkusil jsem to jako jednoduchý test, protože mi 600 ns přišlo hodně. Takže nejenže se používala strcmp(), ale volala se přes funkční pointer a skrz další funkci (g_str_hash()).

[gsnak]

pouzil som hash table z glibc (hcreate, hsearch), tam sa hash zvolit neda takze neviem aky hash je tam pouzity, GHashTable z glib urcite vyskusam.

[Tomáš]

Můžu se zeptat kolika bitový bloom filter jste použil? Zrychlení na na 4/6 u mezi variantami bloom+hash vs. hash u 100% neshody se mi zdá málo. Čekal bych o něco lepší výsledek. Jaká byla úspěšnost bloomova filtru?

[gsnak]

94%. resp. 6% su false positive ktore dohladavam cez bisekciu alebo hash table.

[Šangala]

Trošku mě to zajímalo (někdy je třeba se nudit ;)), tak jsem si to zkusil bez „woodoo“ a „pracně“ :) (jen přímým indexováním a qsort a bsearch).
Časy jsou v nano-sekundách na záznam při 10M záznamech délky 30-35 znaků (délky 30-35 rovnoměrně obsažené) náhodně vygenerovaných z 58 znaků (nejčastější běžné znaky).

V prvním sloupci jsem provedl rozdělení dle délky (tedy rozdělení na 6 množin) /všechny uváděné časy jsou 'existující-neexistující'/,

v druhém sloupci jsem přidal index podle prvního písmena (díky náhodnému generování dochází k velmi rovnoměrnému rozložení - máme 6 rovnoměrný nadskupin, 6*255 podksupin kde v 6*58 je to rovnoměrně rozložené) a

v třetím jen velmi jednoduše přidal OpenMP na hledací smyčku.

Časy v závorce jsou pro řetězce obsahující 1-255 znaky (binární string bez '\0'), díky lepšímu rozložení se to pak trochu zkracuje/rovnoměrně dělí do 6*255 skupin.

Každé hledání používá fci strlen() pro zjištění délky momentálně hledaného řetěze, bez zjišťování délky jsou hodnoty v [ ] (Byť jsem se snažil dělat testy na systému v klidu, jak vidno záleží na aktuálním stavu, bo ne vždy to mělo logický efekt).

                                              Length   1st Letter  1st Letter-MP
Intel(R) Atom(TM) CPU N270       @ 1.60GHz    2689-3475   871-891     918-918 [923]?    
Intel(R) Core(TM)2 CPU 6600      @ 2.40GHz    1167-1496   410-411     167-175 [141] (153-154 [117])
Intel(R) Core(TM) i7 CPU M 640   @ 2.80GHz     782-1118   110-112      64- 67 [ 68]? 
*Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz 2×  536- 723   134-134      74- 68 [ 58]  
*Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz 8×  541- 729   102-102      34- 36 [ 29]  (30- 32 [ 24]) 

Atom je jednojádro HT, 2. je Core2Duo,3 je NTB i7, a Xeon čtyř-HT-jádro, ale ve virtuálu poprvé přidělení 2×CPU podruhé 8×CPU (ale je v zasadě jedno jestli 4 nebo 8 jádra nebo 4-16 povolených threadů, na toto HT nepomáhá, časy byly „stejné“).

[gsnak]

Příloha:

• test2.tar.gz (5523 bytů)

Spravil som nejake demo, je to v prilohe, tu je vysledok na mojom stroji:

CPU: Intel(R) Atom(TM) CPU D410   @ 1.66GHz
Mem: 1996, Free: 494
	
Vsetky  Ziadne  Algoritmus

0.764us 0.846us bisect
0.656us 0.523us hsearch
1.306us 0.535us bloom+bisect (miss 100.00%, 1.97%)
1.168us 0.514us bloom+hsearch (miss 100.00%, 1.97%)
0.539us 0.459us GHashTable

Prvy stlpec udava primerny cas 1 hladania ak sme hladali len take hodnoty ktore sa v poli nachadzaju. Druhy stlpec udava cas 1 hladania ak sme hladali len take hodnoty ktore sa v poli nenachadzaju. Udaj v zatvorke u bloom udava kolko krat vratil pozitivny vysledok v prvom a druhom stlpci. Napr. u mna v 2% vysledkov bloom filter vratil false positive.

Kompilujte takto: make && make data && make test run

Zda sa teda ze GHashTable je najrychlejsia.

[Šangala]

A to je za 1M (dle POCET 1000000 v nahodne_data.c) ne za 10M? (s 35 znaky).

[gsnak]

Ano.

[gsnak]

Potom je to samozrejme podelene takze toto je za 1 hladanie.

[Šangala]

Jasan, jen jsem se zarazil, protože mi to vůbec nesedělo s tímto, tak jsem se jukl do zdrojáku a na 1M „může být“.
Čekal bych, že by se ti víc měly otevřít nůžky v rozdílech na 10M záznamech.
PS: Těch záznamů je docela málo a píšeš „neměnné“, možná to lze i zrychlit specifickým hledáním, pro ta data. Může být zásadní rozdíl mezi „náhodná data“ a „tvoje data“.

[axel]

Pro zajimavost u mne pro 1Mx35 (cygwin na Win7):

CPU: Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz
/bin/sh: free: command not found

Vsetky  Ziadne  Algoritmus

0.184us 0.203us bisect
0.255us 0.238us hsearch
0.336us 0.157us bloom+bisect (miss 100.00%, 1.97%)
0.407us 0.154us bloom+hsearch (miss 100.00%, 1.97%)
0.233us 0.155us GHashTable

pro 10Mx35:

CPU: Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz
/bin/sh: free: command not found

Vsetky  Ziadne  Algoritmus

0.212us 0.231us bisect
0.281us 0.287us hsearch
0.390us 0.178us bloom+bisect (miss 100.00%, 1.99%)
0.469us 0.181us bloom+hsearch (miss 100.00%, 1.99%)
0.276us 0.179us GHashTable

pro 1Mx250:

CPU: Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz
/bin/sh: free: command not found

Vsetky  Ziadne  Algoritmus

0.267us 0.224us bisect
0.659us 0.593us hsearch
0.849us 0.602us bloom+bisect (miss 100.00%, 1.99%)
1.247us 0.602us bloom+hsearch (miss 100.00%, 1.99%)
0.597us 0.444us GHashTable

zkusil jsem puvodne 1Mx350, ale padlo mi na segfault.

[gsnak]

Padlo to lebo v nacitaj_data.c je char s[256]. Zaujimave je ako velmi na to vplyva dlzka retazca, necakal som ze to bude mat az taky vplyv.

[Josef Kufner]

Délka řetězců může rozhodnout o tom, zda se ti to vejde do cache nebo ne. V takovém případě nastane od určité délky výrazný propad, ale jinak ta závislost rychlosti na délce řetězce bude téměř konstantní.

[axel]

Pri techto casech maji takove veci velky vliv. Zatimco hash se pocita z celeho retezce (nemusi, ale dela se to tak), porovnani na neshodu se (na datech, jak se generovala) nezmeni. Je to spis otazka hrani si s optimalizacemi nez nejakeho principu. Pokud maji data napr. nejakou zvlastni vlastnost, zamerenim se na ni pri optimalizaci se to muze extremne zlepsit. V tomto pripade napr. mame nahodna data nad domenou cca 50 znaku, dal by se napsat natvrdo kod, ktery by treba prvni a druhe pismeno rozhazoval do samostatnych poli a teprve v nich by se pulilo apod., opet by to prineslo nejaky ten tik...