L'ordinamento è stabile in Ruby?

Question

sort nella stalla Ruby? Cioè, per gli elementi che sono in un pareggio per sort, l'ordine relativo tra loro è conservato dall'ordine originale? Ad esempio, dato:

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

è garantito che abbiamo sempre per

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

seguente

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

senza alcuna variazione per l'ordine relativo tra gli elementi con valore :id:d, :f e tra :b, :e, :g e tra :c, :h? Se questo è il caso, dove nella documentazione è descritto?

Questa domanda può o non può avere connessione con this question.

Answer 1

s' sort e sort_by Entrambi MRI sono unstable. Qualche tempo fa c'era un request per renderli stabili, ma è stato respinto; il motivo è che Ruby usa uno in-place quicksort algorithm, che offre prestazioni migliori se non è richiesta la stabilità. Si noti che è ancora possibile implementare metodi stabili da quelli instabili:

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

personalmente non ci conterei. Come attacco facendo qualcosa di simile:

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

Answer 3

No, l'ordinamento incorporato di ruby ​​non è stabile.

Se si desidera un ordinamento stabile, questo dovrebbe funzionare. Probabilmente vorresti creare un metodo per questo se lo userai spesso.

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

Fondamentalmente si registra l'indice di campo originale di ogni elemento, e utilizza come un tie-breaker quando h[:int] è lo stesso.

Ulteriori informazioni, per i curiosi:

quanto ne so, utilizzando l'indice dell'array originale come tie-breaker è l'unico modo per garantire la stabilità quando si utilizza un ordinamento instabile. Gli attributi attuali (o altri dati) degli articoli non ti diranno il loro ordine originale.

L'esempio è un po 'forzato perché le chiavi :id sono ordinate in ordine crescente nell'array originale. Supponiamo che l'array originale sia stato ordinato decrescente per :id; che ci si vuole i :id 's nel risultato di essere discendente quando tie-rottura, in questo modo:

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

Utilizzando l'indice originale gestirà anche questo.

Aggiornamento: proprio suggerimento

di Matz (vedi this page) è simile, e può essere un po 'più efficiente di quanto sopra:

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

Answer 4

Per alcune implementazioni di Ruby, specie è stabile, ma non dovresti dipendere da questo. La stabilità di Ruby è definita dall'implementazione.

Cosa dice la documentazione

The documentation dice che non si deve dipendere sorta essere stabile:

Il risultato non è garantito per essere stabile. Quando il confronto di due elementi restituisce 0, l'ordine degli elementi è imprevedibile.

Si noti che questo non dice se l'ordinamento è stabile o meno. Dice solo che non è garantito che sia stabile. Qualsiasi implementazione data di Ruby potrebbe avere un ordinamento stabile e comunque essere coerente con la documentazione. Potrebbe anche avere un ordinamento instabile o cambiare se l'ordinamento è stabile in qualsiasi momento.

Cosa Rubino realmente fa

stampe codice

Questa prova true se sorta di Ruby è stabile, o false se non è:

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] 

Ecco i risultati per tutti i rubini che ho installato su la mia macchina 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] 

possiamo vedere che JRuby è instabile, e la risonanza magnetica prima di 2,2, su Linux, è instabile. MRI> = 2.2.0 è stabile (di nuovo, su Linux).

La piattaforma è importante. Anche se il risultato di cui sopra dimostra che tipo è stabile nelle MRI 2.4.1 su Linux, la stessa versione è instabile su Windows:

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

Perché è di risonanza magnetica ordinamento stabile su Linux, ma non su Windows?

Anche all'interno di una singola versione di un'implementazione di Ruby, l'algoritmo di ordinamento può cambiare. La risonanza magnetica può utilizzare almeno tre diversi tipi. La routine di ordinamento viene selezionata in fase di compilazione utilizzando una serie di #ifdefs in util.c. Sembra che la risonanza magnetica abbia la possibilità di utilizzare i tipi da almeno due diverse librerie. Ha anche una sua implementazione.

Cosa dovresti fare al riguardo?

Poiché l'ordinamento può essere stabile ma non può essere garantito stabile, non scrivere codice che dipenda dal fatto che il tipo di Ruby sia stabile. Tale codice potrebbe interrompersi se utilizzato su una versione, un'implementazione o una piattaforma diversa.