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í
×
včera 18:55 | Zajímavý projekt

Společnosti Google, Microsoft, Twitter a Facebook společně představily open source platformu Data Transfer Project (DTP). Cílem platformy je zjednodušit uživatelům přechod a přenos dat mezi jednotlivými online službami. Podrobnosti v pdf a na GitHubu.

Ladislav Hagara | Komentářů: 1
včera 18:33 | Nová verze

Canonical a Microsoft společně oznámili, že PowerShell Core je nově dostupný také jako snap balíček na Snapcraftu. Microsoft uvolnil zdrojové kódy PowerShellu (Wikipedie, GitHub) v srpnu 2016 pod open source licencí MIT a naportoval je na Linux.

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

Novinkou v minor aktualizaci webového prohlížeče Vivaldi je podpora vyhledávače Qwant (Wikipedie). Vývojáři Vivaldi zdůrazňují, že se jedná o evropský vyhledávač respektující soukromí uživatelů.

Ladislav Hagara | Komentářů: 6
včera 01:33 | Nová verze

Po šesti letech od vydání verze 1.0 byla vydána verze 2.0 multiplatformního editoru tagů MusicBrainz Picard (Wikipedie). Přehled novinek, vylepšení a oprav v changelogu.

Ladislav Hagara | Komentářů: 0
19.7. 16:22 | Nová verze Ladislav Hagara | Komentářů: 11
19.7. 15:00 | Komunita

Dnes končí podpora Ubuntu 17.10 Artful Aardvark. Uživatelům je doporučen přechod na Ubuntu 18.04 Bionic Beaver s prodlouženou podporou do roku 2023. Podpora standardních verzí Ubuntu je 9 měsíců. Verze 17.10 byla vydána 19. října 2017.

Ladislav Hagara | Komentářů: 11
19.7. 13:33 | Bezpečnostní upozornění

Společnost Oracle vydala čtvrtletní bezpečnostní aktualizaci svých softwarových produktů (CPU, Critical Patch Update). Opraveno bylo celkově 334 bezpečnostních chyb. V Oracle Java SE je například opraveno 8 bezpečnostních chyb. Všechny jsou vzdáleně zneužitelné bez autentizace. V Oracle MySQL je opraveno 31 bezpečnostních chyb. Vzdáleně zneužitelných bez autentizace je 7 z nich.

Ladislav Hagara | Komentářů: 0
19.7. 13:11 | Zajímavý software

Nick Clifton zveřejnil na blogu společnosti Red Hat věnujícímu se počítačové bezpečnosti nástroj, pomocí kterého lze ověřit, zda jsou binární spustitelné soubory odolné vůči variantě 1 bezpečnostní chyby Spectre v procesorech.

Ladislav Hagara | Komentářů: 0
19.7. 03:00 | Nová verze

Po více než roce vývoje od vydání verze 1.12 byla vydána nová verze 1.13 Java edice počítačové hry Minecraft (Wikipedie). Kódový název nejnovější verze je Update Aquatic. Přehled novinek v oficiálním oznámení o vydání. Detailní přehled novinek na Gamepedii a na YouTube.

Ladislav Hagara | Komentářů: 4
18.7. 23:55 | Nová verze

Společnost Epic Games vydala verzi 4.20 svého proprietárního multiplatformního herního enginu Unreal Engine (Wikipedie). Přehled novinek i s celou řadou obrázků a videi v oznámení na blogu.

Ladislav Hagara | Komentářů: 0
Jak čtete delší texty z webových stránek?
 (77%)
 (20%)
 (5%)
 (7%)
 (2%)
 (10%)
Celkem 371 hlasů
 Komentářů: 40, poslední 29.6. 10:21
    Rozcestník

    Dotaz: bruteforce string matching

    11.8.2017 16:37 exoskeleton
    bruteforce string matching
    Přečteno: 549×
    Dobry den,

    mam mnozinu asi 20mil stringov (dlzka je cca 34 znakov) a hladam sposob ako ich co najrychlejsie porovnat s vygenerovanym stringom.

    momentalne to riesim tak, ze stringy mam ulozene v postgresql (samozrejmostou je btree index) a robim SELECT string FROM strings WHERE string='vygenerovany_string'. Je to bruteforce napisany v c s vyuzitim libpq kniznice, pri ktorom dosahujem cca 170 porovnani/selectov za sekundu.

    zda sa mi 170 porovnani za sekundu malo. rad by som toto navysil o niekolko radov a priblizil sa ku 100000 a viac porovnani za sekundu

    myslite ze sa to da dosiahnut v beznych domacich podminkach? a ak ano ako by sa to dalo vyriesit?

    PS: zacinam uvazovat nad aho-corasick algoritmom ale kjedze nie som developer, bolo by super ine riesenie

    Dakujem

    Odpovědi

    11.8.2017 20:19 rastos | skóre: 61 | blog: rastos
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Zaujímalo by ma, ako by dopadlo riešenie napísané v C s qsort() a bsearch().
    Jan Zahornadsky avatar 13.8.2017 10:32 Jan Zahornadsky | skóre: 22 | blog: hans_blog
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Podle předpokladu velmi dobře -- ono 20M nejsou žádná data a 100k dotazů za sekundu není žádná rychlost.

    V C++ bez vláken mi to dává kolem 500k vyhledání za sekundu s binary_search, s tím vyhledávacím stromem by to bylo ještě víc.
    #include <iostream>
    #include <string>
    #include <functional>
    
    #include <algorithm>
    
    #include <cstdlib>
    #include <ctime>
    
    std::string some_string() {
            char result[35];
            for (int i = 0; i < 34; i++) {
                    result[i] = ' ' + rand() % 64;
            }
            result[34] = 0;
            return result;
    }
    
    
    void measure_time(const std::string &label, std::function<void()> f) {
            clock_t start = clock();
            std::cout << label << std::flush;
    
            f();
    
            clock_t finish = clock();
            std::cout << " - finished in " << ((float)(finish - start)/CLOCKS_PER_SEC) << "s" << std::endl;
    }
    
    int main() {
    
            static const int MAX = 20000000;
    
            std::string *s = new std::string[MAX];
    
            measure_time("String generation", [&s]() {
                    for (int i = 0; i < MAX; i++) {
                            s[i] = some_string();
                    }
            });
    
            measure_time("Sorting", [&s]() {
                    std::sort(s, s+MAX);
            });
    
            static const int LOOKUP_COUNT = 100000;
            std::string *lookup = new std::string[LOOKUP_COUNT];
            for (int i = 0; i < LOOKUP_COUNT; i++) {
                    lookup[i] = some_string();
            }
    
            measure_time("Lookup of 100k new strings", [&s, &lookup]() {
                    for (int i = 0; i < LOOKUP_COUNT; i++) {
                            std::binary_search(s, s+MAX, lookup[i]);
                    }
            });
    
    
            return 0;
    }
    
    Dostávám:
    String generation - finished in 5.90161s
    Sorting - finished in 14.5592s
    Lookup of 100k new strings - finished in 0.188295s
    
    Actually, I was half an hour into the pointer scripting documentation when she got dressed and left.
    14.8.2017 20:11 exoskeleton
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Moc dakujem za pekne riesenie, skusim to prepisat do C.
    Jan Zahornadsky avatar 15.8.2017 21:40 Jan Zahornadsky | skóre: 22 | blog: hans_blog
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Můžu se zeptat proč je nutné, aby to bylo v C? Já bych opravdu použil nějakou templatu, třeba set<string>, bude to hotové na pár řádků a i pokud je nad tím nějaká obsáhlá C logika, tak to stejně nevadí, protože to většinou C++ komilátor zvládne zakomponovat.
    Actually, I was half an hour into the pointer scripting documentation when she got dressed and left.
    15.8.2017 23:00 exoskeleton
    Rozbalit Rozbalit vše Re: bruteforce string matching
    zial nie som programator a existujuci kod je uz napisany v C, tak to budem musiet nejako polepit.
    11.8.2017 22:05 Filip Jirsák | skóre: 67 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Z toho popisu vůbec není jasné, co vlastně řešíte za problém, takže budu jen hádat Pokud máte předem daných 20 milionů řetězců a potřebujete v nich vyhledávat, prostě z těch 20 milionů řetězců nejprve postavte vyhledávací strom, uložte si jej a pak v něm vyhledávejte. Pokud se těch 20 milionů řetězců nemění, použijte trie – pro vyhledávání to bude nejrychlejší a doba sestavení stromu vás nemusí zajímat, budete ho sestavovat jen jednou.
    Jan Zahornadsky avatar 13.8.2017 10:38 Jan Zahornadsky | skóre: 22 | blog: hans_blog
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Podle popisu tipuji, že autor to má napsané v C, ale dotazuje se do databáze -- tam je celkem pravděpodobné, že těch 170 dotazů/s je dáno čistě jenom tím round tripem k SQL serveru. Jinak jak jsem napsal výše, ono i naivní řešení je rychlostí víc než dostačující, teda pokud jsou data v paměti.
    Actually, I was half an hour into the pointer scripting documentation when she got dressed and left.
    14.8.2017 16:58 exoskeleton
    Rozbalit Rozbalit vše Re: bruteforce string matching

    Mate pravdu, je to napisane v C a v databaze je len jeden stlpec s mnozinou 20M stringov. Tento jediny stlpec je zaroven aj primarnym klucom.

    Pointa mala byt v tom ze databaza si sama vsetko zoptimalizuje a vytvori indexy a hladanie/bruteforce bude velmi rychle. Pre mna ako neprogramatora toto mala byt najlahsia cesta/riesenie

    po testoch sa ukazuje ze s roznymi konfiguraciami a optimalizaciami postgresql viem dosiahnut max 170 selectov/pokusov za sekundu

    14.8.2017 18:04 Filip Jirsák | skóre: 67 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Databáze si určitě sama nevytvoří indexy. A u takovéhle úlohy hodně záleží na tom, jak k databázi přistupujete a jak s ní pracujete. Úplně něco jiného bude, když se s každým SELECTem navazuje nové spojení k databázi, ověřuje uživatel a parsuje SQL dotaz, a něco jiného bude, když budete už mít spojení navázané, dotaz bude rozparsovaný a jenom budete měnit parametry dotazu. Ale pro tenhle váš problém není relační databáze vhodné řešení, vy potřebujete fulltextový index, např. Lucene nebo nad ním postavený Solr nebo ElasticSearch. A pokud chcete vyždímat co nejvyšší výkon z jednoho stroje, je velká režie s navazováním spojení k databázi, lepší je nějaké embedded řešení, které můžete mít přímo ve své aplikaci (např. to Lucene). Ostatně, možná kdybyste použil nějakou mapu, slovník nebo hashovací tabulku (záleží na jazyku/knihovně, kdo to má jak pojmenované) ze základní knihovny, třeba v Pythonu, požadovaný výkon z toho vytáhnete a nebudete muset řešit nic speciálního.
    14.8.2017 22:30 exoskeleton
    Rozbalit Rozbalit vše Re: bruteforce string matching
    uvazoval som nad aho-corasick algoritmom alebo nad radix tree, ale to je nad moje programatorske sily. p Zahornadsky ukazal pre mna asi najschodnejsiu cestu.

    popripade este skusim otestovat solr a uvidim, co z toho vypadne.
    Jendа avatar 15.8.2017 15:49 Jendа | skóre: 74 | blog: Výlevníček | JO70FB
    Rozbalit Rozbalit vše Re: bruteforce string matching
    uvazoval som nad aho-corasick algoritmom
    Jako že bys to lineárně prošel? To nebude fungovat - kromě false-positives taky kvůli rychlosti: celé ty tvoje stringy mají 680 MB, a to musíš celé přečíst (a ten automat žere vstup po bajtech).

    Ostatní vyhledávací struktury mají složitost logaritmickou.

    qsort + binární vyhledávání snad zvládneš, ne? A pokud se ti ty stringy, ve kterých vyhledáváš, mění (což jsi pořád ještě nenapsal!), použij červeno-černý strom - například ten z tree(3) nebo z libucw.
    Procesor je napájený přímo ze sítě a používá i její takt.
    15.8.2017 17:01 exoskeleton
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Jedna sa o mnozinu 20mil stringov, do ktorej pribudaju nove len velmi malo. Tj. Da sa povazovat za staticku.
    15.8.2017 20:41 lertimir | skóre: 61 | blog: Par_slov
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Jak píše Jenda. Pokud je to statická monožina tak setřidit a binární vyhledávání. 20 mil < 2^25 takže po setřidění je na vyhledání stringu max 25 porovnání. A při přídání dotřídit qsortem (nebo heap sortem. Klasické algoritmy ze 70-let, jsou algoritmy s matematikou v zádech a také neoptimalizují mnoho cílů současně (jako ta databáze, protože u ní bych spíše čekal datové struktury, které mi, co možná nejvíce efektivně umožní provést join.)
    15.8.2017 15:55 Pali
    Rozbalit Rozbalit vše Re: bruteforce string matching
    Z popisu vyplýva, že by sa malo jednať o presnú zhodu vstupného reťazca s nejakým v zadanej množine.

    Na to vôbec netreba Ahov-Corasickovej algoritmus. Ten si pre zadanú množinu slov pripraví vyhľadávací automat a potom pre vstupný reťazec hľadá všetky výskyty pripravených slov ako podreťazce toho vstupného. Rieši to teda iný problém.

    20 miliónov reťazcov o dĺžke 34 znakov sa ešte vôjde do pamäti. V tomto prípade stačí použiť obyčajný písmenkový strom (Trie), prípadne nejakú komprimovanú variantu. Je to o dosť jednoduchšie ako Ahov-Corasickovej algoritmus.

    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.