Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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


In reply to Re^2: Efficient run determination. by Enlil
in thread Efficient run determination. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (3)
    As of 2019-05-26 15:16 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Do you enjoy 3D movies?



      Results (153 votes). Check out past polls.

      Notices?
      • (Sep 10, 2018 at 22:53 UTC) Welcome new users!