帰ってきたネコブログ

次は、Perlのsortと対決してみる。

use strict;
use warnings;
use v5.10;
use Time::HiRes qw/time/;
use Array::Shuffle qw/shuffle_array/;

my @data = 1..100000;

say '--- insert (desc) ---';
{
    my @wk = reverse @data;

    my $st = time();
    my @sorted = insert_sort( @wk );
    say time() - $st;
}

say '--- perl (desc) ---';
{
    my @wk = reverse @data;

    my $st = time();
    my @sorted = sort { $b <=> $a } @wk;
    say time() - $st;
}

say '--- perl (asc) ---';
{
    my @wk = @data;

    my $st = time();
    my @sorted = sort { $b <=> $a } @wk;
    say time() - $st;
}

say '--- perl (random) ---';
for ( 1..5 ) {
    my @wk = @data;
    shuffle_array( @wk );

    my $st = time();
    my @sorted = sort { $b <=> $a } @wk;
    say time() - $st;
}

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
--- insert (desc) ---
0.142155885696411
--- perl (desc) ---
0.00903892517089844
--- perl (asc) ---
0.0095820426940918
--- perl (random) ---
0.0560169219970703
0.05712890625
0.0576529502868652
0.0561912059783936
0.0558931827545166

ちょっとだけ期待したんですけどね、ぜんぜん敵いませんでした。
分かってたとは言え悲しいですが、XSでも書けば違うんですかね。
ただ、sortにも得意、不得意があるようで、
ランダムデータだと、少し時間が掛かるようです。

あと、こんなの見つけました。
sort-2.01 – perldoc.jp

ちなみに、関数の方の説明はこちら。
sort – perldoc.jp

で、関数の説明を見るとマージソートが使われているそうなので、
マージソートを実装した際にも、
今回のように、データ列との関係を調べてみようと思います。

おしまい。

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