46

Rubyはsort安定していますか？つまり、と同点の要素の場合、sortそれらの間の相対的な順序は元の順序から保持されますか？たとえば、次のようになります。

a = [
  {id: :a, int: 3},
  {id: :b, int: 1},
  {id: :c, int: 2},
  {id: :d, int: 0},
  {id: :e, int: 1},
  {id: :f, int: 0},
  {id: :g, int: 1},
  {id: :h, int: 2},
]

私たちが常に得ることが保証されていますか

a.sort_by{|h| h[:int]}

以下

[
  {id: :d, int: 0},
  {id: :f, int: 0},
  {id: :b, int: 1},
  {id: :e, int: 1},
  {id: :g, int: 1},
  {id: :c, int: 2},
  {id: :h, int: 2},
  {id: :a, int: 3},
]

:id値が:d、、の要素間、および、、、の間、および、の間の相対的な順序に変化はあり:fませ:bんか？その場合、ドキュメントのどこに記載されていますか？:e:g:c:h

この質問は、この質問と関連がある場合とない場合があります。

4

4 に答える 4

60

MRIのsortとsort_byはどちらも不安定です。少し前に安定させたいという要望がありましたが、却下されました。理由：Rubyはインプレースクイックソートアルゴリズムを使用しており、安定性が必要ない場合はパフォーマンスが向上します。不安定なメソッドから安定したメソッドを実装できることに注意してください。

module Enumerable
  def stable_sort
    sort_by.with_index { |x, idx| [x, idx] }
  end

  def stable_sort_by
    sort_by.with_index { |x, idx| [yield(x), idx] }
  end
end
于 2013-03-15T22:17:11.690 に答える
18

いいえ、ルビーの組み込みソートは安定していません。

安定したソートが必要な場合、これは機能するはずです。頻繁に使用する場合は、そのためのメソッドを作成することをお勧めします。

a.each_with_index.sort_by {|h, idx| [h[:int], idx] }.map(&:first)

基本的に、各アイテムの元の配列インデックスを追跡しh[:int]、同じ場合はタイブレーカーとして使用します。

好奇心旺盛な方のための詳細情報：

私の知る限り、不安定なソートを使用する場合の安定性を保証する唯一の方法は、タイブレーカーとして元の配列インデックスを使用することです。アイテムの実際の属性（またはその他のデータ）では、元の順序はわかりません。

:idキーは元の配列で昇順で並べ替えられるため、この例は多少工夫されています。:id元の配列が;の降順で並べ替えられたとします。次:idのように、タイブレーク時に結果の'が降順になるようにします。

[
 {:id=>:f, :int=>0},
 {:id=>:d, :int=>0},
 {:id=>:g, :int=>1},
 {:id=>:e, :int=>1},
 {:id=>:b, :int=>1},
 {:id=>:h, :int=>2},
 {:id=>:c, :int=>2},
 {:id=>:a, :int=>3}
]

元のインデックスを使用すると、これも処理されます。

アップデート：

Matz自身の提案（このページを参照）も同様であり、上記よりもわずかに効率的である可能性があります。

n = 0
ary.sort_by {|x| n+= 1; [x, n]}
于 2013-03-21T16:10:26.310 に答える
11

Rubyの一部の実装では、並べ替えは安定していますが、それに依存するべきではありません。Rubyのソートの安定性は、実装によって定義されます。

ドキュメントの内容

ドキュメントには、ソートが安定していることに依存すべきではないと書かれています。

結果は安定しているとは限りません。2つの要素の比較が0を返す場合、要素の順序は予測できません。

これは、ソートが安定しているかどうかを示すものではないことに注意してください。安定しているとは限らないというだけです。Rubyの特定の実装は、安定したソートを持ち、それでもドキュメントと一貫性がある可能性があります。また、ソートが不安定になったり、ソートがいつでも安定するかどうかが変わる可能性があります。

Rubyが実際に行うこと

このテストコードはtrue、Rubyの並べ替えが安定しfalseている場合、または安定していない場合に出力されます。

Foo = Struct.new(:value, :original_order) do
  def <=>(foo)
    value <=> foo.value
  end
end

size = 1000
unsorted = size.times.map do |original_order|
  value = rand(size / 10)
  Foo.new(value, original_order)
end
sorted = unsorted.sort
stably_sorted = unsorted.sort_by do |foo|
  [foo.value, foo.original_order]
end
p [RUBY_PLATFORM, RUBY_VERSION, RUBY_PATCHLEVEL, sorted == stably_sorted]

LinuxボックスにインストールしたすべてのRubiesの結果は次のとおりです。

["java", "1.8.7", 357, false]
["java", "1.9.3", 551, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 376, false]
["x86_64-linux", "1.9.3", 392, false]
["x86_64-linux", "1.9.3", 484, false]
["x86_64-linux", "1.9.3", 551, false]
["x86_64-linux", "2.0.0", 643, false]
["x86_64-linux", "2.0.0", 648, false]
["x86_64-linux", "2.1.0", 0, false]
["x86_64-linux", "2.1.10", 492, false]
["x86_64-linux", "2.1.1", 76, false]
["x86_64-linux", "2.1.2", 95, false]
["x86_64-linux", "2.1.3", 242, false]
["x86_64-linux", "2.1.4", 265, false]
["x86_64-linux", "2.1.5", 273, false]
["x86_64-linux", "2.1.6", 336, false]
["x86_64-linux", "2.1.7", 400, false]
["x86_64-linux", "2.1.8", 440, false]
["x86_64-linux", "2.1.9", 490, false]
["x86_64-linux", "2.2.0", 0, true]
["x86_64-linux", "2.2.1", 85, true]
["x86_64-linux", "2.2.2", 95, true]
["x86_64-linux", "2.2.3", 173, true]
["x86_64-linux", "2.2.4", 230, true]
["x86_64-linux", "2.2.5", 319, true]
["x86_64-linux", "2.2.6", 396, true]
["x86_64-linux", "2.3.0", 0, true]
["x86_64-linux", "2.3.1", 112, true]
["x86_64-linux", "2.3.2", 217, true]
["x86_64-linux", "2.3.3", 222, true]
["x86_64-linux", "2.4.0", 0, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.1", 111, true]
["x86_64-linux", "2.4.2", 198, true]
["x86_64-linux", "2.4.5", 335, true]
["x86_64-linux", "2.4.9", 362, true]
["x86_64-linux", "2.5.0", 0, true]
["x86_64-linux", "2.5.3", 105, true]
["x86_64-linux", "2.5.7", 206, true]
["x86_64-linux", "2.6.0", 0, true]
["x86_64-linux", "2.6.2", 47, true]
["x86_64-linux", "2.6.3", 62, true]
["x86_64-linux", "2.6.4", 104, true]
["x86_64-linux", "2.6.5", 114, true]
["x86_64-linux", "2.6.6", 146, true]
["x86_64-linux", "2.7.0", 0, true]
["x86_64-linux", "2.7.1", 83, true]
["x86_64-linux", "2.7.2", 137, true]
["x86_64-linux", "3.0.0", 0, true]
["x86_64-linux", "3.0.0", -1, true]
["x86_64-linux", "3.0.1", 64, true]
["x86_64-linux", "3.0.2", 107, true]

LinuxではJRubyが不安定で、2.2より前のMRIが不安定であることがわかります。MRI> = 2.2.0は安定しています（これもLinux上で）。

ただし、プラットフォームは重要です。上記の結果は、LinuxのMRI 2.4.1でソートが安定していることを示していますが、同じバージョンはWindowsでは不安定です。

["x64-mingw32", "2.4.1", 111, false]

LinuxではMRIのソートが安定しているのに、Windowsでは安定していないのはなぜですか？

Ruby実装の単一バージョン内であっても、ソートアルゴリズムは変更される可能性があります。MRIは、少なくとも3つの異なる種類を使用できます。ソートルーチンは、 util.cの一連の#ifdefを使用してコンパイル時に選択されます。MRIには、少なくとも2つの異なるライブラリからのソートを使用する機能があるようです。また、独自の実装があります。

あなたはそれについて何をすべきですか？

ソートは安定している可能性がありますが、安定性を保証することはできないため、Rubyのソートが安定していることに依存するコードを記述しないでください。そのコードは、別のバージョン、実装、またはプラットフォームで使用すると破損する可能性があります。

于 2017-06-11T17:14:55.893 に答える
-4

個人的に私はこれを当てにしません。このようなことをするのはどうですか：

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }
于 2013-03-15T21:49:13.560 に答える