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 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ářů: 2
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ářů: 4
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ářů: 3
včera 01:23 | Zajímavý software

Příspěvek na blogu otevřené certifikační autority Let's Encrypt informuje o začlenění podpory protokolu ACME (Automatic Certificate Management Environment) přímo do webového serveru Apache. Klienty ACME lze nahradit novým modulem Apache mod_md. Na vývoj tohoto modulu bylo uvolněno 70 tisíc dolarů z programu Mozilla Open Source Support (MOSS). K rozchození HTTPS na Apache stačí nově přidat do konfiguračního souboru řádek s ManagedDomain. Minutový videonávod na YouTube [reddit].

Ladislav Hagara | Komentářů: 2
17.10. 14:15 | Komunita

Daniel Stenberg, autor nástroje curl, na svém blogu oznámil, že obdržel letošní Polhemovu cenu, kterou uděluje Švédská inženýrská asociace za „technologickou inovaci nebo důvtipné řešení technického problému“.

marbu | Komentářů: 10
17.10. 13:40 | Pozvánky

Cílem Social Good Hackathonu, který se uskuteční 21. a 22. října v Brně, je vymyslet a zrealizovat projekty, které pomůžou zlepšit svět kolem nás. Je to unikátní příležitost, jak představit nejrůznější sociální projekty a zrealizovat je, propojit aktivní lidi, zástupce a zástupkyně nevládních organizací a lidi z prostředí IT a designu. Hackathon pořádá brněnská neziskovka Nesehnutí.

… více »
Barbora | Komentářů: 1
17.10. 00:44 | Pozvánky

V sobotu 21. října 2017 se na půdě Elektrotechnické fakulty ČVUT v Praze uskuteční RT-Summit – setkání vývojářů linuxového jádra a uživatelů jeho real-time verze označované jako preempt-rt.

… více »
Pavel Píša | Komentářů: 8
Jak se vás potenciálně dotkne trend odstraňování analogového audio konektoru typu 3,5mm jack z „chytrých telefonů“?
 (13%)
 (2%)
 (0%)
 (2%)
 (73%)
 (11%)
Celkem 62 hlasů
 Komentářů: 4, poslední včera 21:50
    Rozcestník

    Dotaz: bruteforce string matching

    11.8. 16:37 exoskeleton
    bruteforce string matching
    Přečteno: 520×
    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. 20:19 rastos | skóre: 60 | 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.
    15.8. 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. 20:41 lertimir | skóre: 60 | 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. 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.