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í
×

dnes 21:44 | Nová verze

Organizace Apache Software Foundation (ASF) na svém blogu slaví páté výročí kancelářského balíku Apache OpenOffice jako jejího Top-Level projektu. Při této příležitosti byl vydán Apache OpenOffice 4.1.4 (AOO 4.1.4). Podrobnosti v poznámkách k vydání. Dlouhé čekání na novou verzi tak skončilo.

Ladislav Hagara | Komentářů: 0
dnes 19:22 | Pozvánky

Již příští týden - 26. a 27. října se v Praze v hotelu Olšanka odehraje OpenWRT Summit. Na webu konference naleznete program a možnost zakoupení lístků - ty stojí 55 dolarů. Čtvrtek bude přednáškový a v pátek se budou odehrávat převážně workshopy a meetingy.

Miška | Komentářů: 0
dnes 13:44 | Nová verze

Bylo vydáno Ubuntu 17.10 s kódovým názvem Artful Aardvark. Ke stažení jsou Ubuntu Desktop a Server, Ubuntu Cloud Images, Ubuntu Netboot, Kubuntu, Lubuntu a Lubuntu Alternate, Lubuntu Next, Ubuntu Budgie, Ubuntu Kylin, Ubuntu MATE, Ubuntu Studio a Xubuntu. Podrobnosti v poznámkách k vydání.

Ladislav Hagara | Komentářů: 1
dnes 13:00 | Komunita

MojeFedora.cz informuje, že Fedora 27 dostane podporu pro AAC. Podpora multimediálních formátů je ve výchozí instalaci Fedory tradičně limitovaná kvůli softwarovým patentům, ale desktopový tým Red Hatu se ji i tak snaží v poslední době co nejvíce rozšířit. Už nějaký čas obsahuje kodeky pro MP3, H.264, AC3 a nyní byl přidán také kodek pro další velmi rozšířený zvukový formát – AAC.

Ladislav Hagara | Komentářů: 1
včera 23:55 | Pozvánky

Spolek OpenAlt zve příznivce otevřených technologií a otevřeného přístupu na 145. brněnský sraz, který proběhne v pátek 20. října od 18:00 hodin v restauraci Time Out na adrese Novoměstská 2 v Řečkovicích. Jedná se o poslední sraz před konferencí OpenAlt 2017, jež proběhne o víkendu 4. a 5. listopadu 2017 na FIT VUT v Brně. Běží registrace účastníků.

Ladislav Hagara | Komentářů: 0
včera 21:44 | Nová verze

Byla vydána verze 5.2.0 multiplatformního virtualizačního nástroje Oracle VM VirtualBox. Jedná se o první stabilní verzi z nové větve 5.2. Z novinek lze zmínit například možnost exportování VM do Oracle Cloudu, bezobslužnou instalaci hostovaného systému nebo vylepšené GUI. Podrobnosti v seznamu změn. Aktualizována byla také dokumentace.

Ladislav Hagara | Komentářů: 1
včera 14:00 | Zajímavý projekt

Byl spuštěn Humble Down Under Bundle. Za vlastní cenu lze koupit multiplatformní hry The Warlock of Firetop Mountain, Screencheat, Hand of Fate a Satellite Reign. Při nadprůměrné platbě (aktuálně 3,63 $) také Hacknet, Hacknet Labyrinths, Crawl a Hurtworld. Při platbě 12 $ a více lze získat navíc Armello.

Ladislav Hagara | Komentářů: 0
včera 13:00 | Nová verze

Google Chrome 62 byl prohlášen za stabilní (YouTube). Nejnovější stabilní verze 62.0.3202.62 tohoto webového prohlížeče přináší řadu oprav a vylepšení. Vylepšeny byly také nástroje pro vývojáře (YouTube). Opraveno bylo 35 bezpečnostních chyb.

Ladislav Hagara | Komentářů: 4
včera 11:00 | Zajímavý článek

Článek (en) na Mozilla.cz je věnován vykreslování stránek ve Firefoxu. V průběhu roku 2018 by se ve Firefoxu měl objevit WebRender, jenž by měl vykreslování stránek urychlit díky využití GPU.

Ladislav Hagara | Komentářů: 5
včera 08:22 | Bezpečnostní upozornění

NÚKIB (Národní úřad pro kybernetickou a informační bezpečnost) informuje o zranitelnosti ROCA v procesu generování RSA klíčů, který se odehrává v softwarové knihovně implementované například v kryptografických čipových kartách, bezpečnostních tokenech a dalších hardwarových čipech vyrobených společností Infineon Technologies AG. Zranitelnost umožňuje praktický faktorizační útok, při kterém útočník dokáže vypočítat

… více »
Ladislav Hagara | Komentářů: 4
Jak se vás potenciálně dotkne trend odstraňování analogového audio konektoru typu 3,5mm jack z „chytrých telefonů“?
 (10%)
 (1%)
 (1%)
 (1%)
 (75%)
 (13%)
Celkem 103 hlasů
 Komentářů: 6, poslední dnes 20:51
    Rozcestník

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

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