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 07:43 | Nová verze

Na Steamu se objevil port hry Arma: Cold War Assault (Operation Flashpoint) pro Mac a Linux. … více »

creon | Komentářů: 13
dnes 05:55 | Nová verze

Po 18 měsících od vydání verze 8.0 byla vydána verze 9.0 open source alternativy GitHubu, tj. softwarového nástroje s webovým rozhraním umožňujícího spolupráci na zdrojových kódech, GitLab. Představení nových vlastností v příspěvku na blogu a na YouTube.

Ladislav Hagara | Komentářů: 0
dnes 03:33 | Komunita

Platnost posledního patentu souvisejícího s Dolby Digital (AC-3) vypršela. Po MP3 se tak do Fedory oficiálně dostane také kodek AC-3.

Ladislav Hagara | Komentářů: 3
dnes 00:44 | Komunita

Feral Interactive, společnost zabývající se vydáváním počítačových her pro operační systémy macOS a Linux, nabízí své hry na Steamu vývojářům open source 3D grafické knihovny Mesa zdarma. Podmínkou je minimálně 25 commitů za posledních 5 let. Stejnou nabídku dostali vývojáři knihovny Mesa v roce 2015 od Valve. O rok dříve dostali od Valve tuto nabídku vývojáři Debianu a Ubuntu.

Ladislav Hagara | Komentářů: 0
včera 23:55 | Nová verze

Opera 44, verze 44.0.2510.857, byla prohlášena za stabilní. Nejnovější verze tohoto webového prohlížeče je postavena na Chromiu 57. Z novinek vývojáři Opery zdůrazňují podporou Touch Baru na nejnovějších MacBoocích Pro (gif). Přehled novinek pro vývojáře na blogu Dev.Opera.

Ladislav Hagara | Komentářů: 1
včera 20:56 | Pozvánky

V úterý 28. dubna se koná další Prague Containers Meetup. Přijďte si zopakovat, jak psát kvalitnější Dockerfile a jaké novinky a ulehčení přináší ansible-container, který vám umožní spravovat celý životní cyklus vašeho kontejneru. Místo konání: Concur, Bucharova 11, Praha-Stodůlky.

little-drunk-jesus | Komentářů: 0
včera 17:00 | Nová verze

Po půl roce od vydání verze 3.22 bylo vydáno GNOME ve verzi 3.24 s kódovým názvem Portland. Vydání obsahuje 28 459 změn od přibližně 753 přispěvatelů. Z novinek lze zmínit funkci noční světlo, přepracovaná nastavení, aplikaci Recepty, zdokonalenou oblast pro upozornění nebo zdokonalený webový prohlížeč. Podrobnosti i s náhledy v poznámkách k vydání a v novinkách pro vývojáře a správce systémů.

Ladislav Hagara | Komentářů: 8
včera 11:55 | Humor

Majitelé koček by měli být obezřetní při používání desktopového prostředí XFCE ve výchozím nastavení. Používání XFCE může mást jejich kočky a vést k poškrábání displeje. Jedná se o chybu 12117. K dispozici je již patch.

Ladislav Hagara | Komentářů: 20
21.3. 15:55 | Nová verze

Byla vydána verze 7.5 sady aplikací pro SSH komunikaci OpenSSH. Jedná se o opravné vydání. Volba UsePrivilegeSeparation v sshd_config se stala zastaralou (deprecated). Upozornit lze na změnu formátu log záznamů. Novou verzi OpenSSH již nelze přeložit s upstreamem nepodporovanými verzemi OpenSSL.

Ladislav Hagara | Komentářů: 0
21.3. 14:44 | Nová verze

Byla vydána verze 5.1.0 svobodného integrovaného vývojového prostředí KDevelop. Z novinek lze zdůraznit podporu LLDB. Programátoři mohou nově ladit své programy pomocí GDB nebo LLDB MI. Jedná se o jeden z výsledků Google Summer of Code (GSoC 2016). Zdrojové kódy lze nově přímo z menu KDevelopu analyzovat pomocí nástroje Cppcheck. Přibyla podpora OpenCL. Vylepšena byla podpora programovacího jazyka Python. Přímo z menu lze měnit barevná schémata KDevelopu.

Ladislav Hagara | Komentářů: 6
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (14%)
 (2%)
 (72%)
 (3%)
 (10%)
Celkem 919 hlasů
 Komentářů: 72, poslední 1.3. 11:16
    Rozcestník

    Dotaz: multi regexp

    19.7.2013 14:43 Zaboj Campula
    multi regexp
    Přečteno: 310×

    Zdravim vsechny,

    Vstup

    • Mam mnozinu regularnich vyrazu (radove tisice).
    • a mam jeden textovy retezec.
    Problem
    • Najit alespon jeden regularni vyraz ktery s shoduje s retezcem nebo vratit chybu.
    Jazyk
    • idealne c/c++
    Sekvencni prochazeni vsech regularnich vyrazu a test na shodu je pomale.

    Ma nekdo nejaky napad na chytry algoritmus?

    Odpovědi

    19.7.2013 15:55 Kit
    Rozbalit Rozbalit vše Re: multi regexp
    Spojit těch 1000 regulárních výrazů do jednoho?
    19.7.2013 16:15 extremni lama | skóre: 14 | blog: e_lama
    Rozbalit Rozbalit vše Re: multi regexp
    pokud potrebuje vedet i ktery z nich matchuje tak to nebude tak jednoduchy.

    Napada me treba:

    - nejdriv udelas jeden velky RE, ktery vrati match pokud libovolny z tech 1000 RE by vratil match

    - vyzkousis a pokud najde match, tak:

    - vytvoris si 2 novy RE. Jeden bude spojovat puvodni RE 1 .. 500, ten druhy bude spojovat puvodni RE 501 .. 1000

    - vyzkousis match s kazdym z tech dvou

    - ten ktery vrati shodu znovu rozdelis, atd...

    Ty spojovaci RE by sis mohl predpocitat a umistnit do binarniho stromu, ktery bys potom prochazel od korene k listum...

    Takze bys vzdycky zkousel log2(N) RE.
    The enemy of my enemy is still my enemy.
    19.7.2013 16:20 extremni lama | skóre: 14 | blog: e_lama
    Rozbalit Rozbalit vše Re: multi regexp
    jeste bych doplnil ze tohle by melo fungovat dobre pokud pouzivas regex engine ktery si to vnitrne prevadi na FA.

    Pokud vnitrne pouziva backtracking tak to asi nepomuze...
    The enemy of my enemy is still my enemy.
    19.7.2013 16:18 Zaboj Campula
    Rozbalit Rozbalit vše Re: multi regexp
    To jako kdybych mel dejme tomu regularni vyrazy
    • A.*B
    • A[AB]C
    • D$
    Tak udlat jeden \(A.*B\|A[AB]C\|D$\) To by mozna slo, ale nejsem si jisty jestly by to bylo o moc rychlejsi nez sekvencni prohledavani. Zmerim a dam vedet.
    19.7.2013 16:58 Kit
    Rozbalit Rozbalit vše Re: multi regexp
    Přesně tak. Záleží na kvalitě kompilátoru regulárního výrazu, ale předpokládám řádové zrychlení oproti sekvenčnímu prohledávání.

    Některé jazyky (např. PHP) umožňují zadat regulární výrazy do pole. Netuším, jak je to s rychlostí.
    wamba avatar 19.7.2013 18:00 wamba | skóre: 37 | blog: wamba
    Rozbalit Rozbalit vše Re: multi regexp
    No v Perl-u jsem to zkoušel a dokážu najít případy, kdy to bude rychlejší i o dost pomalejší
    #!/usr/bin/perl
    use 5.010;
    use warnings;
    use strict;
    use List::Util qw{first};
    use Benchmark;
    our $VERSION = 0.001;
    
    my $string =
    '234781802319q8019810328103982104398021483049823094830498023982094823028340932840923830483201223';
    
    my @multiregexp = ( qr{ \A \d+ . \z }msx, qr{ \$ }msx, );
    
    timethese(
        1000000,
        {
            more => sub {
                my $trueregexp = first { $string ~~ $_ } @multiregexp;
            },
            one => sub { my $tt = $string ~~ m{\A \d+ . \z|\$}msx ? 1 : 0; },
            one_better =>
              sub { my $tt = $string ~~ m{\A \d+ . \z|\A .* \$ .* \z}msx ? 1 : 0; },
        }
    );
    
    mi vypíše
    Benchmark: timing 1000000 iterations of more, one, one_better...
          more:  3 wallclock secs ( 2.72 usr +  0.00 sys =  2.72 CPU) @ 367647.06/s (n=1000000)
           one: 14 wallclock secs (13.69 usr +  0.01 sys = 13.70 CPU) @ 72992.70/s (n=1000000)
    one_better: 12 wallclock secs (12.06 usr +  0.00 sys = 12.06 CPU) @ 82918.74/s (n=1000000)
    
    když $string upravím a přidám na konec $, tak
          more:  3 wallclock secs ( 3.21 usr +  0.00 sys =  3.21 CPU) @ 311526.48/s (n=1000000)
           one: 12 wallclock secs (13.74 usr +  0.00 sys = 13.74 CPU) @ 72780.20/s (n=1000000)
    one_better:  1 wallclock secs ( 2.04 usr +  0.00 sys =  2.04 CPU) @ 490196.08/s (n=1000000)
    
    a když smažu q z takto upraveného $string
          more:  3 wallclock secs ( 2.18 usr +  0.00 sys =  2.18 CPU) @ 458715.60/s (n=1000000)
           one:  1 wallclock secs ( 1.39 usr +  0.00 sys =  1.39 CPU) @ 719424.46/s (n=1000000)
    one_better:  0 wallclock secs ( 1.36 usr +  0.00 sys =  1.36 CPU) @ 735294.12/s (n=1000000)
    
    atp.
    This would have been so hard to fix when you don't know that there is in fact an easy fix.
    wamba avatar 19.7.2013 18:51 wamba | skóre: 37 | blog: wamba
    Rozbalit Rozbalit vše Re: multi regexp
    a to first ještě dá na výstup, který ten regexp bude true ještě se to dá otestovat jako
     more_better => sub {
                my $tt = $string ~~ @multiregexp ? 1 : 0;
              }
    
    které je nejrychlejší ve všech předešlých případech
    This would have been so hard to fix when you don't know that there is in fact an easy fix.
    19.7.2013 15:59 Mr.S1lent.cz
    Rozbalit Rozbalit vše Re: multi regexp
    Nebo taky muzes zaindexovat hledany retezec a napsat custom regexp nastroj pro vyhledavani v indexu :)
    19.7.2013 16:25 Zaboj Campula
    Rozbalit Rozbalit vše Re: multi regexp
    Omlovam se, ale nechapu. Slo by ten napad nejak rozvest, abych ho pochopil i ja?
    19.7.2013 18:55 Mr.S1lent.cz
    Rozbalit Rozbalit vše Re: multi regexp
    Zalezi na povaze vstupu, z toho musis vychazet.

    1) je to nahodny retezec vsech pismen nebo jen velkych a malych, cisel, specialnich znaku? 2) regexpy jsou generovany obecne na nejake mnoziny znaku nebo primo na nejaky konkretni retezce?

    To zaindexovani ti odhalim, az ty mi zodpovis tyto dva body, jinak to nema smysl :)
    wamba avatar 20.7.2013 09:59 wamba | skóre: 37 | blog: wamba
    Rozbalit Rozbalit vše Re: multi regexp
    tak abych odpověděl navrhuji použít Perl
    use 5.010;
    use warnings;
    use strict;
    use List::Util qw{first};
    our $VERSION = 0.001;
    
    my $string =
    '23478180231x98019810328103982104398021483049823094830498023982094823028340932840923830483201223$';
    
    my @multiregexp = ( qr{ \A \d+ . \z }msx, qr{ \$ }msx, );
    my $trueregexp = first { $string ~~ $_ } @multiregexp;
    
    say 'tento regexp vyhovuje ', $trueregexp;
    
    a když to nebude dostatečně rychlé, tak to chce vědět více o těch regexp-ech popř. o tom řetězci, aby se dalo navrhnout něco efektivnějšího
    This would have been so hard to fix when you don't know that there is in fact an easy fix.
    23.7.2013 15:51 Zaboj Campula
    Rozbalit Rozbalit vše Re: multi regexp

    Takze dekuji vsem za kometare.

    Spojeni do jednoho velkeho regexpu jak je navrzeno vyse by snad splnilo podminku na rychle vyhledavani, nicmene jsem skoncil na tom ze je potreba i pomerne rychla reakce na to kdyz uzivatel nejaky regulani vyraz prida/ubere/zmeni a konstrukce toho dloooouheho regularniho vyrazu a jeho kompilace je prilis pomala.

    Vysledne reseni je nakonec zalozene na tom, ze ty regularni vyrazy - tedy alespon vetsinaz nich ma v sobe nejaky pevny retezec, napriklad "[0-9]ABC[0-9]" a pomoci techto retezcu lze udelat index a v tom indexu najit podmnozinu regexu ktere se pak matchuji sekvencne. Vetsinou jsou to regexy slozitejsi nez v tom prikladu, ale obvykle to jde a tech par stovek regexu, ze kterych se neda nejaky rozumny retezec vyextraovat se bude prochazet sekvencne az kdyz se nenajde jinde.

    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.