帰ってきたネコブログ

かの有名なクヌース先生の力を借りて、
適切な間隔でシェルソートを行ってみました。

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

my @data = 1..20000;
shuffle_array( @data );

my @perl_sorted;
{
    my $st = time();
    @perl_sorted = sort { $b <=> $a } @data;
    say 'Perl  : ', time() - $st;
}

{
    my $st = time();
    my @sorted = shell_sort(
        \@data,
        sub { $_[0] * 2; },
        sub { int($_[0] / 2); }
    );
    say 'Simple: ', time() - $st;
}

{
    my $st = time();
    my @sorted = shell_sort(
        \@data,
        sub { ($_[0] * 2) + 1; },
        sub { int(($_[0] - 1) / 2); }
    );
    say 'Knuth1: ', time() - $st;
}

{
    my $st = time();
    my @sorted = shell_sort(
        \@data,
        sub { ($_[0] * 3) + 1; },
        sub { int(($_[0] - 1) / 3); }
    );
    say 'Knuth2: ', time() - $st;
}

sub shell_sort {
    my ( $data_ref, $inc, $dec ) = @_;
    my @data = @{$data_ref};

    my $gap = 1;
    my $cnt = scalar( @data );

    while ( $gap < $cnt ) {
        $gap = $inc->( $gap );
    }

    while ( ($gap = $dec->($gap)) ) {
        for (my $i=$gap; $i<$cnt; $i++) {
            my $wk = $data[$i];
            my $j = $i;
            for (; $gap<=$j; $j-=$gap) {
                if ( $wk <= $data[$j-$gap] ) {
                    last;
                }
                else {
                    $data[$j] = $data[$j-$gap];
                }
            }

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

実行結果はこんな感じ。
$ perl aaa.pl
Perl : 0.00928997993469238
Simple: 1.65300297737122
Knuth1: 0.559776067733765
Knuth2: 0.531576871871948

という訳で、今回はランダムなデータ列で計測しましたが、
相変わらず、Perlの組み込み関数には勝てないものの、
最初の実装と比べると、だいぶ改善されています。
ただし、処理時間はデータ列に依存するので、
本来であれば、n回計測して平均を取る必要があります。

間隔を、1,2,4,8, ... でソートしてしまうと、
例えば、間隔が4以上の間は、
0,4,8 ... と、1,5,9, ... と、2,6,10, ... と、
3,7,11, ... のグループ単位でソートされてしまうので、
こういうのを防ぎながら、混ぜ合わせつつソートするために、
ソースコードのような間隔の計算を行っています。

たしかに、混ざり合わないと、例に挙げたグループのうち、
2グループには大きな数字が多く含まれていて、
残りの2グループには小さな数字が多く含まれていると、
間隔が1になっても、あまりソートされていないデータ列が出来てしまう気もしますが、
それを直感的に理解できるかと言われると、自分には難しいです。

という訳で、もうしばらくはシェルソートで引っ張る予定です。

おしまい。

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