railsinstaller - ruby on rails

Es ordenar en Ruby estable?

Question

Es sort en Ruby estable? Es decir, para los elementos que están en un empate para el sort , ¿se conserva el orden relativo entre ellos del orden original? Por ejemplo, dado:

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

¿Está garantizado que siempre conseguimos para

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

el seguimiento

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

sin ninguna variación para el orden relativo entre los elementos con el valor :id :d :f , y entre :b :e :g , y entre :c :h ? Si ese es el caso, ¿en qué parte de la documentación se describe?

Esta pregunta puede o no tener conexión con esta pregunta .

Answer 1

No, el tipo incorporado de ruby ​​no es estable.

Si quieres una clasificación estable, esto debería funcionar. Es probable que desee crear un método si lo va a usar a menudo.

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

Básicamente, realiza un seguimiento del índice de matriz original de cada elemento y lo utiliza como un desempate cuando h[:int] es el mismo.

Más información, para los curiosos:

Hasta donde yo sé, usar el índice de matriz original como el desempate es la única manera de garantizar la estabilidad cuando se usa una clasificación inestable. Los atributos reales (u otros datos) de los artículos no le indicarán su orden original.

Su ejemplo es algo inventado porque las claves :id están ordenadas de forma ascendente en la matriz original. Supongamos que la matriz original se ordenó descendiendo por :id ; querrías que :id ''s en el resultado esté descendiendo cuando desempates, así:

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

Usar el índice original también manejará esto.

Actualizar:

La sugerencia de Matz (ver esta página ) es similar, y puede ser ligeramente más eficiente que la anterior:

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

Answer 2

Para algunas implementaciones de Ruby, el género es estable, pero no debes depender de él. La estabilidad del género de Ruby está definida por la implementación.

Lo que dice la documentación

La documentación dice que no debe depender de que el género sea estable:

El resultado no está garantizado para ser estable. Cuando la comparación de dos elementos devuelve 0, el orden de los elementos es impredecible.

Tenga en cuenta que esto no dice si el tipo es estable o no. Simplemente dice que no se garantiza que sea estable. Cualquier implementación dada de Ruby podría tener un tipo estable y ser consistente con la documentación. También podría tener una clasificación inestable o cambiar si el género es estable en cualquier momento.

Lo que Ruby realmente hace

Este código de prueba se imprime true si el género de Ruby es estable, o false si no lo es:

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]

Aquí están los resultados de todos los Rubies que he instalado en mi caja de 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]

Podemos ver que JRuby es inestable, y MRI antes de 2.2, en Linux, es inestable. MRI> = 2.2.0 es estable (nuevamente, en Linux).

La plataforma importa, sin embargo. Aunque el resultado anterior muestra que el género es estable en MRI 2.4.1 en Linux, la misma versión es inestable en Windows:

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

¿Por qué el tipo de MRI es estable en Linux, pero no en Windows?

Incluso dentro de una única versión de una implementación de Ruby, el algoritmo de ordenamiento puede cambiar. La MRI puede usar al menos tres géneros diferentes. La rutina de ordenación se selecciona en tiempo de compilación usando una serie de #ifdefs en util.c Parece que MRI tiene la capacidad de utilizar géneros de al menos dos bibliotecas diferentes. También tiene su propia implementación.

Que deberias hacer al respecto?

Como el género puede ser estable pero no puede garantizarse que sea estable, no escriba código que dependa de que el género de Ruby sea estable. Ese código podría romperse cuando se usa en una versión, implementación o plataforma diferente.

Answer 3

Tanto el tipo de MRI como el sort_by son unstable . Hace algún tiempo hubo una request para hacerlos estables, pero fue rechazado; la razón es que Ruby usa un algoritmo de quicksort in situ , que funciona mejor si no se requiere estabilidad. Tenga en cuenta que aún puede implementar métodos estables a partir de los inestables:

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 4

personalmente no contaría con esto. ¿Qué tal si haces algo como esto?

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