abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 0
dnes 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
včera 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 8
včera 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 8
včera 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 2
včera 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
včera 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 0
včera 00:10 | Nová verze

Byla vydána verze 3.2 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata. Z novinek lze zmínit například podporu protokolů DNP3 a CIP/ENIP, vylepšenou podporu TLS a samozřejmě také aktualizovanou dokumentaci.

Ladislav Hagara | Komentářů: 0
1.12. 21:00 | Nová verze

Byla vydána beta verze Linux Mintu 18.1 s kódovým jménem Serena. Na blogu Linux Mintu jsou hned dvě oznámení. První o vydání Linux Mintu s prostředím MATE a druhé o vydání Linux Mintu s prostředím Cinnamon. Stejným způsobem jsou rozděleny také poznámky k vydání (MATE, Cinnamon) a přehled novinek s náhledy (MATE, Cinnamon). Linux Mint 18.1 bude podporován až do roku 2021.

Ladislav Hagara | Komentářů: 0
1.12. 16:42 | Nová verze

Byl vydán Devuan Jessie 1.0 Beta 2. Jedná se o druhou beta verzi forku Debianu bez systemd představeného v listopadu 2014 (zprávička). První beta verze byla vydána v dubnu letošního roku (zprávička). Jedna z posledních přednášek věnovaných Devuanu proběhla v listopadu na konferenci FSCONS 2016 (YouTube, pdf).

Ladislav Hagara | Komentářů: 0
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 763 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

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

8.1.2014 12:34 gsnak | skóre: 19 | blog: gsnak
Rychle hľadanie či sa retazec nachadza v poli v C
Přečteno: 1072×
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).
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL

Řešení dotazu:


Odpovědi

8.1.2014 13:18 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
8.1.2014 13:33 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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).
8.1.2014 14:21 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
No neviem ci ma zmysel setrit pamat, ma to len nejakych 300 MB v pamati.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
8.1.2014 15:56 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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á.
8.1.2014 13:23 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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...
9.1.2014 08:11 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
8.1.2014 13:54 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
8.1.2014 14:24 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Mas pravdu, je to 0.3us, nie 1ms, cize bisekcia je asi milion krat rychlejsia. Na porovnavanie pouzivam strcmp.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
8.1.2014 15:25 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
8.1.2014 15:36 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
8.1.2014 15:51 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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).
8.1.2014 16:19 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
8.1.2014 18:47 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
8.1.2014 16:10 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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š.
8.1.2014 16:23 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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?
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
8.1.2014 18:28 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Samozrejme jde o paralelismus ve smyslu vice hledani provadenych paralelne, pokud by delal jedno hledani, tak by mu asi 0,3us stacilo:-)
8.1.2014 19:35 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
9.1.2014 08:12 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Ano formuloval si to presne.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
11.1.2014 18:57 extremni lama | skóre: 14 | blog: e_lama
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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 :-)
The enemy of my enemy is still my enemy.
11.1.2014 19:57 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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ěří.
11.1.2014 20:32 extremni lama | skóre: 14 | blog: e_lama
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
K [*]: neni to tak protoze prumer z logaritmu != logaritmus z prumeru :-)

Ale jinak mas pravdu a asi se to nevyplati.
The enemy of my enemy is still my enemy.
11.1.2014 20:51 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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
11.1.2014 21:32 extremni lama | skóre: 14 | blog: e_lama
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v 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"...
The enemy of my enemy is still my enemy.
15.1.2014 18:56 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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...
16.1.2014 01:50 extremni lama | skóre: 14 | blog: e_lama
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
The enemy of my enemy is still my enemy.
11.1.2014 20:58 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C

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.

11.1.2014 21:29 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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...
11.1.2014 21:43 extremni lama | skóre: 14 | blog: e_lama
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Good idea. Asymptoticka slozitost se asi nezlepsi oproti hledani prvku jednotlive, ale mohlo by se zlepsit chovani cache.
The enemy of my enemy is still my enemy.
8.1.2014 19:06 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C

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?

To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
8.1.2014 20:21 trilobyte | skóre: 1 | blog: podtrzitko
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Uz to ma setrideny predem, ale 0.3 us na hledani je moc dlouho :).
8.1.2014 20:43 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Teď už jsem to našel, nějak mi to v diskuzi uniklo :), v dotazu je 1sec a 1ms což mě zmátlo.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
9.1.2014 10:15 Tomáš
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C

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 avatar 9.1.2014 12:55 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
Hello world ! Segmentation fault (core dumped)
9.1.2014 17:50 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C

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.

To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
10.1.2014 10:09 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
10.1.2014 10:40 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
10.1.2014 13:14 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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).
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
10.1.2014 14:03 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
10.1.2014 14:43 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
10.1.2014 15:05 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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...
10.1.2014 15:43 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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í).
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
11.1.2014 11:59 potato
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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()).
10.1.2014 15:51 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
10.1.2014 14:51 Tomáš
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C

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?

10.1.2014 15:53 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
94%. resp. 6% su false positive ktore dohladavam cez bisekciu alebo hash table.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
12.1.2014 22:27 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C

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é“).

To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
14.1.2014 12:23 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Příloha:
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.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
14.1.2014 14:36 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
A to je za 1M (dle POCET 1000000 v nahodne_data.c) ne za 10M? (s 35 znaky).
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
14.1.2014 15:49 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Ano.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
14.1.2014 15:50 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
Potom je to samozrejme podelene takze toto je za 1 hladanie.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
14.1.2014 16:10 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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“.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
14.1.2014 16:43 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.

15.1.2014 08:11 gsnak | skóre: 19 | blog: gsnak
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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.
DOGE: DE7q1kxqvoFek7UGWBWBt47QWJTRBqVNLL
Josef Kufner avatar 15.1.2014 12:26 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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í.
Hello world ! Segmentation fault (core dumped)
15.1.2014 13:01 axel
Rozbalit Rozbalit vše Re: Rychle hľadanie či sa retazec nachadza v poli v C
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...

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.