Extracting values from a list of (key, value) pairs
If you need ordered key, value pairs, you can either use something like Tie::IxHash or a simple array of key, value pairs. I found myself in the situation where I needed to extract just the keys from such an array.
There are a number of ways to do it, but which is the fastest? I tried a few pure Perl approaches, as well as List::Util::pairkeys
(which as of this writing isn't yet in a stable release of Perl, assuming that List::Util remains in the core). The pure Perl approaches either use various means of flipping a binary toggle, or splice()
ing through a sacrificial copy of the array.
Here we go:
#!/usr/bin/env perl
use 5.10.1;
use strict;
use warnings;
use List::Util qw[ pairkeys ];
use Benchmark qw[ timethese cmpthese ];
my $N = 10000;
my @N = 1 .. $N;
cmpthese(
timethese(
10000,
{
'splce' => sub {
my @v;
my ( $k, $v );
my @N = @N;
push @v, $k while ( ( $k, $v ) = splice( @N, 0, 2 ) );
},
'%m' => sub {
use integer;
my $flip = 0;
my @v = map { ++$flip % 2 ? $_ : () } @N;
},
'%g' => sub {
use integer;
my $flip = 0;
my @v = grep { ++$flip % 2 } @N;
},
'1-m' => sub {
use integer;
my $flip = 0;
my @v
= map { ( $flip = 1 - $flip ) ? $_ : () } @N;
},
'1-g' => sub {
use integer;
my $flip = 0;
my @v = grep { $flip = 1 - $flip } @N;
},
'ff' => sub {
use integer;
my $flip = 0;
my @v = grep { $flip = !( $flip .. $flip ) } @N;
},
'xor' => sub {
use integer;
my $flip = 0;
my @v = grep { $flip ^= 1 } @N;
},
'for' => sub {
use integer;
my @v;
for( my $i = 0 ; $i < @N ; $i+=2 ) {
push @v, $N[$i];
}
},
'idxp' => sub {
use integer;
my @v;
push @v, $N[2 * $_] for 0..(@N/2)-1;
},
'idxm' => sub {
use integer;
my @v;
@v = map { $N[2 * $_] } 0..(@N/2)-1;
},
'idxa' => sub {
use integer;
my @v;
$v[$_] = $N[2 * $_] for 0..(@N/2)-1;
},
'pkey' => sub {
my @v = pairkeys @N;
},
} ) );
And here are the results:
Rate splce ff %m 1-m idxm %g for xor idxa 1-g idxp pkey
splce 497/s -- -3% -5% -27% -30% -33% -40% -52% -53% -54% -59% -74%
ff 514/s 3% -- -2% -25% -28% -30% -38% -50% -52% -53% -58% -74%
%m 524/s 6% 2% -- -23% -26% -29% -37% -49% -51% -52% -57% -73%
1-m 681/s 37% 33% 30% -- -4% -8% -18% -34% -36% -37% -44% -65%
idxm 712/s 43% 39% 36% 5% -- -3% -14% -31% -33% -34% -41% -63%
%g 738/s 49% 44% 41% 8% 4% -- -11% -29% -31% -32% -39% -62%
for 831/s 67% 62% 58% 22% 17% 13% -- -20% -22% -24% -32% -57%
xor 1037/s 109% 102% 98% 52% 46% 41% 25% -- -3% -4% -15% -47%
idxa 1067/s 115% 108% 104% 57% 50% 45% 28% 3% -- -2% -12% -45%
1-g 1086/s 119% 111% 107% 59% 52% 47% 31% 5% 2% -- -11% -44%
idxp 1214/s 144% 136% 131% 78% 70% 64% 46% 17% 14% 12% -- -37%
pkey 1942/s 291% 278% 270% 185% 173% 163% 134% 87% 82% 79% 60% --
- If you've got
List::Util::pairkeys
, use it. - Array indexing is surprisingly fast.
- Pushing onto the end of an array is significantly faster than direct assignment into it.
grep
is faster thanmap
; not too surprising- Remainders (%) are slower then subtraction; not too surprising.
- Binary exclusive-or is comparable to subtraction, which is a bit surprising
- In this application
use integer
provided a significant boost in speed. - The flipflop operator is surprisingly slow
splice()
andflipflop
are essentially tied.splice()
is slowed down significantly by needing to make a copy of the array. (If I added the copy cost to the others it moved up two slots in the rankings). It would be even slower if the array (or its elements) were larger. When Copy on Write (COW) makes it into Perl, that difference should diminish.