Dotaz: bruteforce string matching

[exoskeleton]

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

[rastos]

Zaujímalo by ma, ako by dopadlo riešenie napísané v C s qsort() a bsearch().

[Jan Zahornadsky]

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

[exoskeleton]

Moc dakujem za pekne riesenie, skusim to prepisat do C.

[Jan Zahornadsky]

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.

[exoskeleton]

zial nie som programator a existujuci kod je uz napisany v C, tak to budem musiet nejako polepit.

[Filip Jirsák]

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]

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.

[exoskeleton]

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

[Filip Jirsák]

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.

[exoskeleton]

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а]

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.

[exoskeleton]

Jedna sa o mnozinu 20mil stringov, do ktorej pribudaju nove len velmi malo. Tj. Da sa povazovat za staticku.

[lertimir]

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

[Pali]

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.