Czy sortowanie w Ruby jest stabilne?

Question

Czy sort w stabilnej wersji? Oznacza to, że dla elementów, które są w remisie dla sort, czy ich kolejność zachowana jest od pierwotnej kolejności? Na przykład, biorąc pod uwagę:

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}, 
] 

jest to zagwarantowane, że zawsze dostać za

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

następujące

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

bez zmienności względnego porządku wśród elementów o wartości :id:d, :f i spośród :b, :e, :g, oraz spośród :c, :h? Jeśli tak, to gdzie w dokumentacji jest to opisane?

To pytanie może lub może nie mieć związku z this question.

Answer 1

Zarówno MRI „s sort i sort_by są unstable. Jakiś czas temu było request, aby były stabilne, ale zostało odrzucone; Powodem jest to, że Ruby używa in-place quicksort algorithm, która działa lepiej, gdy stabilność nie jest wymagana. Zauważ, że nadal możesz wdrożyć stabilne metody z niestabilnych:

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

osobiście nie będę na to liczył. Jak walka robi coś takiego:

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] } 

Answer 3

Nie, wbudowany rodzaj ruby ​​nie jest stabilny.

Jeśli chcesz sortować stabilnie, powinno to działać. Prawdopodobnie chcesz go utworzyć, jeśli będziesz go często używać.

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

Zasadniczo śledzi pierwotnego wskaźnika tablicy każdego elementu i wykorzystuje go jako rozstrzygające gdy h[:int] jest taka sama.

Więcej informacji dla ciekawskich:

O ile mi wiadomo, z wykorzystaniem oryginalnego indeks tablicy jako tie-breaker to jedyny sposób, aby zagwarantować stabilność podczas korzystania niestabilny sortowania. Rzeczywiste atrybuty (lub inne dane) przedmiotów nie będą zawierały oryginalnego zamówienia.

Twój przykład jest nieco spreparowany, ponieważ klucze :id posortowane są rosnąco w oryginalnej tablicy. Załóżmy, że pierwotna tablica została posortowana malejąco według :id; że chcesz tego :id JEST W rezultacie będzie malejąco po tie-breaking, tak:

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

Korzystanie oryginalny indeks zajmie to zbyt.

Aktualizacja: własna sugestia

Matz (patrz this page) jest podobna, a może być nieco bardziej wydajny niż powyższe:

n = 0 
ary.sort_by {|x| n+= 1; [x, n]} 

Answer 4

Dla niektórych implementacjach Ruby, sortowania jest stabilna, ale nie powinieneś na tym polegać. Stabilność sortowania Ruby jest zdefiniowana przez implementację.

Co mówi dokumentacja

The documentation mówi, że nie powinno zależeć sortowania jest stabilna:

Wynik nie jest gwarancją stabilny. Gdy porównanie dwóch elementów zwraca 0, kolejność elementów jest nieprzewidywalna.

Należy zauważyć, że nie oznacza to, czy sortowanie jest stabilne. Po prostu mówi, że nie ma gwarancji, że będzie stabilny. Każda konkretna implementacja Rubiego może być stabilna i nadal zgodna z dokumentacją. Może również mieć niestabilny rodzaj lub zmienić, czy sortowanie jest stabilne w dowolnym momencie.

Co Ruby faktycznie robi

Ten test wydruki kodu true jeśli sortowania Ruby jest stabilny, czy false jeśli to nie jest:

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] 

Poniżej znajdują się wyniki dla wszystkich Rubiny mam zainstalowane na moim Linuksie:

["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] 

Widzimy, że JRuby jest niestabilny, a MRI przed 2.2, Linux, jest niestabilny. MRI> = 2.2.0 jest stabilny (ponownie, w systemie Linux).

Platforma ma jednak znaczenie. Chociaż powyższy wynik pokazuje, że porządek jest stabilny w MRI 2.4.1 w systemie Linux, ta sama wersja jest niestabilna w systemie Windows:

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

Dlaczego MRI rodzaj stabilny na Linuksie, ale nie na Windows?

Nawet w pojedynczej wersji implementacji Ruby algorytm sortowania może się zmienić. MRI może wykorzystywać co najmniej trzy różne rodzaje. Procedura sortowania jest wybierana podczas kompilacji przy użyciu serii #ifdefs w util.c. Wygląda na to, że MRI ma możliwość korzystania z sortów z co najmniej dwóch różnych bibliotek. Ma również własną implementację.

Co należy z tym zrobić?

Ponieważ sortowanie może być stabilne, ale nie można zagwarantować, że jest stabilne, nie należy pisać kodu, który zależy od stabilności sortowania Ruby. Ten kod mógł zostać złamany, gdy jest używany w innej wersji, implementacji lub platformie.