LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Diskuze: článek Perl (17) - Regulární výrazy - kotvy

Zajímavě hloupý konečný automat
(link)
3.11.2005 10:57
Hynek (Pichi) Vychodil
Věk: ( ~42 let) , Pracovní pozice: software architect , Praxe v IT let: ( ~15 let) , Bydliště: Brno
Řetězec "Perl" je totiž v 1. případě hledán pouze jednou.
Tahle věta mě hodně zarazila. Říkal jsem si, že ta implementace regulárních výrazů nemůže být tak hloupá, aby to v tom druhém případě dělalo fakt dvakrát. Jistě tomu tak není, ale skutečně je v tom nějaký zádrhel a konečný automat vygenerovaný v druhém případě opravdu je složiťejší a pomalejší než v prvním případě. Na delších řeťězcích roste délka prohledávání na deseti a více násobky. Viz jednoduchý test:
#!/usr/bin/env perl
use strict;
use warnings;
use Benchmark qw(:all :hireswallclock);
my $r = 100; # string parts repeat my $i = 1000; # grep repeats my $l = -2; # test for 2 seconds
my $str = 'euiwghiweuh'x$r . 'Perl5' . 'wehjdiuh'x$r . 'Perl6' . 'weiuhiwhjh'x$r; # make string
my %regexps = ( # tested regexps first => qr/Perl(5|6)/o, second => qr/Perl5|Perl6/o, first_nomatch => qr/Perl(?:5|6)/o, );
sub makeRegexpTests (\%) { # make hash of tests from regexps map { # make pairs 'regexp_name' => sub { regexp testing } my $re = $regexps{$_}; # store regexp in local variable $_, # regexp name ( return ('regexp_name', testing function) ) sub { # testing function for (my $c = 0; $c < $i; $c++) { $str =~ m/$re/g; # here can't use $regexps{$_} because value wasn't finded in compile time }; } } keys %{$_[0]} }
cmpthese( $l, # how long/repeats tests { makeRegexpTests %regexps }, # tests );
P.S.: Mimochodem, proč se uvnitř tagu <pre> strácejí prázdné řádky? BTW proč se mi při opakované editaci objeví &lt; převedené na <?
Re: Zajímavě hloupý konečný automat
(link)
3.11.2005 13:45
Hynek (Pichi) Vychodil
Věk: ( ~42 let) , Pracovní pozice: software architect , Praxe v IT let: ( ~15 let) , Bydliště: Brno
Tady je verze pro zkoumani vlivu délky řetězce. Omlouvám se za trošku cryptic způsob zápisu, ale mě to přijde krásně čitelné a už snad ani jinak psát neumím :-)
#!/usr/bin/env perl
use strict;
use warnings;
use Benchmark qw(:all :hireswallclock);
my $l = -2; # test for 2 seconds my @testParams = ( {r=>1, i=>100000}, # r=>string parts repeats, i=>grep repeats {r=>10, i=>10000}, {r=>100, i=>1000}, ); my %regexps = ( # tested regexps first => qr/Perl(5|6)/, second => qr/Perl5|Perl6/, first_nomatch => qr/Perl(?:5|6)/, ); sub testString ($) { # make testing string my ($r) = @_; 'euiwghiweuh'x$r . 'Perl5' . 'wehjdiuh'x$r . 'Perl6' . 'weiuhiwhjh'x$r }
sub makeRegexpTest ($$$) { # make test function my ($str, $re, $i) = @_; # localize parameters for use in testing function sub { # testing function (here $str, $re, $i like constants - see perlsub(1)) for (my $c = 0; $c < $i; $c++) { $str =~ m/$re/g; }; } }
foreach ( @testParams ) { my ($r, $i) = @$_{qw(r i)}; print "r: $r, i: $i$/"; cmpthese( $l, # how long/repeats tests { map +($_, makeRegexpTest testString $r, $regexps{$_}, $i), keys %regexps }, # tests ); }

DISKUZE

Zajímavě hloupý konečný automat 3.11.2005 10:57 Hynek (Pichi) Vychodil
  L Re: Zajímavě hloupý konečný automat 3.11.2005 13:45 Hynek (Pichi) Vychodil




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

13.9.2017 8:00 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

15.5.2017 23:50 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

18.9.2017 14:37 / Rojas
high security vault

15.9.2017 7:33 / Wilson
new zealand childcare jobs

31.8.2017 12:11 / Jaromir Obr
Re: ukůládání dat ze souboru

30.7.2017 11:12 / Jaromir Obr
Národní znaky

27.7.2017 12:24 / Jaromir Obr
Cteni/zapis

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze