nDiki

2013年7月23日 (火)

Perl で「いくつかの値のどれかと同じか判定」するにはやはりハッシュにして exists するのが速い

Perl で「ある値が、いくつかの値のどれかと同じか判定」するには、あらかじめ判定用のハッシュを作っておくのが定石だし、実際に速い。けど実際にどれぐらい速いのかな。

試してみる。手元の環境は Perl 5.14.2。どれかにマッチするのは 0.1% というケースでベンチマーク

 #!/usr/bin/perl

 use warnings;
 use strict;

 use Benchmark qw(cmpthese);
 use List::MoreUtils qw(any);

 foreach my $size (3, 10, 100) {
   my @a = (1 .. $size);
   my %h;
   $h{$_}++ foreach @a;

   cmpthese(
     -30,
     {
       "grep($size)" => sub {
         foreach my $i (1 .. $size * 1000) {
           my $exists = grep { $_ == $i } @a;
         }
       },
       "any($size)" => sub {
         foreach my $i (1 .. $size * 1000) {
           my $exists = any { $_ == $i } @a;
         }
       },
       "exists($size)" => sub {
         foreach my $i (1 .. $size * 1000) {
           my $exists = exists $h{$i};
         }
       },
       "make & exists($size)" => sub {
         foreach my $i (1 .. $size * 1000) {
           my %my_h;
           $my_h{$_}++ foreach @a;
           my $exists = exists $my_h{$i};
         }
       },
     }
   );
   print "\n";
 }

結果

                   Rate        any(3) make & exists(3)       grep(3)    exists(3)
 any(3)           107/s            --             -33%          -77%         -87%
 make & exists(3) 160/s           49%               --          -66%         -80%
 grep(3)          471/s          339%             194%            --         -43%
 exists(3)        820/s          665%             412%           74%           --

                    Rate      any(10) make & exists(10)     grep(10)  exists(10)
 any(10)           21.1/s           --               -8%         -67%        -91%
 make & exists(10) 23.0/s           9%                --         -65%        -90%
 grep(10)          64.9/s         208%              182%           --        -73%
 exists(10)         240/s        1036%              941%         269%          --

                     s/iter make & exists(100)   any(100)  grep(100) exists(100)
 make & exists(100)     3.48                 --       -50%       -65%        -99%
 any(100)               1.75                99%         --       -30%        -97%
 grep(100)              1.23               182%        42%         --        -96%
 exists(100)        4.49e-02              7643%      3797%      2641%          --

やはりハッシュを作っておいた方が速いね。ただし毎回その場で配列に入っているものからハッシュを作って判定処理するぐらいなら100個程度なら grep した方が速い。

配列の全件をほぼ毎回舐めることになる今回のケースでは any よりも grep の方が速い。

Happy Benchmarking!

スポンサード リンク
[ 7月23日全て ]

About Me

Naney Naney (なにい)です。株式会社ミクシィで SNS 事業の部長をしています。

nDiki1999年1月に始めたコンピュータ日誌を前身とする NaneyWeb 日記(兼パーソナルナレッジベース)です。ちょっとしたノートは nNote にあります。

※内容は個人的見解であり所属組織とは関係ありません。

follow us in feedly

月別インデックス
Process Time: 0.130672s / load averages: 1.03, 0.79, 0.69
nDiki by WATANABE Yoshimasa (Naney, Google profile)
Powered by DiKicker