配列の差 - tsucchi’s diary(元はてなダイアリー)

「配列の差」ってたまに欲しくなりませんか？

ならないですか。そうですか。

オイラはたまに欲しいときがあります。「パスワードの自動生成するけど、ある特定のアルファベットを除きたい」とか、なんかのチェックをするときに、「全リストを取得してからいくつかの除外対象を除く」とか、最近2回くらい「配列の差」が欲しいことがありました。

で、オイラが最初に考えたダサダサなやり方がコレ。

my @difference = @array1;
for my $exclude (@array2) {
    @difference = grep($_ ne $exclude, @difference);
}

@array1 と @array2 の差が @difference に入ります。実質的に二重ループなのでダサダサなのは明らかなんだけど、他にやり方がとりあえず思いつかなかった。。。

で、ちょっとぐぐったら、なんと perlfaq にあるらしい orz

二つの配列の差(difference)を求めるには? 二つの配列の共通要素(inter section)を求めるには? - perlfaq4 - データ操作訳出 2005/11/8

ハッシュを使います。以下のプログラム片は質問の両方を行います。与えられた配列の要素には重複がないと仮定しています。

@union = @intersection = @difference = ();
%count = ();
foreach $element (@array1, @array2) { $count{$element}++ }
foreach $element (keys %count) {
    push @union, $element;
    push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element;
}

なるほどね。確かに。

では、自分のやり方がどれだけダサかったかを検証してみます。

#!/bin/perl
use strict;
use Benchmark qw(cmpthese);

my @array1 = qw(aaa bbb ccc ddd eee);
my @array2 = qw(aaa ccc);
my $count = 50000;

#
# from Perl FAQ
# http://www.kt.rim.or.jp/~kbk/perl5.005/perlfaq4.html#How_do_I_compute_the_difference_
sub get_difference1 {
    my @difference = ();
    my %count = ();
    for my $element (@array1, @array2) { $count{$element}++ }
    for my $element (keys %count) {
        push @difference, $element if  $count{$element} <= 1;
    }
    return @difference;
}

#
# 自作
sub get_difference2 {
    my @difference = @array1;
    for my $exclude (@array2) {
        @difference = grep($_ ne $exclude, @difference);
    }
    return @difference;
}

cmpthese($count, {
        'Perl FAQ' => \&get_difference1,
        'Mine'     => \&get_difference2,
    });

説明不要ですよね。Perl FAQ のやり方が get_difference1 で、オイラの考えたやり方が get_difference2 です。では、実行。

tsucchi@over[117]% perl a.pl
            Rate     Mine Perl FAQ
Mine     95522/s       --      -3%
Perl FAQ 98462/s       3%       --

あり？意外と差がないや。データが小さすぎるのかな？ではデータを少しずつ大きくして試します。

# array1 の要素数を増やしてみる
my @array1_bak = @array1;
my @alpha = qw(aaa bbb ccc ddd eee fff ggg hhh iii jjj kkk lll mmm nnn ooo ppp qqq rrr sss ttt uuu vvv www xxx yyy zzz);
for (my $array1_length = 0; $array1_length <= 500; $array1_length += 100) {
    for( my $i=0; $i<$array1_length; $i++) {
        push(@array1, $alpha[int rand(scalar(@alpha))]);
    }

    print "追加した要素数: $array1_length: \n";
    cmpthese($count, {
        'Perl FAQ' => \&get_difference1,
        'Mine'     => \&get_difference2,
    });
    @array1 = @array1_bak;
}

なんとなくランダムな要素を 100, 200, 300, 400, 500 個ずつ足してみて、そのたびに結果をとってみます。

では実行。

追加した要素数: 0: 
             Rate     Mine Perl FAQ
Mine      95522/s       --      -6%
Perl FAQ 101587/s       6%       --
追加した要素数: 100: 
            Rate     Mine Perl FAQ
Mine      3951/s       --     -71%
Perl FAQ 13417/s     240%       --
追加した要素数: 200: 
           Rate     Mine Perl FAQ
Mine     1743/s       --     -79%
Perl FAQ 8184/s     369%       --
追加した要素数: 300: 
           Rate     Mine Perl FAQ
Mine     1051/s       --     -82%
Perl FAQ 5872/s     459%       --
追加した要素数: 400: 
           Rate     Mine Perl FAQ
Mine      767/s       --     -83%
Perl FAQ 4578/s     497%       --
追加した要素数: 500: 
           Rate     Mine Perl FAQ
Mine      511/s       --     -83%
Perl FAQ 3039/s     495%       --

予想通り。。。とでも言うのかな。要素が増えるとオイラのやり方はありえないほど遅くなりました。重複を許す場合や、順序を保存したい場合は perlfaq のやり方だとダメなんだけど、それでもやっぱり事前にきっちり調べておかないとダメだよね、というお話でした。