ruby sort_by descending

¿Cómo funciona Ruby sort_by{rand}?

Question

Creo que este es un gran Ruby de una sola línea:

someArray.sort_by {rand}

Es conciso, es legible y funciona, pero no entiendo muy bien cómo. Esto es lo que sé:

1. rand evalúa como un número entre 0 y 1 (como 0.783468632804653)
2. rand se está evaluando repetidamente en el código anterior, porque asignarlo a x primero interrumpe la ordenación aleatoria
3. sort_by {0.783468632804653} , o cualquier otro número que probé, no tiene ningún efecto en la matriz

ruby-doc.org no fue de mucha ayuda para mí en este caso .

¿Alguien puede explicar esto paso a paso?

Actualizar

He estado usando Ruby por más tiempo ahora, y veo que me faltaba uno o dos conceptos aquí. La clave es que:

1. rand es un método (definido en Kernel); genera un número aleatorio
2. {rand} es un bloque que sort_by mantiene y lo llama cada vez que quiere comparar dos elementos de la colección. Si la colección es un conjunto de objetos que representan países, debe poder tomar dos de ellos y determinar cuál es el primero. ¿Pones el que tiene el nombre más largo primero? ¿El que tiene la mayor masa de tierra? El bloque debe responder a esa pregunta devolviendo un valor que dice "usted preguntó sobre España vs Camerún, y yo digo que Camerún es lo primero". (Podrías hacer eso con {|country| country.name.length}

El resto de cómo funciona sort_by se explica en la documentación. Todavía no estoy del todo seguro de por qué devolver un número aleatorio funciona en absoluto. Supuestamente, sort_by redondea a -1, 0 o 1, ¿cuál es el más cercano? Pero en cualquier caso, obtener un número aleatorio diferente cada vez que llama al bloqueo es bastante diferente de obtener el mismo número cada vez. Cuando sort_by dice "¿cuál de estos dos países viene primero?", {rand} pone una venda en los ojos, gira 10 veces, apunta y dice "¡esa!" :)

Answer 1

El bloque rand produce una clave que se utiliza en la clasificación. Es diferente cada vez que se evalúa, así que obtienes un orden aleatorio.

Cuando coloca un solo número allí, es el mismo cada vez, por lo que el orden no cambia. Eso significa que el algoritmo de clasificación es ''estable'', no mueve las entradas en orden.

Y aquí hay un código aún más corto, incluso más claro:

someArray.shuffle

Answer 2

En Ruby 1.8 / 1.9, tanto sort como sort_by se implementan en C, esto es un equivalente aproximado de cómo funciona esto:

Digamos que empiezas con [1,2,3,4] y llamas sort_by{rand} :

1. (Inventé algunos números al azar):

   Se crea una matriz de tuplas: [[0.12232, 1],[0.53434, 2],[0.333, 3],[0.99, 4]]

   En un código Ruby más o menos equivalente, esto es: [1,2,3,4].map{|x| [rand, x]} [1,2,3,4].map{|x| [rand, x]}

2. La ordenación rápida de Ruby se realiza en el arreglo basado en el primer elemento: (note que la implementación interna está lejos de ser trivial y contiene una tonelada de optimizaciones para arreglos ya ordenados y demás)

   [[0.12232, 1],[0.333, 3],[0.53434, 2],[0.99, 4]]

   En Ruby en bruto, este paso es: ary.sort{|x,y| x[0] <=> y[0]} ary.sort{|x,y| x[0] <=> y[0]}

3. Los punteros se copian de la nueva matriz ordenada, a la posición correcta en la matriz original.

   [1,3,2,4]

   En Ruby en bruto, este paso es: ary.map{|x,y| y} ary.map{|x,y| y}

Esta técnica a veces se denomina " Transformada de Schwartz ". El almacenamiento en caché significa que la operación costosa no se realiza más de N veces. Es decir, esta es una forma muy eficiente de aleatorizar una matriz.

Nota : array.shuffle! será la forma integrada más eficiente de barajar una matriz (en el lugar) ya que utiliza una versión moderna de Fisher-Yates :

static VALUE
rb_ary_shuffle_bang(VALUE ary)
{
long i = RARRAY_LEN(ary);
rb_ary_modify(ary);
while (i) {
long j = rb_genrand_real()*i;
VALUE tmp = RARRAY_PTR(ary)[--i];
RARRAY_PTR(ary)[i] = RARRAY_PTR(ary)[j];
RARRAY_PTR(ary)[j] = tmp;
}
return ary;
}

Answer 3

Lo que sort_by puede dividir en dos simples pasos:

1. Llama al método map / collect en la matriz provista y con el bloque provisto . En su caso, el resultado sería solo una matriz de números aleatorios; llamemos a esta matriz intermedia A1. Tenga en cuenta que tiene la longitud de la matriz inicial.

2. A1 se ordena normalmente, pero lo que se devuelve no es el A1 ordenado, sino la matriz original, donde los elementos se mueven de la misma manera que los correspondientes de A1, mientras se ordenan.

Así es como funciona el siguiente ejemplo:

["Paulo", "Sergito", "Nick"].sort_by {|word| word.length} 

Ordena las palabras por su longitud, porque primero la matriz de palabras se asigna en una matriz de longitudes, y esas longitudes se clasifican, mientras que las palabras en la matriz original se mueven de manera correspondiente.

Answer 4

sort_by es un refinamiento de sort , que se usa así:

people.sort do |person1, person2|
person1 <=> person2
end

La función de sort cede al bloque cuando necesita saber el orden de dos cosas, en este caso, personas. El bloque devuelve -1 si la cosa izquierda es menor que la derecha, 0 si son iguales y 1 si la cosa derecha es más grande que la izquierda. El operador de la nave espacial <=> tiene la maravillosa propiedad de que devuelve -1, 0 o +1, exactamente qué clase necesita.

No he mirado, pero es muy probable que Ruby esté usando el algoritmo de quicksort rápido.

Alguna persona inteligente notó que seguimos haciendo lo mismo en el lado izquierdo del operador de la nave espacial como lo hacemos en el lado derecho, y surgió sort_by , usado de esta forma:

people.sort_by do |person|
person.name
end

En lugar de que el algoritmo de clasificación asigne dos objetos al bloque y permita que el bloque los compare, el algoritmo otorga un solo objeto al bloque. El bloque luego devuelve cualquier atributo o valor que se debe usar para hacer la clasificación. Ruby recuerda el valor que el bloque devolvió para cada elemento, y al comparar esos valores, sabe en qué orden poner las cosas. Es genial que ya no tengas que repetirte.

Su código aleatorio funciona simplemente "inventando cosas" cuando el algoritmo de clasificación cede al bloque. En lugar de devolver algo sensible, el bloque produce un valor aleatorio. Esto hace que el algoritmo de clasificación ordene las cosas, bueno, al azar.