id:ichirin2501のコードのどこに問題があるかは、以下のベンチマークを走らせてみればわかります。

#!/usr/bin/env perl
use 5.012;
use Benchmark qw/:all/;

sub uniq_copy {
    my @array = @_;
    my %hash;
    @hash{@array} = ();
    return keys %hash;
}

sub uniq_nocopy {
    my %seen;
    @seen{@_} = ();
    return keys %seen;
}

my $u = shift || 100;
my $d = shift || 100;

my @a = ( 1 .. $u ) x $d;

say '@a = ', "( 1 .. $u ) x $d";

cmpthese timethese 0,
  {
    copy   => sub { uniq_copy(@a) },
    nocopy => sub { uniq_nocopy(@a) },
  }

100要素の100回繰り返し、つまり10,000要素で、これだけの差が出ました。

         Rate   copy nocopy
copy    274/s     --   -82%
nocopy 1524/s   457%     --

何が問題だったかというと、@_をコピーして使っていたこと。いずれの実装でも、よく見るとコピーは不要です。

ただし一般論として、@_はコピーしてから使えというのは正しい。以下をご覧下さい。right()もwrong()も、引数に1を足して返すだけの簡単なsubですが、wrong()の方は元の引数まで書き換えてしまっています。

use 5.012;

sub wrong { map { ++$_   } @_ }
sub right { map { $_ + 1 } @_ }

my @a = (1..10);
say join ",", right(@a);
say join ",", @a;
say join ",", wrong(@a);
say join ",", @a;

これを防ぐために、@_は直接使わずにコピーして使うのがperlでsubを書く際の一般的な作法なのですが、今回のuniqの実装のように、@_の要素数が膨大になりうる場合は立派な例外です。

この点を改めてベンチマークを取り直した結果が、以下の通り(100x100の場合)

          Rate     map      au    grep foreach   slice     lmu
map      162/s      --    -25%    -66%    -75%    -89%    -91%
au       217/s     34%      --    -55%    -66%    -86%    -89%
grep     482/s    198%    122%      --    -25%    -68%    -75%
foreach  638/s    294%    194%     32%      --    -57%    -66%
slice   1500/s    827%    591%    212%    135%      --    -21%
lmu     1901/s   1075%    775%    295%    198%     27%      --

built-inではhashの最強ぶりと、XSの活用でそれをも上回るList::MoreUtilsの優秀さがよりはっきりとしました。

Dan the Perl Monger

#!/usr/bin/env perl
use 5.012;
use Benchmark qw/:all/;

sub uniq_au{
    use Array::Uniq ();
    return Array::Uniq::uniq sort @_;
}
sub uniq_foreach {
    my %hash;
    $hash{$_} = 1 foreach (@_);
    return keys %hash;
}

sub uniq_grep {
    my %hash;
    return grep { !$hash{$_}++ } @_;
}

sub uniq_lmu {
    use List::MoreUtils;
    return List::MoreUtils::uniq @_;
}

sub uniq_map {
    my %hash = map { $_ => 1 } @_;
    return keys %hash;
}

sub uniq_slice {
    my %hash;
    @hash{@_} = ();
    return keys %hash;
}

my $u = shift || 100;
my $d = shift || 100;

my @a = ( 1 .. $u ) x $d;

say '@a = ', "( 1 .. $u ) x $d";

cmpthese timethese 0,
  {
    au      => sub { uniq_au(@a) },
    foreach => sub { uniq_foreach(@a) },
    grep    => sub { uniq_grep(@a) },
    lmu     => sub { uniq_lmu(@a) },
    map     => sub { uniq_map(@a) },
    slice   => sub { uniq_slice(@a) },
  };