Ruby中的排序是否稳定？

Question

是sortRuby的稳定吗？也就是说,对于处于平局状态的元素,它们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？如果是这种情况,文档中的描述是什么？

这个问题可能与此问题有关,也可能没有.

Answer 1

无论MRI的排序和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

Answer 2

不,ruby的内置排序不稳定.

如果你想要稳定的排序,这应该工作.如果你经常使用它,你可能想为它创建一个方法.

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

基本上它跟踪每个项目的原始数组索引,并在相同时将其用作打破平局h[:int].

更多信息,对于好奇:

据我所知,使用原始数组索引作为决胜局是使用不稳定排序时保证稳定性的唯一方法.项目的实际属性(或其他数据)不会告诉您原始订单.

你的例子有点人为,因为:id键在原始数组中按升序排序.假设原始数组按降序排序:id; :id打破平局时,你希望结果中的's'降序,就像这样:

[
 {: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]}

Answer 3

对于Ruby的某些实现,sort是稳定的,但你不应该依赖它.Ruby的排序的稳定性是实现定义的.

文档说的是什么

文档说你不应该依赖于排序稳定:

结果不能保证稳定.当两个元素的比较返回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]

我们可以看到JRuby不稳定,在Linux上2.2之前的MRI是不稳定的.MRI> = 2.2.0是稳定的(再次,在Linux上).

但平台很重要.虽然上面的结果表明在Linux上的MRI 2.4.1中排序是稳定的,但同样的版本在Windows上不稳定:

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

为什么MRI在Linux上排序稳定,但在Windows上却不稳定？

即使在Ruby实现的单个版本中,排序算法也可以改变.MRI可以使用至少三种不同的种类.在编译时使用util.c中的一系列#ifdefs选择排序例程.看起来MRI有能力使用来自至少两个不同库的种类.它也有自己的实现.

你应该怎么做？

由于排序可能是稳定的,但不能保证稳定,因此不要编写依赖于Ruby排序稳定的代码.在不同版本,实现或平台上使用时,该代码可能会中断.