Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re^2: Efficient run determination.

by Enlil (Parson)
on Mar 08, 2003 at 08:04 UTC ( #241351=note: print w/replies, xml ) Need Help??


in reply to Re: Efficient run determination.
in thread Efficient run determination.

I was looking over the results and I mistakenly put that my first solution was slower than my second one (did I mention that it was late).

Anyhow, I went ahead and used the same benchmarking methods as used by BrowserUK above to see the results for myself except that I wanted to see how different solutions would do under different conditions. So I modified the code a little (both to do a more thorough benchmark (on the Perl only solutions, as the Inline C version is tons faster so no need to beat another dead horse),and also to add my first attempt (Enlil_1)):

#! perl -slw use strict; use Time::HiRes qw( gettimeofday tv_interval ); my $re = ''; $re .="(?:(?:(.)(?:\\$_*))|\$)" for 1 .. 500; $re = qr/$re/o; my @chars = ( "A" .. "Z", "a" .. "z", 0 .. 9, qq( ),qw(! @ $ % ^ & *) + ); for ( 0 .. 100 ) { my $max_size = int(rand(600)) + 2; my $stn = ""; $stn .= @chars[rand @chars] x int(rand(9)) for 1 .. $max_size; my $iterations = int(rand(600)) + 500; print 'STRING:', $stn; print 'Iterations: ', $iterations; print 'Length: ', length($stn); for my $sub ( qw/Enlil_2 Dingus_1 PhiRatE_2 Rasta_1 TommyW_1 Robart +es_1 BrowserUk Dingus_2 Enlil_1/ ){ #! p_process_2/ ) { my $res; my $t0 = [gettimeofday]; for (1..$iterations) { no strict 'refs'; $res = &{$sub}($stn); } printf "%20s: %7.5f sec/iteration found:%3d\n", $sub, tv_inter +val( $t0 )/$iterations, scalar @$res; } } sub BrowserUk { $_ = shift; my @c = m/$re/; $#c = $#- -1; return \@c; } sub Enlil_1 { $_ = shift; my @bah; my $old_pos = 0; while ( /((.)\2*)/g ) { push @bah, [$2,$old_pos,length($1)]; $old_pos = pos(); } return \@bah; } sub Enlil_2 { $_ = shift; my @bah; while ( /((.)\2*)/g) { push (@bah, [$2,$-[1],$+[1] - $-[1]]); } return \@bah; } sub Dingus_1 { my $string = shift; my ($p, $c, $i, @res) = (0, substr($string,0,1)); for ($i=1; $i<length($string); $i++) { next if ($c eq substr($string,$i,1)); push (@res, [$c,$p,($i-$p)]); $c = substr($string,$i,1); $p = $i; } push (@res, [$c,$p,($i-$p)]); return \@res; } sub Dingus_2 { $_ = shift; my (@res, $i, $p); $i = 0; while ( /(.)\1*/g ) { push (@res, [$1, $i, pos()-$i]); $i = pos; } return \@res; } sub Rasta_1 { $_ = shift; my ($pp, $l, @res, $c) = (0, length); while ($pp < $l) { $c = substr $_, $pp, 1; if ( /\G\Q$c\E+/gc ) { push @res,[$c, $pp, pos() - $pp]; $pp = pos; } } return \@res; } sub TommyW_1 { $_ = shift; my ($pos, @triples) = (0); my @reps= /((.)\2*)/g; while (@reps) { my $hits=shift @reps; my $char=shift @reps; push @triples, [$char, $pos, length $hits]; $pos+=length $hits; } return \@triples; } sub Robartes_1 { my $string = shift; my ($currstart, $index, @res) = (0, 0); my @listedstring = split//, $string; my $prev = shift @listedstring; for (@listedstring) { if ($_ eq $prev) { $index++; } else { push @res, [$prev, $currstart, $index-$currstart+1]; $currstart=++$index; $prev=$_; } } push @res, [$prev, $currstart, $index-$currstart+1]; return \@res; } sub PhiRatE_2 { $_ = shift; my ($count, $i, $prev, $next, @res) = (0, 0); $prev = $next = chop($_); while ($next || $prev) { if ($prev eq $next) { $count++; } else { push @res,[$prev, $i=$count, $count]; $prev = $next; $count = 1; } $i++; $next = chop; } return \@res; }

One of the first things that I noticed, is that PhiRate's Perl code is broken, as the while($next||$prev) will return false when two 0's show up in a row (i.e. "00"). Regardless, running this code on both a RH Linux 7.2 running Perl 5.8 (compiled from source) or AS Perl on WinXP Pro Enlil_1 and Dingus_2 were usually neck in neck (when PhiRate's solution returns correctly it is usually close as well though almost always last most of my results slower).

Even when I play around with the $max_size, and the multiplier (the "x int(rand(9))" part), the rankings seem to stay the same.

Here are some results (from both places though I have removed the string as it is sometimes rather long.):

Iterations: 936 Length: 875 Enlil_2: 0.00455 sec/iteration found:190 Dingus_1: 0.00340 sec/iteration found:190 PhiRatE_2: 0.00007 sec/iteration found: 3 Rasta_1: 0.00875 sec/iteration found:190 TommyW_1: 0.00397 sec/iteration found:190 Robartes_1: 0.00673 sec/iteration found:190 BrowserUk: 0.00301 sec/iteration found:190 Dingus_2: 0.00260 sec/iteration found:190 Enlil_1: 0.00260 sec/iteration found:190 Iterations: 602 Length: 1476 Enlil_2: 0.00795 sec/iteration found:330 Dingus_1: 0.00599 sec/iteration found:330 PhiRatE_2: 0.00118 sec/iteration found: 67 Rasta_1: 0.01551 sec/iteration found:330 TommyW_1: 0.00707 sec/iteration found:330 Robartes_1: 0.01159 sec/iteration found:330 BrowserUk: 0.00687 sec/iteration found:330 Dingus_2: 0.00452 sec/iteration found:330 Enlil_1: 0.00471 sec/iteration found:330 Iterations: 1067 Length: 70 Enlil_2: 0.00035 sec/iteration found: 14 Dingus_1: 0.00028 sec/iteration found: 14 PhiRatE_2: 0.00026 sec/iteration found: 14 Rasta_1: 0.00067 sec/iteration found: 14 TommyW_1: 0.00029 sec/iteration found: 14 Robartes_1: 0.00049 sec/iteration found: 14 BrowserUk: 0.00056 sec/iteration found: 14 Dingus_2: 0.00021 sec/iteration found: 14 Enlil_1: 0.00023 sec/iteration found: 14 Iterations: 995 Length: 363 Enlil_2: 0.00182 sec/iteration found: 75 Dingus_1: 0.00140 sec/iteration found: 75 PhiRatE_2: 0.00136 sec/iteration found: 75 Rasta_1: 0.00352 sec/iteration found: 75 TommyW_1: 0.00156 sec/iteration found: 75 Robartes_1: 0.00277 sec/iteration found: 75 BrowserUk: 0.00123 sec/iteration found: 75 Dingus_2: 0.00107 sec/iteration found: 75 Enlil_1: 0.00105 sec/iteration found: 75

-enlil

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://241351]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2019-07-23 11:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If you were the first to set foot on the Moon, what would be your epigram?






    Results (25 votes). Check out past polls.

    Notices?