in reply to Finding all substrings

One small optimization you may do is to keep a temporary variable instead of calling length() at each iteration of each loop: 
sub substrings {
  my $string = shift;
  my @result = ();
  my $strlen = length $string;
  foreach my $length (1..$strlen) {
    foreach my $offset (0..$strlen-$length) {
      push @result, substr($string,$offset,$length);
    }
  }
  return @result;
}

[download]

Replies are listed 'Best First'.
Re: Re: Finding all substrings
by broquaint (Abbot) on Apr 24, 2002 at 18:12 UTC
    Actually it makes it ever so slightly slower, much to my surprise :-/ 
    use Benchmark qw(cmpthese);

sub substrings_TheHobbit {
  my $string = shift;
  my @result = ();

  foreach my $length (1..length($string)) {
    foreach my $offset (0..length($string)-$length) {
      push @result,substr($string,$offset,$length);
    }
  }
  return @result;
}

sub substrings_thelenm {
  my $string = shift;
  my @result = ();
  my $strlen = length $string;

  foreach my $length (1..$strlen) {
    foreach my $offset (0..$strlen-$length) {
      push @result, substr($string,$offset,$length);
    }
  }
  return @result;
}


cmpthese(-10, {
    TheHobbit   => sub { substrings_TheHobbit("Just Another Perl Hacke
+r,") },
    thelenm     => sub { substrings_thelenm("Just Another Perl Hacker,
+") },
});

__output__

Benchmark: running TheHobbit, thelenm, each for at least 10 CPU second
+s...
 TheHobbit: 12 wallclock secs (10.51 usr +  0.03 sys = 10.54 CPU) @ 80
+4.55/s (n=8480)
   thelenm: 14 wallclock secs (10.44 usr +  0.02 sys = 10.46 CPU) @ 80
+9.37/s (n=8466)
           Rate TheHobbit   thelenm
TheHobbit 805/s        --       -1%
thelenm   809/s        1%        --

    [download]
    Is there any reason why a function call would be quicker accessing a lexical variable?
    _________
    broquaint
[reply]
[d/l]
      I bet it's because length() is special. All SVs cache their length already, so putting it in a lexical is just a slower way to cache length().

      -sam

[reply]

      Some repeated benchmarking answers this . . .

      my is expensive. Removing the my and making $strlen a global eliminates the diferrence for the small test case. The bench about the same. Multiplying the length of the test string by ten and leaving $strlen global gives thelenm's sub big gains over the orginal - %6-%10. Finally, making $strlen lexical and retesting reduces those gains by %4-%8, still testing with "Just Another Perl Hacker,"x10.

      So, yes, this is definately an optimization.

      Cheers,
      Erik
[reply]
[d/l]
[select]
Re: Re: Finding all substrings
by giulienk (Curate) on Apr 24, 2002 at 18:08 UTC
    AFAIK the code between parens in the foreach statement is executed just once to obtain a list over which to iterate.
    So yours is not really an optimization.
    Update: i see now your and suaveant point as the inner loop get called multiple times: the original post was not that clear.

    $|=$_='1g2i1u1l2i4e2n0k',map{print"\7",chop;select$,,$,,$,,$_/7}m{..}g

[reply]
      Very true... but the inner foreach loop gets called multiple times... so there would be a bit of savings... certainly good advice in this case... in a single for loop it would make no difference.

                      - Ant
                      - Some of my best work - (1 2 3)

[reply]

In Section Seekers of Perl Wisdom