Re: Miniature golf question

For efficiency, you generally want to avoid map expressions that return more than one element for each element of the original list, at least in current versions of Perl. As I understand it, map preallocates a list to hold the results, but when you return several elements for each individual element, there's a lot of overhead to accomodate the extra elements.

Here's a way to do the transfer without using map:

my @keys = grep /^t/, keys %hash;
my %newhash;
@newhash{@keys} = @hash{@keys};
[download]

On the other hand, I did a quick benchmark, which ended up showing little difference in efficiency between the solutions:

#!perl -w

use strict;

use Benchmark;

Benchmark->import(qw/cmpthese/) if $^V;

my $time = shift || 5;
my $size  = shift || 100;

my %hash;

for (0 .. $size) {
  if ($_ < $size / 4) {
    $hash{"t$_"} = 1;
  } else {
    $hash{"a$_"} = 1;
  }
}

my %bms = (
           grep_map    => sub { my @keys = grep /^\t/, keys %hash;
                                my %newhash = map { ($_, $hash{$_}) } 
+@keys;
                              },
           just_map    => sub { my %newhash = map /^\t/ ?
                                  ( $_, $hash{$_} ) :
                                  (), keys %hash;
                              },
           grep_slice  => sub { my @keys = grep /^\t/, keys %hash;
                                my %newhash;
                                @newhash{@keys} = @hash{@keys};
                              },
          );

if ($^V) {
  cmpthese(-$time, \%bms);
} else {
  timethese(-$time, \%bms);
}

__END__

% perl bm.pl
Benchmark: running grep_map, grep_slice, just_map, each for at least 5
+ CPU seconds...
  grep_map:  6 wallclock secs ( 5.29 usr +  0.01 sys =  5.30 CPU) @ 40
+34.15/s (n=21381)
grep_slice:  6 wallclock secs ( 5.28 usr +  0.00 sys =  5.28 CPU) @ 40
+47.73/s (n=21372)
  just_map:  6 wallclock secs ( 5.23 usr +  0.00 sys =  5.23 CPU) @ 39
+90.06/s (n=20868)
             Rate   just_map   grep_map grep_slice
just_map   3990/s         --        -1%        -1%
grep_map   4034/s         1%         --        -0%

% perl/bin/perl bm.pl 5 1000
Benchmark: running grep_map, grep_slice, just_map, each for at least 5
+ CPU seconds...
  grep_map:  6 wallclock secs ( 5.26 usr +  0.00 sys =  5.26 CPU) @ 41
+2.17/s (n=2168)
grep_slice:  6 wallclock secs ( 5.25 usr +  0.00 sys =  5.25 CPU) @ 41
+2.95/s (n=2168)
  just_map:  6 wallclock secs ( 5.29 usr +  0.00 sys =  5.29 CPU) @ 39
+8.87/s (n=2110)
            Rate   just_map   grep_map grep_slice
just_map   399/s         --        -3%        -3%
grep_map   412/s         3%         --        -0%
grep_slice 413/s         4%         0%         --
[download]

So I guess you can just go with whichever solution you like best. :)

Comment on Re: Miniature golf question Select or Download Code

Replies are listed 'Best First'.
Re (tilly) 2: Miniature golf question by tilly (Archbishop) on Jul 17, 2001 at 00:16 UTC
Your efficiency note is only true until Perl 5.6.1. The problem is that Perl builds the return list in place. In old versions it would only allocate the minimum necessary space, moving data every time. The moving of data was a O(n²) bottleneck. Starting in 5.6.1 it will allocate the minimum of the minimum necessary, and the length of the data stack. This results in a power of 2 reallocation strategy that winds up being O(n) in terms of moving data. To experience the difference that this makes, try running this statement in both a new and old version of Perl: `my @big_list = map {($_, $_)} 1..50_000;` [download] If it takes a while, you aren't on 5.6.1 yet. :-)	[reply] [d/l]
Re: Re (tilly) 2: Miniature golf question by nysus (Parson) on Jul 17, 2001 at 07:30 UTC
Tilly, I started to read "Structure and Interpretations of Computer Programs" and it was right around the stuff you bring up above that I started to get lost. Too much for a guy who blew off H.S. more than he should have. So until I brush up on my math skills, do you know of a lighter introduction to the kind of concepts you mention above? Thanks, bro. $PM = "Perl Monk's"; $MCF = "Most Clueless ~~Friar~~ ~~Abbot~~ Bishop"; $nysus = $PM . $MCF; Click here if you love Perl Monks	[reply]
Re: Re: Miniature golf question by suaveant (Parson) on Jul 16, 2001 at 23:31 UTC
I think he was looking for golf solutions, since his title is miniature golf... so its more the terseness of the code, throwing efficiency to the wind... Hehe, I certainly wouldn't want to use the grep without the keys call anywhere else :) - Ant	[reply]