最近 perl を覚えたらしい方が「これからは for じゃなくて mapでしょ!」といって片っ端から普通にループするコードをそのまま(←ここ重要) map で書いているのを目撃したので、ちょっと調べてみました。

今回 google さんに与えたキーワードは「perl map foreach 速度」で、トップ 2つは以下でした。

mapは遅いのか - 北海道苫小牧市出身のPGが書くブログ
http://d.hatena.ne.jp/hiratara/20060425/1145979934
→ map がちょっとだけ遅い派

foreach と map を比べてみた - あれだよ、あれ……なんだっけ？
http://wizard-blue.hatenablog.jp/entry/2013/06/21/120437
→ map がとても速い派

という訳でここで決着をつけたいと思います。
「map がとても速い派」の方は、測定を行っているコードに残念ながら致命的な欠陥があります。それは… 普通に読むと $count2 が副作用で変化してしまう点、もうちょっと調べると cmpthese 内ではそもそも $count1, $count2 が未定義として扱われてしまうという点なんですが、これは別件。

ちゃんと動くように書き直してみましょう。ちなみにやりたいことは

文字列1と文字列2を比較して、文字列2に文字列1の文字が全て含まれているか確認する処理
だそうですので、特別サービスで元にはない方法も追加しておきます。
(元コードでやりたいことができるかどうかは…この際問わないことにします)

コード
use strict;
use warnings;

use Benchmark qw(cmpthese);

my $count1 = 'abcdefghijklmnopqrstuvwxyz';
my $count2 = 'bzdfijlmonqrsvaehykcwgptux';

# オリジナルの map を使う方法
sub test_map {
    my ($c1, $c2) = ($count1, $count2);
    map { $c2 =~ s/$_//; } split("", $c1);
}

# オリジナルの for を使う方法
sub test_foreach {
    my ($c1, $c2) = ($count1, $count2);
    $c2 =~ s/$_// foreach(split("", $c1));
}

# おまけ
sub test_map_grep {
    my %c2 = map {($_ => 1)} split("", $count2);

    scalar(grep { !$c2{$_} } split("", $count1)) == 0;
}

my $code = {
    'map'       =>  \&test_map,
    'foreach'   =>  \&test_foreach,
    'map_grep'  =>  \&test_map_grep,
};

my $iterate = 100_000;

cmpthese($iterate, $code);

結果 
            Rate      map  foreach map_grep
map      15848/s       --      -4%     -67%
foreach  16584/s       5%       --     -65%
map_grep 47847/s     202%     189%       --

そんなわけで、

  • 普通にループを for (foreach でも同じ)を map にしただけではあまり速度が変わらない
  • map に適したアルゴリズムを使えば速いかもしれない
というマットウな結論になるかと思われます。

元のコードとおまけコードを比べると、メモリの確保などの技術的な要因の他にも違いがあります。

元コードの文字比較回数は、$count2 がだんだん短くなるという点に目をつぶると、概ね文字列の長さの積になります。一方、おまけコードは、ハッシュを使って文字列の有無を検索しているので、$count1回の比較という ということで計算量のオーダーがちょっと低いのです。

という訳で、速さの違いは map と for の違いじゃなくてアルゴリズムの違いというまさかの結論ということにしたいと思います。

あ、文字列生成を何度も繰り返すと遅いのは本当ですからね、それも忘れないでくださいね!!
タグ ：
#perl