c# - sistemas - ¿Utiliza Random y OrderBy un buen algoritmo de mezcla?

requisitos de la gestion de memoria

Question

He leído un artículo sobre varios algoritmos aleatorios en Coding Horror . He visto que en alguna parte las personas han 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?

Answer 1

A partir de esta cita de Skeet:

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

¡Voy a explicar un poco el motivo de la esperanza única!

Ahora, desde el Enumerable.OrderBy :

Este método realiza un tipo estable; es decir, si las claves de dos elementos son iguales, se conserva 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 el que están en la matriz. Ahora, ¿cuál es la posibilidad de que esto suceda? Es difícil calcular exactamente, pero está el problema del cumpleaños que es exactamente este problema.

Ahora, ¿es real? ¿Es verdad?

Como siempre, cuando tenga dudas, escriba algunas líneas de programa: http://pastebin.com/5CDnUxPG

Este pequeño bloque de código mezcla una matriz 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 pseudo-código ... Producen un equivalente resultados, pero uno se hace del primer al último elemento, mientras que el otro se hace del último al primer elemento), el ingenuo algoritmo incorrecto de http://blog.codinghorror.com/the-danger-of-naivete/ y el uso del .OrderBy(x => r.Next()) y .OrderBy(x => r.Next(someValue)) .

Ahora, Random.Next es

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

por lo que es equivalente a

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

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

El programa luego prueba algunos valores, en el rango 1 ... 4096. Al observar el resultado, está bastante claro que para valores bajos (<128), el algoritmo es muy parcial (4-8%). Con 3 valores necesitas al menos r.Next(1024) . Si r.Next(1024) la matriz (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 extra de valor máximo (porque la paradoja del cumpleaños está conectada al sqrt (valores numéricos)), por lo que que si el valor máximo es 2 ^ 31, diré que deberías poder ordenar arreglos de hasta 2 ^ 12/2 ^ 13 bits (4096-8192 elementos)

Answer 2

Buscando un algoritmo? Puedes usar mi clase ShuffleList :

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);
        }
    }
}

Entonces, úsalo así:

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

¿Como funciona?

Tomemos una lista ordenada inicial de los 5 primeros enteros: { 0, 1, 2, 3, 4 } .

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

En el siguiente ejemplo paso a paso, los elementos que se pueden mover son 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

Answer 3

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

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

¿No podría ser que el IEnumerableSorter llame a una función de comparación para cada paso de algoritmo de, 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, es posible que realmente estropee el algoritmo de clasificación y lo haga mucho peor que las expectativas en las que se basa el algoritmo. Por supuesto, eventualmente se estabilizará y devolverá algo.

Puede que lo revise más tarde al poner 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.

Answer 4

Encontré que la respuesta de Jon Skeet es totalmente satisfactoria, pero el robo-escáner de mi cliente informará cualquier instancia de Random como una falla de seguridad. Así que lo System.Security.Cryptography.RNGCryptoServiceProvider para System.Security.Cryptography.RNGCryptoServiceProvider . Como beneficio adicional, se soluciona el problema de seguridad de subprocesos mencionado. Por otro lado, RNGCryptoServiceProvider se ha medido como 300 veces más lento que el uso de 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];
    }
}

Answer 5

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

Answer 6

Esto ha aparecido muchas veces antes. Busque Fisher-Yates en .

Aquí hay un ejemplo 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;
                }
        }
}

Answer 7

Esto se basa en la answer Jon Skeet.

En esa respuesta, la matriz se mezcla y luego se devuelve usando yield . El resultado neto es que la matriz se mantiene en la memoria durante el tiempo 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 tres primeros elementos, y los otros solo se necesitarán más tarde, si es que se necesitan. Mi sugerencia es yield los números tan pronto como se intercambien. Esto reducirá el costo de inicio, mientras mantiene el costo de la iteración en O (1) (básicamente 5 operaciones por iteración). El costo total seguiría siendo el mismo, pero la reorganización en sí misma sería más rápida. En los casos en que esto se denomina collection.Shuffle().ToArray() teóricamente no hará ninguna diferencia, pero en los casos de uso mencionados anteriormente acelerará la puesta en marcha. Además, esto haría que el algoritmo fuera útil para casos en los que solo necesitas algunos elementos únicos. Por ejemplo, si necesita sacar tres cartas de una baraja de 52, puede llamar a deck.Shuffle().Take(3) y solo se realizarán tres cambios (aunque la matriz completa debería copiarse primero).

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

Answer 8

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

Dice-O-Matic

La razón por la que estoy publicando esto aquí, es que él hace algunos puntos interesantes sobre cómo sus usuarios reaccionaron a la idea de usar algoritmos para mezclar, 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 afecte al dinero;).

Answer 9

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

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

La implementación de un método simple de extensión Shuffle consistiría básicamente en llamar a ToList o ToArray en la entrada y luego usar una implementación existente de Fisher-Yates. (Pase el Random como parámetro para hacer la vida en general más agradable.) Hay muchas implementaciones ... Probablemente haya recibido una en alguna parte.

Lo bueno de este método de extensión es que entonces 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á todo el trabajo que necesite.

Tenga en cuenta que en ambos casos, debe tener cuidado con la instancia de Random que utiliza como:

• La creación de dos instancias de Random más o menos 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 Random que entra en más detalles sobre estos problemas y proporciona soluciones.

Answer 10

Parece un buen algoritmo de mezcla, si no estás muy preocupado por el rendimiento. El único problema que señalaría es que su comportamiento no es controlable, por lo que puede tener dificultades para probarlo.

Una posible opción es hacer pasar 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.

Answer 11

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 un elemento aleatorio a cada elemento de la serie y ordenando la secuencia por estos enteros.

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

Answer 12

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

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 ()) utiliza 38.6528 ms

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

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

EDITAR: CODIGO 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
Estado del resultado: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

Conclusión:
Supongamos que LINQ OrderBy (r.Next ()) y OrderBy (Guid.NewGuid ()) no son peores que el método de mezcla definido por el usuario en First Solution.

Respuesta: Son contradicción.