帰ってきたネコブログ

では、さっそくソートに掛かる時間を計測したいと思います。

use strict;
use warnings;
use v5.10;
use Benchmark qw/cmpthese timethese/;
use Array::Shuffle qw/shuffle_array/;

{
    my $n = 10;
    my @data = 1..2000;

    my @data_asc_ary = map {
        my @tmp = @data;
        \@tmp;
    } 1..$n;

    my @data_rand_ary = map {
        my @tmp = @data;
        shuffle_array( @tmp );
        \@tmp;
    } 1..$n;

    cmpthese( $n, {
        'asc' => sub {
            my $ary_ref = shift @data_asc_ary;
            insert_sort( @{$ary_ref} );
        },
        'random' => sub {
            my $ary_ref = shift @data_rand_ary;
            insert_sort( @{$ary_ref} );
        }
    });
}

print "\n";

{
    my @data_asc  = 1..5000;
    my @data_desc = reverse @data_asc;

    timethese( 1, {
        'asc ' => sub {
            my @wk = @data_asc;
            insert_sort( @wk );
        },
        'desc' => sub {
            my @wk = @data_desc;
            insert_sort( @wk );
        }
    });
}

sub insert_sort {
    my @data = @_;

    my $cnt = scalar( @data );
    for (my $i=1; $i<$cnt; $i++) {
        my $wk = $data[$i];
        my $j = $i;
        for (; 0<$j; $j--) {
            if ( $wk <= $data[$j-1] ) {
                last;
            }
            else {
                $data[$j] = $data[$j-1];
            }
        }

        $data[$j] = $wk;
    }
 
    return @data;
}

結果はこんな感じ。

$ perl aaa.pl 
       s/iter    asc random
asc      1.38     --   -49%
random  0.696    98%     --

Benchmark: timing 1 iterations of asc , desc...
      asc :  9 wallclock secs ( 8.66 usr +  0.04 sys =  8.70 CPU) @  0.11/s (n=1)
            (warning: too few iterations for a reliable count)
      desc:  0 wallclock secs ( 0.00 usr +  0.00 sys =  0.00 CPU)
            (warning: too few iterations for a reliable count)

ランダムデータの場合と、小さい順に並んだデータだと、
だいたい倍くらいの差がつくようです。

そして、大きい順に並んだデータはソート済みのデータと等価なので、
ソートに掛かる時間が短過ぎて、他と比較のしようがないです。

あと、見直してて思ったのは、
シャッフルが無視できるようなデータ数でやれば、
もっとテストコードがシンプルかなーって思いました。

ここまではカンペ通りです。

続く。

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