comment on

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;
}
[download]

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
[download]

-enlil

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

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Your skill will accomplish what the force of many cannot
	PerlMonks