En LINQ, ¿orderby() ejecuta la función de comparación solo una vez o la ejecuta siempre que sea necesario?

Question

Encontré un método para barajar una matriz en Internet.

Random rand = new Random(); 
shuffledArray = myArray.OrderBy(x => rand.Next()).ToArray(); 

Sin embargo, estoy un poco preocupado por la exactitud de este método. Si OrderBy ejecuta x => rand.Next() muchas veces para el mismo artículo, los resultados pueden entrar en conflicto y resultar en cosas raras (posiblemente excepciones).

Lo probé y todo está bien, pero todavía quiero saber si esto es absolutamente seguro y siempre funciona como se esperaba, y no puedo encontrar la respuesta de Google.

¿Alguien podría darme algunas explicaciones?

Gracias de antemano.

Answer 1

Su enfoque debería funcionar, pero es lento.

Funciona porque OrderBy primero calcula las claves para cada elemento usando el selector de teclas, luego ordena las claves. Por lo tanto, el selector de llave solo se llama una vez por artículo.

En Reflector .NET, vea el método ComputeKeys en la clase EnumerableSorter.

this.keys = new TKey[count]; 
for (int i = 0; i < count; i++) 
{ 
    this.keys[i] = this.keySelector(elements[i]); 
} 
// etc... 

si esto es absolutamente seguro y siempre funciona como se esperaba

Se indocumentado así que en teoría podría cambiar en el futuro.

Para barajar aleatoriamente puede usar Fisher-Yates shuffle. Esto también es más eficiente, utilizando solo el tiempo O (n) y el cambio de lugar en lugar de O (n log (n)) tiempo y O (n) memoria adicional.

pregunta relacionada

• C#: Is using Random and OrderBy a good shuffle algorithm?

Answer 2

El uso de un shufflebag definitivamente funcionará.

En cuanto a su método orderby, creo que no es completamente aleatorio ya que se mantiene el orden de elementos iguales. Entonces, si tienes una matriz aleatoria [5 6 7 2 6], los elementos en los dos seises estarán siempre en el mismo orden.

Tendré que hacer una prueba de frecuencia para estar seguro.

Answer 3

Asumo que estás hablando de LINQ a objetos, en cuyo caso la clave utilizada para la comparación se genera solamente una vez por cada elemento. (Tenga en cuenta que esto es solo un detalle de la implementación actual y podría cambiar, aunque es muy poco probable porque tal cambio introduciría los errores que usted menciona.)

Para responder a su pregunta más general: su enfoque debería funcionar, pero hay mejores formas de hacerlo. El uso de OrderBy normalmente será el rendimiento O (n log n), mientras que Fisher-Yates-Durstenfeld shuffle será O (n).

(Hay un example Shuffle extension for IEnumerable<T> here, o un in-place equivalent for IList<T> here, si lo prefiere.)