ichirin2501's diary

重複した要素をユニークにする代表的な方法としていくつかある。
ふと、どのコードが速いのか気になったのでベンチマークを取ってみました。
今回調べたコードは以下の6種類

# use Array::Uniq;
sub unique_au{
    my @array = @_;
    return uniq sort @array;
}
# foreach
sub unique_each{
    my @array = @_;
    my %hash;
    $hash{$_} = 1 foreach(@array);
    return keys %hash;
}
# grep
sub unique_grep{
    my @array = @_;
    my %hash;
    return grep{!$hash{$_}++} @array;
}
# use List::MoreUtils;
sub unique_lmu{
    my @array = @_;
    return List::MoreUtils::uniq @array;
}
# map
sub unique_map{
    my @array = @_;
    my %hash = map{$_,1} @array;
    return keys %hash;
}
# ハッシュスライス
sub unique_slice{
    my @array = @_;
    my %hash;
    @hash{@array} = ();
    return keys %hash;
}

ベンチマークは、PerlのBenchmarkモジュールを使用しました。
関数に渡す配列に格納されてるのは整数のみで、ランダムシャッフルされたものです。
要素数1000のときは、Benchmarkで10000回試行
要素数10000のときは、Benchmarkで1000回試行
要素数100000のときは、Benchmarkで100回試行
Benchmarkの試行回数が異なるのは時間があまりかからない手元環境の限界回数です。
Benchmarkの試行回数に限っては、とにかく処理回数を多くしたほうが測定値の信頼性が出る？
という理由から統一はしていません。
ただ、異なる配列データではなく、同じ配列データに対して、試行を重ねてるだけになります。
測定値の信頼性を上げるという理由からなので、同じ配列データでも良い？でしょ、たぶんｗ
横軸は要素数に対して重複してる要素の割合です。0%だと完全にユニーク、100%だと全部同じになります。
縦軸はBenchmarkモジュールが出力した値になります。
測定した配列データの種類は重複率0%, 25%, 50%, 75%, 100% の5種類です。

まとめ？
mapコード, Array:Uniqコードは遅い。
ハッシュスライスのコードが安定して性能が良いようです。
要素数がこれ以上増えると、恐らく List::MoreUtils::uniq が光ってくると思われます。
今回調べたのは実行速度だけなので、メモリ使用量も考慮して調べると違った結果になるかも？です。

追記：2011/7/18 9:56
こちらで、id:dankogaiさんから@_をコピーするコストについて、ご指摘を受けました。
あちらで公開されてるコードを手元で動かしてみたところ、以下のような結果になりました。

@a = ( 1 .. 100 ) x 100
Benchmark: running au, foreach, grep, lmu, map, slice for at least 3 CPU seconds...
        au:  3 wallclock secs ( 3.16 usr +  0.00 sys =  3.16 CPU) @ 126.58/s (n=400)
   foreach:  3 wallclock secs ( 3.18 usr +  0.00 sys =  3.18 CPU) @ 365.09/s (n=1161)
      grep:  4 wallclock secs ( 3.26 usr +  0.00 sys =  3.26 CPU) @ 299.08/s (n=975)
       lmu:  4 wallclock secs ( 3.21 usr +  0.00 sys =  3.21 CPU) @ 686.60/s (n=2204)
       map:  3 wallclock secs ( 3.14 usr +  0.00 sys =  3.14 CPU) @ 74.20/s (n=233)
     slice:  3 wallclock secs ( 3.18 usr +  0.00 sys =  3.18 CPU) @ 776.73/s (n=2470)
          Rate     map      au    grep foreach     lmu   slice
map     74.2/s      --    -41%    -75%    -80%    -89%    -90%
au       127/s     71%      --    -58%    -65%    -82%    -84%
grep     299/s    303%    136%      --    -18%    -56%    -61%
foreach  365/s    392%    188%     22%      --    -47%    -53%
lmu      687/s    825%    442%    130%     88%      --    -12%
slice    777/s    947%    514%    160%    113%     13%      --

測定環境
perl version 5.12.3
Benchmark version 1.11
List::MoreUtils version 0.32
Array::Uniq version 0.02
マシン　Gateway GT5020j
スペックはこれに
メモリ　DDR2 1024MB * 2 + DDR2 512MB = 2560MB の状態
Fedora14 , kernel 2.6.35.13-92.fc14.i686

ベンチマークの結果を見る限り、ハッシュスライスがList::MoreUtils::uniqを上回っています。
測定違いかと思い、何度か試してみたのですが結果は変わりませんでした。
環境の違い？なのかもしれませんが、現状では確かめられませんorz
以下のノートPCでも動かしてみましたがハッシュスライスが上回ってました。
（FC14,kernel同じ,version同じ）
ASUS U31F-RX480
CPU名：インテルR Core? i5-480M プロセッサー
動作周波数：2.66GHz (インテルR ターボ・ブースト・テクノロジー利用時は最大: 2.93GHz)
2次キャッシュメモリ：256KB×2
3次キャッシュメモリ：3MB
(公式から引用)

長い前置き？になりましたが、
今の自分の環境ではハッシュスライスのほうが良い結果を出すようです。
他の人の環境ではList::MoreUtils::uniqがより良い結果を出すこともあるかもしれません。
と、一言書き加えておきます。

@_コピーを止め、再度ベンチマークを取って視覚化してみました。
@_コピーを含めたデータも図に入っていますが、コピー有無の差を見たかったからです。
コピー有の測定データは前回と同じものを使用しています。
そのため、コピー無との測定時に使用した配列データとは異なっています。
その点に関しては多少の誤差が含まれると思いますが、考慮するほどのものではないでしょうｗ
縦軸、横軸は上記の図と同じです。