Every other

[Philip Potter]

Torsten's solution was fastest:

pgp at teach:~/src/perl/scratch$ cat every-other.pl
#!/usr/bin/env perl

use strict;
use warnings;

use feature qw(say);

use Benchmark qw(:all);

my @data = 1..100;

cmpthese( 50_000, {
        'via array slice map'   => \&via_array_slice_map,
        'via array slice grep'  => \&via_array_slice_grep,
        'via hash'              => \&via_hash,
        'via part'              => \&via_part,
        'via grep bang'         => \&via_grep_bang,
        'via grep preinc'       => \&via_grep_preinc,
        'via grep xor'          => \&via_grep_xor,
        'via map'               => \&via_map,
    });

# for testing only
#local $,=',';
#say via_array_slice_map();
#say via_array_slice_grep();
#say via_hash();
#say via_part();
#say via_grep_bang();
#say via_grep_preinc();
#say via_grep_xor();
#say via_map();

sub via_array_slice_map {
    return @data[map {$_*2} 0..$#data/2];
}

sub via_array_slice_grep {
    return @data[ grep {!($_ & 1)} (0 .. $#data) ];
}

sub via_hash {
    my %hash = @data;
    return (sort {$a <=> $b} keys %hash);
}

sub via_part {
    use List::MoreUtils qw(part);
    my $i = 0;
    my @part = part {$i++ % 2} @data;
    return @{$part[0]};
}

sub via_grep_bang {
    my $i = 0;
    return grep { $i = !$i } @data;
}

sub via_grep_preinc {
    my $i = 0;
    return grep { ++$i % 2 } @data;
}

sub via_grep_xor {
    my $i = 0;
    return grep { $i ^= 1 } @data;
}

sub via_map {
    my $i = 1;
    return map {($i ^= 1) ? () : $_} @data;
}

pgp at teach:~/src/perl/scratch$ perl every-other.pl
                        Rate via part via hash via grep bang via array
slice grep via grep preinc via map via array slice map via grep xor
via part             28090/s       --     -19%          -29%
      -37%            -41%    -46%                -52%         -56%
via hash             34483/s      23%       --          -12%
      -22%            -28%    -34%                -41%         -46%
via grep bang        39370/s      40%      14%            --
      -11%            -17%    -24%                -32%         -39%
via array slice grep 44248/s      58%      28%           12%
        --             -7%    -15%                -24%         -31%
via grep preinc      47619/s      70%      38%           21%
        8%              --     -9%                -18%         -26%
via map              52083/s      85%      51%           32%
       18%              9%      --                -10%         -19%
via array slice map  58140/s     107%      69%           48%
       31%             22%     12%                  --          -9%
via grep xor         64103/s     128%      86%           63%
       45%             35%     23%                 10%           --

[eech, this table doesn't fit well in email. see
http://www.doc.ic.ac.uk/~pgp/everyother.txt]

so grep {$i ^= 1} @data; is fastest (on my machine at this phase of
the moon etc), and somehow around 60% faster than grep {$i = !$i}
@data; -- it surprises me that these aren't exactly the same..

I'd still stick with grep {++$i % 2} @data; for readability though...

map beat two of the grep implementations despite protests that it
copies rather than aliasing. Mapping was also better than grepping for
forming index lists for array slices.

part is unfairly disadvantaged since it is actually forming two lists,
one of the evens and one of the odds, so it's not surprising that it
is the slowest.

In the end though, you only get a 2.25 factor gain of the best against
the worst, so you might as well pick something readable.

Phil

2009/10/30 Mark Fowler <mark at twoshortplanks.com>:
> Hello,
>
> I have in the past coded things to only discover later that someone
> else has already written what I have toiled away on, only better.  So
> this time, I'm asking the experts[1] first.
>
> I have an array in Perl 5 [2].  I want *every* *other* element from
> it.  There is, of course, more than one way to do it:
>
> my @new;
> foreach (my $i = 0; $i < @old; $i++) {
>  push @new, $old[ $i ];
> }
>
> Or
>
> my $i;
> my @new = grep { $i = !$i } @old;
>
> Or so on.  None of these are particularly readable, or for that
> matter, blindly efficient (they still use quite a few ops for such a
> simple operation)
>
> What I would prefer is this:
>
> my @new = every_other @old;
>
> Which I guess could be generalised like so:
>
> i.e.
>
> everyother @array;
> everyother @array, $offset;
> everyother @array, $offset, $take_how_many;
> everyother @array, $offset, $take_how_many, $skip_how_many;
>
> (with the default being everyother @array, 0, 1, 1)
>
> e.g.
>
> Ideally this would be a utility in List::MoreUtils or suchlike, but
> it's not.  Ideally it'd be implemented in C as well as in Perl so that
> it doesn't burn ops for such a simple idea.
>
> Before I get going with the coding, does anyone know of anything else
> that can do this?
>
> Mark.
>
> [1] experts on Buffy that is.   Who might also happen to know some Perl.
> [2] There's very nice syntax for this in Perl 6, isn't there?  I'm not
> using that language yet.
>