Perlで配列の積集合(intersection)を求めるベンチマーク がおもしろかったので自分でもやってみた 。 List::などのクラスは遅いそうなので、除外して、 連想配列(hash)を使った方法だけに絞った。 

use strict;
use warnings;

use Benchmark;

my @l1 = map { int rand 1000 } 1..1000;
my @l2 = map { int rand 1000 } 1..1000;

timethese(10000, {
  q/hash-map-grep-exists/ => sub {
    my (%in_l1);
    map { $in_l1{$_}++ } @l1;
    grep { exists $in_l1{$_} } @l2;
  },

  q/hash-map+keys/ => sub {
    my (%union, %isect);
    map { $union{$_}++ && $isect{$_}++ } @l1, @l2;
    keys(%isect);
  },

  q/hash-foreach-keys/ => sub {
    my (%union, %isect);
    foreach my $e (@l1, @l2) { $union{$e}++ && $isect{$e}++ }
    keys(%isect);
  },

  q/hash-grep/ => sub {
    my %in_l1 = map { $_ => 1 } @l1;    ### こういう書き方は遅い
    grep { $in_l1{$_} } @l2;
  },

  q/hash-grep-exists/ => sub {
    my %in_l1 = map { $_ => undef } @l1;
    grep { exists $in_l1{$_} } @l2;
  },
});

processtime
hash-map-grep-exists 33 wallclock secs (28.93 usr + 0.01 sys = 28.94 CPU) @ 345.54/s (n=10000)
hash-foreach-keys 53 wallclock secs (48.90 usr + 0.01 sys = 48.91 CPU) @ 204.46/s (n=10000)
hash-grep-exists 54 wallclock secs (43.32 usr + 0.05 sys = 43.37 CPU) @ 230.57/s (n=10000)
hash-grep 55 wallclock secs (46.70 usr + 0.02 sys = 46.72 CPU) @ 214.04/s (n=10000)
hash-map+keys 61 wallclock secs (50.56 usr + 0.04 sys = 50.60 CPU) @ 197.63/s (n=10000)

hash を利用しているので、hashの作り方の違いで速さが 変わった。hash-map-grep-exists(33 secs)と hash-grep-exists(54 secs) の違いは、連想配列 %in_l1 への 値の代入方法にある。hashを作るときに、 my %hash = map { $_ => 1 } @array;という ような書き方をすると、hash を作ってから、別の変数に 代入しなおす処理があるらしく、hash を作るだけの処理時間 として比較すると倍くらい遅いらしい。書き方は1行で済むのでかっこいい 感じがするが。$in_l1{$_}++のように 個別に代入を1回づつ行えば、もう一度 %in_l1 へのコピー代入は 不要になるためらしい。

また、hash の中の特定のメンバの値を取り出すよりも、 存在を確認するだけなら exists のほうがほんの少し速い。

遅いのは、hash-map-keysで、map {} の処理ブロック内で 条件分岐をしているところのもよう。

また、= 1 と = undef は速度変わらず。=1 よりも ++ のほうが速い。

というわけで、2つの配列の間で積集合を求めるのにいちばん速かったコードを 関数にするとこうなる。 

sub array_intersection($$) {
  my (%_u);
  map { $_u{$_}++ } @{$_[0]};
  grep { exists $_u{$_} } @{$_[1]};
}

一方、python で配列の積集合を求めるときは、setsというのを 使って抽象的に書ける。こういうところはPerlにはない、教育系でも 使われているpythonにメリットがある。教育系で使われるから、 卒業してもpythonを使う、ということなのだろう。 速さは調べていないが、python の配列・ 行列機能は数値計算処理にも使われているので、けっこう速い のではないか？ 

import sets
a_set = sets.Set([3, 2])
b_set = sets.Set([4, 3])
print a_set & b_set   # or a_set.intersection(b_set)