帰ってきたネコブログ

まずは、おさらいから。

use strict;
use warnings;
use v5.10;

my $str = '1,2,10,20,100,200';
my @ary = reverse( split /,/, $str );

say "------------------------------------";
printf("%5s,", $_ ) for @ary;
print "\n";
say "------------------------------------";
printf("%5s,", $_ ) for sort @ary;
print "\n";
say "------------------------------------";
printf("%5s,", $_ ) for sort { $a <=> $b } @ary;
print "\n";
say "------------------------------------";

実行すると、こんな感じ。
$ perl aaa.pl
------------------------------------
200, 100, 20, 10, 2, 1,
------------------------------------
1, 10, 100, 2, 20, 200,
------------------------------------
1, 2, 10, 20, 100, 200,
------------------------------------

という訳で、デフォルトの動作だと文字列比較によるソートが行われるので、
（値の）小さい順にソートするには、ブロック等を指定する必要がある。

で、本題。

use strict;
use warnings;
use v5.10;
use Benchmark qw/cmpthese/;

my @int_vals = reverse 1..2000000;
my @str_vals = map '' . $_, @int_vals;

cmpthese( 1, {
    'int_vals' => sub { my @tmp = sort @int_vals; },
    'str_vals' => sub { my @tmp = sort @str_vals; }
} );

実は、こんなのでも微妙に差が出る。
内部に詳しくないので、理由は分からないけど。

$ perl bbb.pl 
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
           Rate int_vals str_vals
int_vals 1.56/s       --      -6%
str_vals 1.67/s       7%       --

次は、値が小さい順にソートする。

$ cat ccc.pl 
use strict;
use warnings;
use v5.10;
use Benchmark qw/cmpthese/;

my @int_vals = reverse 1..2000000;
my @str_vals = map '' . $_, @int_vals;

cmpthese( 1, {
    'int_vals' => sub { my @tmp = sort { $a <=> $b } @int_vals; },
    'str_vals' => sub { my @tmp = sort { $a <=> $b } @str_vals; }
} );

これだと、こんなに差がでる。

$ perl ccc.pl 
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
           Rate str_vals int_vals
str_vals 1.25/s       --     -34%
int_vals 1.89/s      51%       --

ただ、ベンチマークの取り方として妥当なのか分からなくて、
cmptheseの1つ目の引数を10くらいにすると差が小さくなる。

で、「こんなの、なんに使うの？」って話だけど、
例えば、標準入力で取得した改行区切りの文字列を、
値の小さい順にソートするとこんな感じになる。

use strict;
use warnings;
use v5.10;
use Benchmark qw/cmpthese/;

my @int_vals = reverse 1..2000000;
my $str = join "\n", @int_vals;

cmpthese( 1, {
    'case1' => sub {
        my @vals = split "\n", $str;
        my @tmp = sort { $a <=> $b } @vals;
    },
    'case2' => sub {
        my @vals = map int($_), split("\n", $str);
        my @tmp = sort { $a <=> $b } @vals;
    }
} );

こんな感じで差が出る。

$ perl ddd.pl 
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
      s/iter case1 case2
case1   1.59    --  -26%
case2   1.17   36%    --

ソート前もソート後も数値として扱うなら、数値に変換しても特に問題ないし、
結果的にソートに掛かる時間も改善されるのでオススメです。

おしまい。

カテゴリー: Perl, コンピューター by ネコ on 2013年12月15日 | タグ: アルゴリズム > ソート > メモ