はじめに
Linux環境において(他の環境は未検証)、古いruby(1.8.7など)と新しいruby(3.3.0など)で配列のソート結果に違いが出るという、現代を生きている方には特に役に立たない情報についての共有です。
検証コード
ruby1.8.7でもruby3.3.0でも同じコードが実行可能なように、古い書き方で記述しておきます。
[
{:name => 'elm1', :val => 1},
{:name => 'elm2', :val => 5},
{:name => 'elm3', :val => 3},
{:name => 'elm4', :val => 1},
{:name => 'elm5', :val => 2},
{:name => 'elm6', :val => 6},
{:name => 'elm7', :val => 2},
{:name => 'elm8', :val => 7},
{:name => 'elm9', :val => 4},
{:name => 'elm10', :val => 3},
].sort_by { |x| x[:val] }
ruby1.8.7での実行結果
ruby1.8.7上で実行すると、以下の配列が得られました。
[
{:val=>1, :name=>"elm1"},
{:val=>1, :name=>"elm4"},
{:val=>2, :name=>"elm7"},
{:val=>2, :name=>"elm5"},
{:val=>3, :name=>"elm3"},
{:val=>3, :name=>"elm10"},
{:val=>4, :name=>"elm9"},
{:val=>5, :name=>"elm2"},
{:val=>6, :name=>"elm6"},
{:val=>7, :name=>"elm8"}
]
ruby3.3.0での実行結果
ruby3.3.0で実行すると、以下の配列が得られました。
[
{:name=>"elm1", :val=>1},
{:name=>"elm4", :val=>1},
{:name=>"elm5", :val=>2},
{:name=>"elm7", :val=>2},
{:name=>"elm3", :val=>3},
{:name=>"elm10", :val=>3},
{:name=>"elm9", :val=>4},
{:name=>"elm2", :val=>5},
{:name=>"elm6", :val=>6},
{:name=>"elm8", :val=>7}
]
なぜ違いが出るのか？
ruby1.8.7のソート実装
ruby1.8.7のソート実装を探すと、最終的にここに辿り着きます。
https://github.com/ruby/ruby/blob/ruby_1_8_7/util.h
https://github.com/ruby/ruby/blob/ruby_1_8_7/util.c
ruby_qsortという関数が定義されており、教科書的な再帰関数による実装ではないもののクイックソート実装であることがわかります。
ruby3.3.0のソート実装
ruby3.3.0のソート実装を探すと、最終的にここに辿り着きます。
https://github.com/ruby/ruby/blob/ruby_3_3/include/ruby/util.h
https://github.com/ruby/ruby/blob/ruby_3_3/util.c
ruby1.8.7と比較するとプリプロセッサによる分岐が多数含まれています。一般的なLinux環境(glibcを使う環境)においてはutil.hのこの部分の記述でglibcのqsort_r関数を使う様です。
/**
* Reentrant implementation of quick sort. If your system provides something
* (like C11 qsort_s), this is a thin wrapper of that routine. Otherwise
* resorts to our own version.
*/
#ifdef HAVE_GNU_QSORT_R
# define ruby_qsort qsort_r
#else
void ruby_qsort(void *, const size_t, const size_t,
int (*)(const void *, const void *, void *), void *);
#endif
以上により、異なる実装のクイックソートが使われるためにソート結果が異なる、という事の様です。
……本当にそれで全て解決でしょうか？もう一度ruby1.8.7とruby3.3.0のソート結果を見てみましょう。ruby1.8.7のソート結果ではelm7がelm5より前になるなど、valが同じ要素の順番が元の配列の登場順にならない場合がある一方で、ruby3.3.0ではその様な箇所が見られません。
glibc qsort_rについて
glibcのqsort_r関数についても少し調べてみましょう。qsortの名前からはクイックソートの実装であることが連想されますが、本当にそうなのでしょうか。
github上のものは非公式のミラーだそうですが、ここでglibcの実装を見てみます。
https://github.com/bminor/glibc/blob/master/stdlib/qsort.c
ちゃんと読めてないのですが、ざっくりとこういう動きをしてそうです。
- 一時領域の確保に成功する場合マージソート
- 一時領域の確保が失敗する場合(非常に大きな配列の場合)ヒープソートにフォールバック
多くの場合はマージソートで動作しそうなので、glibcのソートアルゴリズムはマージソート、という事にします。
ソートアルゴリズムの安定性
ソートアルゴリズムによって、並び替え前の順位が同等な複数のデータの前後関係がソート後に保持されるかされないかが変わります。保持されるものを安定なソートと呼びます。
マージソートは安定なソートアルゴリズムに分類され、クイックソートは安定でないソートアルゴリズムに分類されます。
つまり、ruby1.8.7では安定でないクイックソートでソートが行われ、ruby3.3.0では安定なマージソートでソートが行われるため、ソート結果に違いが出る、というのが真相のようです。
いつからこうなってる？
ruby2.2.0のChangeLogに use qsort_r() as ruby_qsort() if it is GNU version.という記述があり、これ以降のリリースでソート関数の実装を使い分けるようになっているようです。
https://docs.ruby-lang.org/en/2.3.0/ChangeLog-2_2_0.html#label-Sat+Feb++8+21-3A44-3A07+2014++Masaki+Matsushita++-3Cglass.saga-40gmail.com-3E