読者です 読者をやめる 読者になる 読者になる

perlの5.6と5.8ではソートアルゴリズムが違う

5.6まではクイックソート、5.7からはマージソートみたいです。

$ perldoc -f sort
...
Perl 5.6 and earlier used a quicksort algorithm ...
In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm...
...


何かまずいの??と言われればマージソートは安定だけどクイックソートは非安定、ということです。非安定なソートアルゴリズムはソート前の並びを保持しないので複合型に対するソート結果が変わってきます。


例として・・・
[1,'c'], [5,'b'], [3,'a'],...みたいな数字と文字のセットの配列を考えます。まず文字をキーにソートして、続いて数字でソートするとどうなるでしょうか。

テストスクリプト
srand 1;
## @arr = ([1,c], [5,b], [3,a], ...)
push @arr, [(1..5)[rand 5], (a..z)[rand 5]] for 1..10;

print "before ...\n";
print join(', ', map "[@$_]", @arr)."\n";

## まずはアルファベットでソート
@arr = sort {$$a[1] cmp $$b[1]} @arr;
## 続いて数字でソート
@arr = sort {$$a[0] <=> $$b[0]} @arr;

print "sort ...\n";
print join(', ', map "[@$_]", @arr)."\n";
結果
$ perl5.8.8 sort.pl 
before ...
[1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a]
sort ...
[1 a], [1 c], [1 e], [2 c], [3 a], [3 b], [4 b], [5 a], [5 a], [5 b]

$ perl5.6.2 sort.pl 
before ...
[1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a]
sort ...
[1 c], [1 a], [1 e], [2 c], [3 b], [3 a], [4 b], [5 a], [5 b], [5 a]


[1 a], [1 c], [1 e] と [1 c], [1 a], [1 e]を比べてもらえば一目瞭然。
5.8.8ではアルファベット順が保持されてますが5.6.2だとグチャグチャです。



じゃどうすれば?と言われればこの例では簡単。1回で両方比較してやればいいだけです。

srand 1;
push @arr, [(1..5)[rand 5], (a..z)[rand 5]] for 1..10;

print "before ...\n";
print join(', ', map "[@$_]", @arr)."\n";

##  まず数値を比較、同じなら文字を比較
@arr = sort {$$a[0] <=> $$b[0] or $$a[1] cmp $$b[1]} @arr;
print "sort by alpha and number ...\n";
print join(', ', map "[@$_]", @arr)."\n";
$ perl5.8.8 sort.pl 
before ...
[1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a]
sort by alpha and number ... ...
[1 a], [1 c], [1 e], [2 c], [3 a], [3 b], [4 b], [5 a], [5 a], [5 b]

$ perl5.6.2 sort.pl 
before ...
[1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a]
sort by alpha and number ... ...
[1 a], [1 c], [1 e], [2 c], [3 a], [3 b], [4 b], [5 a], [5 a], [5 b]

ちなみに他の言語は例えばこんな感じです。


メモリ容量の増大と(マージソートの欠点はメモリを食うこととされてました)、ソート対象がオブジェクトなどの複合型になるにつれてクイックソートからマージソートに移り変わってきてるみたいですね。