シェルソートを書いてみた（後編）
かの有名なクヌース先生の力を借りて、
適切な間隔でシェルソートを行ってみました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | 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になっても、あまりソートされていないデータ列が出来てしまう気もしますが、
それを直感的に理解できるかと言われると、自分には難しいです。
という訳で、もうしばらくはシェルソートで引っ張る予定です。
おしまい。
Leave a Comment