Стабильна ли сортировка в Ruby?
Является sort в Ruby стабильно? То есть для элементов, которые в галстуке для 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 ответа
И 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
Нет, встроенная сортировка ruby не стабильна.
Если вы хотите стабильную сортировку, это должно работать. Возможно, вы захотите создать для него метод, если будете часто его использовать.
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}
]
Использование исходного индекса также справится с этим.
Обновить:
Собственное предложение Матца (см. Эту страницу) похоже и может быть несколько более эффективным, чем приведенное выше:
n = 0
ary.sort_by {|x| n+= 1; [x, n]}
Для некоторых реализаций Ruby сортировка стабильна, но вы не должны зависеть от нее. Устойчивость сортировки в 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]
Вот результаты для всех Ruby, которые я установил на мою Linux-коробку:
["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 нестабилен, а MRI до 2.2 в Linux нестабилен. MRI >= 2.2.0 стабильно (опять же в Linux).
Платформа имеет значение, хотя. Хотя приведенный выше результат показывает, что сортировка стабильна в MRI 2.4.1 в Linux, эта же версия нестабильна в Windows:
["x64-mingw32", "2.4.1", 111, false]
Почему сортировка MRI стабильна в Linux, но не в Windows?
Даже в пределах одной версии реализации Ruby алгоритм сортировки может измениться. МРТ может использовать как минимум три разных вида. Процедура сортировки выбирается во время компиляции, используя серию #ifdefs в util.c. Похоже, что МРТ имеет возможность использовать сортировки по крайней мере из двух разных библиотек. У него также есть своя реализация.
Что с этим делать?
Поскольку сортировка может быть стабильной, но нельзя гарантировать ее стабильность, не пишите код, который зависит от стабильности сортировки в Ruby. Этот код может сломаться при использовании на другой версии, реализации или платформе.
Лично я бы на это не рассчитывал. Как насчет того, чтобы сделать что-то вроде этого:
a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }