¿Usar Random y OrderBy es un buen algoritmo aleatorio?

164

He leído un artículo sobre varios algoritmos aleatorios en Coding Horror . He visto que en algún lugar la gente ha hecho esto para barajar una lista:

var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());

¿Es este un buen algoritmo aleatorio? ¿Como funciona exactamente? ¿Es una forma aceptable de hacer esto?

Svish
fuente

Respuestas:

205

No es una forma de barajar lo que me gusta, sobre todo porque es O (n log n) sin ninguna buena razón cuando es fácil implementar una baraja O (n). El código en la pregunta "funciona" básicamente dando un número aleatorio (¡con suerte único!) A cada elemento, luego ordenando los elementos de acuerdo con ese número.

Prefiero la variante de Durstenfield del shuffle de Fisher-Yates que intercambia elementos.

La implementación de un Shufflemétodo de extensión simple consistiría básicamente en llamar ToListo ToArrayen la entrada y luego usar una implementación existente de Fisher-Yates. (Pase el Randomparámetro como para hacer la vida en general más agradable). Hay muchas implementaciones alrededor ... Probablemente tengo una en alguna respuesta.

Lo bueno de este método de extensión es que sería muy claro para el lector lo que realmente está tratando de hacer.

EDITAR: Aquí hay una implementación simple (¡sin verificación de errores!):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

EDITAR: los comentarios sobre el rendimiento a continuación me recordaron que en realidad podemos devolver los elementos a medida que los barajamos:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

Esto ahora solo hará tanto trabajo como sea necesario.

Tenga en cuenta que en ambos casos, debe tener cuidado con la instancia Randomque usa como:

  • La creación de dos instancias Randomaproximadamente al mismo tiempo producirá la misma secuencia de números aleatorios (cuando se usa de la misma manera)
  • Random No es seguro para subprocesos.

Tengo un artículo sobre elRandom que se detalla más sobre estos temas y proporciona soluciones.

Jon Skeet
fuente
55
Bueno, implementaciones para cosas pequeñas, pero importantes, diría que siempre es bueno encontrarlas aquí en StackOverflow. Entonces sí, por favor, si quieres =)
Svish
9
Jon: tu explicación de Fisher-Yates es equivalente a la implementación dada en la pregunta (la versión ingenua). Durstenfeld / Knuth logran O (n) no por asignación, sino por selección de un conjunto decreciente e intercambio. De esta manera, el número aleatorio seleccionado puede repetirse y el algoritmo solo toma O (n).
tvanfosson
8
Probablemente te estés hartando de tener noticias mías sobre esto, pero me encontré con un pequeño problema en las pruebas de mi unidad del que tal vez quieras estar al tanto. Hay una peculiaridad con ElementAt que hace que invoque la extensión cada vez, dando resultados poco confiables. En mis pruebas estoy materializando el resultado antes de verificar para evitar esto.
tvanfosson
3
@tvanfosson: No está enfermo en absoluto :) Pero sí, las personas que llaman deben saber que se evalúa perezosamente.
Jon Skeet
44
Un poco tarde, pero tenga en cuenta source.ToArray();que debe tener using System.Linq;el mismo archivo. Si no lo haces, obtienes este error:'System.Collections.Generic.IEnumerable<T>' does not contain a definition for 'ToArray' and no extension method 'ToArray' accepting a first argument of type 'System.Collections.Generic.IEnumerable<T>' could be found (are you missing a using directive or an assembly reference?)
Powerlord
70

Esto se basa en la respuesta de Jon Skeet .

En esa respuesta, la matriz se baraja, luego se devuelve usando yield. El resultado neto es que la matriz se mantiene en memoria durante la duración de foreach, así como los objetos necesarios para la iteración, y sin embargo, el costo es todo al principio: el rendimiento es básicamente un ciclo vacío.

Este algoritmo se usa mucho en los juegos, donde se seleccionan los primeros tres elementos, y los demás solo se necesitarán más adelante si es que se necesitan. Mi sugerencia es a yieldlos números tan pronto como se intercambian. Esto reducirá el costo de inicio, mientras mantiene el costo de iteración en O (1) (básicamente 5 operaciones por iteración). El costo total se mantendría igual, pero la mezcla sería más rápida. En los casos en que esto se llama, ya collection.Shuffle().ToArray()que en teoría no hará ninguna diferencia, pero en los casos de uso mencionados anteriormente, acelerará el arranque. Además, esto haría que el algoritmo sea útil para casos en los que solo necesita unos pocos elementos únicos. Por ejemplo, si necesita extraer tres cartas de un mazo de 52, puede llamar deck.Shuffle().Take(3)y solo se realizarán tres intercambios (aunque primero se tendría que copiar toda la matriz).

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
        // we don't actually perform the swap, we can forget about the
        // swapped element because we already returned it.
    }

    // there is one item remaining that was not returned - we return it now
    yield return elements[0]; 
}
configurador
fuente
¡Ay! Es probable que esto no devuelva todos los elementos en la fuente. No puede confiar en que un número aleatorio sea único para N iteraciones.
P Daddy el
2
¡Inteligente! (Y odio estas cosas de 15 personajes ...)
Svish el
@ P Papi: ¿Eh? ¿Cuidado para elaborar?
Svish
1
O puede reemplazar el> 0 con> = 0 y no tener que hacerlo (aunque, un golpe adicional de RNG más una asignación redundante)
FryGuy
44
El costo de inicio es O (N) como el costo de la fuente. ToArray ();
Dave Hillier
8

A partir de esta cita de Skeet:

No es una forma de barajar que me gusta, sobre todo porque es O (n log n) sin ninguna razón cuando es fácil implementar una baraja O (n). El código en la pregunta "funciona" básicamente dando un número aleatorio (¡con suerte único! ) A cada elemento, luego ordenando los elementos de acuerdo con ese número.

¡Seguiré explicando un poco la razón de lo que es de esperar único!

Ahora, desde el Enumerable.OrderBy :

Este método realiza una ordenación estable; es decir, si las claves de dos elementos son iguales, se preserva el orden de los elementos

¡Esto es muy importante! ¿Qué sucede si dos elementos "reciben" el mismo número aleatorio? Sucede que permanecen en el mismo orden en que están en la matriz. Ahora, ¿cuál es la posibilidad de que esto suceda? Es difícil calcular exactamente, pero existe el problema de cumpleaños que es exactamente este problema.

Ahora, ¿es real? ¿Es verdad?

Como siempre, en caso de duda, escriba algunas líneas de programa: http://pastebin.com/5CDnUxPG

Este pequeño bloque de código baraja una serie de 3 elementos una cierta cantidad de veces usando el algoritmo de Fisher-Yates hecho hacia atrás, el algoritmo de Fisher-Yates hecho hacia adelante (en la página wiki hay dos algoritmos de pseudocódigo ... Producen equivalentes resultados, pero uno se realiza del primer al último elemento, mientras que el otro se realiza del último al primer elemento), el ingenuo algoritmo incorrecto de http://blog.codinghorror.com/the-danger-of-naivete/ y el uso de .OrderBy(x => r.Next())y el .OrderBy(x => r.Next(someValue)).

Ahora, Random.Next es

Un entero con signo de 32 bits que es mayor o igual a 0 y menor que MaxValue.

entonces es equivalente a

OrderBy(x => r.Next(int.MaxValue))

Para probar si este problema existe, podríamos agrandar la matriz (algo muy lento) o simplemente reducir el valor máximo del generador de números aleatorios ( int.MaxValueno es un número "especial" ... Es simplemente un número muy grande). Al final, si el algoritmo no está sesgado por la estabilidad del OrderBy, entonces cualquier rango de valores debería dar el mismo resultado.

Luego, el programa prueba algunos valores, en el rango de 1 ... 4096. Mirando el resultado, está bastante claro que para valores bajos (<128), el algoritmo es muy sesgado (4-8%). Con 3 valores necesitas al menos r.Next(1024). Si hace que la matriz sea más grande (4 o 5), incluso r.Next(1024)no es suficiente. No soy un experto en barajar y en matemáticas, pero creo que por cada bit adicional de longitud de la matriz, necesitas 2 bits adicionales de valor máximo (porque la paradoja del cumpleaños está conectada al sqrt (valores numéricos)), entonces que si el valor máximo es 2 ^ 31, diré que debería poder ordenar matrices de hasta 2 ^ 12/2 ^ 13 bits (4096-8192 elementos)

xanatos
fuente
Bien dicho, y muestra perfectamente un problema con la pregunta original. Esto debería fusionarse con la respuesta de Jon.
TheSoftwareJedi
6

Probablemente está bien para la mayoría de los propósitos, y casi siempre genera una distribución verdaderamente aleatoria (excepto cuando Random.Next () produce dos enteros aleatorios idénticos).

Funciona asignando a cada elemento de la serie un número entero aleatorio, luego ordenando la secuencia por estos números enteros.

Es totalmente aceptable para el 99,9% de las aplicaciones (a menos que sea absolutamente necesario manejar el caso límite anterior). Además, la objeción de skeet a su tiempo de ejecución es válida, por lo que si está barajando una lista larga, es posible que no desee usarla.

ripper234
fuente
4

Esto ha surgido muchas veces antes. Busque Fisher-Yates en StackOverflow.

Aquí hay una muestra de código C # que escribí para este algoritmo. Puede parametrizarlo en otro tipo, si lo prefiere.

static public class FisherYates
{
        //      Based on Java code from wikipedia:
        //      http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
        static public void Shuffle(int[] deck)
        {
                Random r = new Random();
                for (int n = deck.Length - 1; n > 0; --n)
                {
                        int k = r.Next(n+1);
                        int temp = deck[n];
                        deck[n] = deck[k];
                        deck[k] = temp;
                }
        }
}
hughdbrown
fuente
2
No debe usarlo Randomcomo una variable estática como esta: Randomno es seguro para subprocesos. Ver csharpindepth.com/Articles/Chapter12/Random.aspx
Jon Skeet
@ Jon Skeet: claro, ese es un argumento legítimo. OTOH, el OP estaba preguntando acerca de un algoritmo que era completamente incorrecto, mientras que esto es correcto (que no sea el caso de uso de barajado de tarjetas multiproceso).
hughdbrown
1
Eso solo significa que esto es "menos incorrecto" que el enfoque del OP. No significa que sea un código que deba usarse sin comprender que no puede usarse de manera segura en un contexto multiproceso ... que es algo que no mencionó. Existe una expectativa razonable de que los miembros estáticos se pueden usar de forma segura desde varios subprocesos.
Jon Skeet
@ Jon Skeet: Claro, puedo cambiarlo. Hecho. Tiendo a pensar que volviendo a una pregunta respondida hace tres años y medio y diciendo: "Es incorrecto porque no maneja el caso de uso multiproceso" cuando el OP nunca preguntó nada más que el algoritmo es excesivo. Revisa mis respuestas a lo largo de los años. A menudo he dado respuestas de OP que fueron más allá de los requisitos establecidos. He sido criticado por eso. Sin embargo, no esperaría que los OP obtuvieran respuestas que se ajustaran a todos los usos posibles.
hughdbrown
Solo visité esta respuesta porque alguien más me señaló en el chat. Si bien el OP no mencionó específicamente el subproceso, creo que definitivamente vale la pena mencionarlo cuando un método estático no es seguro para subprocesos, ya que es inusual y hace que el código no sea adecuado para muchas situaciones sin modificación. Su nuevo código es seguro para subprocesos, pero aún así no es ideal como si lo llamara desde varios subprocesos "aproximadamente" al mismo tiempo para barajar dos colecciones del mismo tamaño, las barajas serán equivalentes. Básicamente, Randomes un dolor de usar, como se señaló en mi artículo.
Jon Skeet
3

Parece un buen algoritmo de barajado, si no te preocupa demasiado el rendimiento. El único problema que señalaría es que su comportamiento no es controlable, por lo que puede ser difícil probarlo.

Una opción posible es que se pase una semilla como parámetro al generador de números aleatorios (o al generador aleatorio como parámetro), para que pueda tener más control y probarlo más fácilmente.

Samuel Carrijo
fuente
3

Encontré que la respuesta de Jon Skeet es completamente satisfactoria, pero el robo-escáner de mi cliente informará que cualquier instancia Randomes una falla de seguridad. Así que lo cambié por System.Security.Cryptography.RNGCryptoServiceProvider. Como beneficio adicional, corrige el problema de seguridad de subprocesos que se mencionó. Por otro lado, RNGCryptoServiceProviderse ha medido 300 veces más lento que el uso Random.

Uso:

using (var rng = new RNGCryptoServiceProvider())
{
    var data = new byte[4];
    yourCollection = yourCollection.Shuffle(rng, data);
}

Método:

/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data)
{
    var elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        rng.GetBytes(data);
        var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}
Frattaro
fuente
3

Buscando un algoritmo? Puedes usar mi ShuffleListclase:

class ShuffleList<T> : List<T>
{
    public void Shuffle()
    {
        Random random = new Random();
        for (int count = Count; count > 0; count--)
        {
            int i = random.Next(count);
            Add(this[i]);
            RemoveAt(i);
        }
    }
}

Luego, úsalo así:

ShuffleList<int> list = new ShuffleList<int>();
// Add elements to your list.
list.Shuffle();

¿Como funciona?

Tomemos un lista ordenada inicial de los 5 primeros números enteros: { 0, 1, 2, 3, 4 }.

El método comienza contando el nubmer de elementos y lo llama count. Luego, al countdisminuir en cada paso, toma un número aleatorio entre 0y county lo mueve al final de la lista.

En el siguiente ejemplo paso a paso, los elementos que se pueden mover están en cursiva , el elemento seleccionado está en negrita :

0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2

SteeveDroz
fuente
Eso no es O (n). RemoveAt solo es O (n).
paparazzo el
Hmm, parece que tienes razón, mi mal! Quitaré esa parte.
SteeveDroz
1

Este algoritmo se baraja generando un nuevo valor aleatorio para cada valor en una lista, luego ordenando la lista por esos valores aleatorios. Piense en ello como agregar una nueva columna a una tabla en memoria, luego llenarla con GUID y luego ordenar por esa columna. A mí me parece una forma eficiente (¡especialmente con el azúcar lambda!)

Dave Swersky
fuente
1

Ligeramente no relacionado, pero aquí hay un método interesante (que a pesar de que es realmente excesivo, REALMENTE se ha implementado) para una generación verdaderamente aleatoria de tiradas de dados.

Dice-O-Matic

La razón por la que estoy publicando esto aquí, es porque él hace algunos puntos interesantes sobre cómo reaccionaron sus usuarios a la idea de usar algoritmos para barajar, sobre dados reales. Por supuesto, en el mundo real, tal solución es solo para los extremos realmente extremos del espectro donde la aleatoriedad tiene un impacto tan grande y tal vez el impacto afecta el dinero;).

Irritar
fuente
1

Diría que muchas respuestas aquí, como "Este algoritmo se baraja al generar un nuevo valor aleatorio para cada valor en una lista, y luego ordenar la lista por esos valores aleatorios" podría estar muy mal.

Creo que esto NO asigna un valor aleatorio a cada elemento de la colección de origen. En cambio, puede haber un algoritmo de ordenación que se ejecute como Quicksort que llamaría a una función de comparación aproximadamente n log n veces. ¡Algún tipo de algoritmo realmente espera que esta función de comparación sea estable y siempre devuelva el mismo resultado!

¡No podría ser que IEnumerableSorter llame a una función de comparación para cada paso del algoritmo, por ejemplo, quicksort y cada vez llame a la función x => r.Next()para ambos parámetros sin almacenarlos en caché!

En ese caso, realmente podría estropear el algoritmo de clasificación y hacerlo mucho peor que las expectativas en las que se basa el algoritmo. Por supuesto, eventualmente se estabilizará y devolverá algo.

Podría verificarlo más tarde colocando la salida de depuración dentro de una nueva función "Siguiente" para ver qué sucede. En Reflector no pude averiguar de inmediato cómo funciona.

cristiano
fuente
1
No es el caso: anulación interna void ComputeKeys (elementos TElement [], int count); Tipo de declaración: System.Linq.EnumerableSorter <TElement, TKey> Ensamblaje: System.Core, Version = 3.5.0.0 Esta función crea primero una matriz con todas las teclas que consumen memoria, antes de ordenarlas rápidamente
Christian
Es bueno saberlo, aunque solo es un detalle de implementación, ¡que posiblemente podría cambiar en futuras versiones!
Blorgbeard sale el
-5

Tiempo de inicio para ejecutarse en código con borrar todos los hilos y almacenar en caché cada nueva prueba,

Primer código fallido. Se ejecuta en LINQPad. Si sigues para probar este código.

Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
list.Add(new String[] {"1","X"});
list.Add(new String[] {"2","A"});
list.Add(new String[] {"3","B"});
list.Add(new String[] {"4","C"});
list.Add(new String[] {"5","D"});
list.Add(new String[] {"6","E"});

//list.OrderBy (l => r.Next()).Dump();
list.OrderBy (l => Guid.NewGuid()).Dump();
st.Stop();
Console.WriteLine(st.Elapsed.TotalMilliseconds);

list.OrderBy (x => r.Next ()) usa 38.6528 ms

list.OrderBy (x => Guid.NewGuid ()) usa 36.7634 ms (se recomienda desde MSDN).

después de la segunda vez ambos usan al mismo tiempo.

EDITAR: CÓDIGO DE PRUEBA en Intel Core i7 [email protected], Ram 8 GB DDR3 @ 1600, HDD SATA 5200 rpm con [Datos: www.dropbox.com/s/pbtmh5s9lw285kp/data]

using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;

namespace Algorithm
{
    class Program
    {
        public static void Main(string[] args)
        {
            try {
                int i = 0;
                int limit = 10;
                var result = GetTestRandomSort(limit);
                foreach (var element in result) {
                    Console.WriteLine();
                    Console.WriteLine("time {0}: {1} ms", ++i, element);
                }
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            } finally {
                Console.Write("Press any key to continue . . . ");
                Console.ReadKey(true);
            }
        }

        public static IEnumerable<double> GetTestRandomSort(int limit)
        {
            for (int i = 0; i < 5; i++) {
                string path = null, temp = null;
                Stopwatch st = null;
                StreamReader sr = null;
                int? count = null;
                List<string> list = null;
                Random r = null;

                GC.Collect();
                GC.WaitForPendingFinalizers();
                Thread.Sleep(5000);

                st = Stopwatch.StartNew();
                #region Import Input Data
                path = Environment.CurrentDirectory + "\\data";
                list = new List<string>();
                sr = new StreamReader(path);
                count = 0;
                while (count < limit && (temp = sr.ReadLine()) != null) {
//                  Console.WriteLine(temp);
                    list.Add(temp);
                    count++;
                }
                sr.Close();
                #endregion

//              Console.WriteLine("--------------Random--------------");
//              #region Sort by Random with OrderBy(random.Next())
//              r = new Random();
//              list = list.OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with OrderBy(Guid)
//              list = list.OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with Parallel and OrderBy(random.Next())
//              r = new Random();
//              list = list.AsParallel().OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with Parallel OrderBy(Guid)
//              list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with User-Defined Shuffle Method
//              r = new Random();
//              list = list.Shuffle(r).ToList();
//              #endregion

//              #region Sort by Random with Parallel User-Defined Shuffle Method
//              r = new Random();
//              list = list.AsParallel().Shuffle(r).ToList();
//              #endregion

                // Result
//              
                st.Stop();
                yield return st.Elapsed.TotalMilliseconds;
                foreach (var element in list) {
                Console.WriteLine(element);
            }
            }

        }
    }
}

Descripción del resultado: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
Estadísticas del resultado: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

Conclusión:
Suponga que LINQ OrderBy (r.Next ()) y OrderBy (Guid.NewGuid ()) no son peores que el Método aleatorio definido por el usuario en la primera solución.

Respuesta: son contradicción.

GMzo
fuente
1
La segunda opción no es correcta y, por lo tanto, su rendimiento es irrelevante . Esto tampoco responde a la pregunta de si ordenar por un número aleatorio es aceptable, eficiente o cómo funciona. La primera solución también tiene problemas de corrección, pero no son tan importantes.
Servy
Lo sentimos, me gustaría saber cuál es el mejor tipo de parámetro de Quicksort de Linq OrderBy. Necesito probar el rendimiento. Sin embargo, creo que el tipo int solo tiene una velocidad mejor que la cadena de Guid, pero no lo es. Comprendí por qué MSDN recomienda. El rendimiento editado de la primera solución es igual que OrderBy con instancia aleatoria.
GMzo
¿Cuál es el punto de medir el rendimiento del código que no resuelve el problema? El rendimiento es solo una consideración entre dos soluciones que funcionan . Cuando usted tiene las soluciones de trabajo, entonces se puede empezar a compararlos.
Servicio
Debo tener tiempo para probar más datos y luego, si está terminado, prometo publicar nuevamente. Suponga: creo que Linq OrderBy no es peor que la primera solución. Opinión: es fácil de usar y entender.
GMzo
Es notablemente menos eficiente que los algoritmos de barajado simples y sencillos, pero una vez más, el rendimiento es irrelevante . No están barajando de manera confiable los datos, además de ser menos efectivos.
Servy