c# - Mezcle usando IComparer

.net shuffle

Question

Antes que nada, sé sobre la mezcla de Fisher-Yates. Pero digamos por argumentos que quiero permitir que el usuario elija una opción de ordenación de una lista desplegable. Esta lista incluiría una opción "Aleatoria". Basado en el resultado de su selección, solo quiero sustituirlo en una instancia de IComparer para mi género. ¿Cómo se vería el IComparer?

Google presenta una plétora de resultados defectuosos que toman esta forma:

public class NaiveRandomizer<T> : IComparer<T>
{
    private static Random rand = new Random();

    public int Compare(T x, T y)
    {
        return (x.Equals(y))?0:rand.Next(-1, 2);
    }
}

Sin embargo, esa implementación es parcial e incluso arrojará una excepción en algunas circunstancias. El sesgo se puede demostrar con el siguiente código:

void Test()
{
    Console.WriteLine("NaiveRandomizer Test:");
    var data = new List<int>() {1,2,3};
    var sortCounts = new Dictionary<string, int>(6);
    var randomly = new NaiveRandomizer<int>();

    for (int i=0;i<10000;i++)
    {   //always start with same list, in _the same order_.
        var dataCopy = new List<int>(data); 
        dataCopy.Sort(randomly);

        var key = WriteList(dataCopy);
        if (sortCounts.ContainsKey(key))
            sortCounts[key]++;
        else
            sortCounts.Add(key, 1);
    }

    foreach (KeyValuePair<string, int> item in sortCounts)
        Console.WriteLine(item.Key + "/t" + item.Value);
}

string WriteList<T>(List<T> list)
{
   string delim = "";
   string result = "";
   foreach(T item in list)
   {
       result += delim + item.ToString();
       delim = ", ";
   }
   return result;
}

Entonces, ¿cómo podría implementar un IComparer<T> aleatorio que resolviera esos problemas? Se permite requerir que cada llamada a .Sort() use una instancia de IComparer separada, ya que no veo ninguna otra forma de hacer esto: los elementos deben compararse utilizando algún otro valor verdaderamente aleatorio, pero ese valor también debe ser consistente para un artículo dentro de una operación de clasificación dada.

Tengo un comienzo aquí , pero fue publicado a toda prisa, es extremadamente lento, y ni siquiera devuelve todos los géneros posibles (las pruebas muestran que al menos elimina el sesgo, si no cuenta las opciones faltantes). No espero un rendimiento O (n) como el de Fisher-Yates, pero sí quiero algo razonable (n log n para un pequeño-ish n), y espero que muestre todos los géneros posibles. Lamentablemente, ese enlace es la respuesta aceptada actualmente para su pregunta, por lo que espero poder reemplazarlo con algo un poco mejor.

Si nada más, quiero que esto sea un imán para todas las consultas de Google que buscan una solución IComparable, que terminarán aquí en lugar de en otra parte indicándoles que utilicen la versión incorrecta.

Answer 1

¿Qué tal una clasificación basada en un campo oculto, que está preasignado con un valor aleatorio?

Answer 2

IComparer que requiere un retorno cero en algún punto (para instancias iguales de T), hace que sea matemáticamente imposible crear un ensamblador genérico idéntico que simule una mezcla aleatoria de Fisher-Yates estadísticamente. Siempre habrá un sesgo. Para una barajadura real, nunca querrás forzarla a devolver ningún valor en particular.

Answer 3

Dar seguimiento a la idea de James Curran: dejar que el IComparer mantenga los valores "ordenados" como una lista; si aparece un nuevo valor, insértelo en la lista en una posición aleatoria; comparar por índice de lista. Optimice manteniendo la lista como un árbol equilibrado o algo así. Cada instancia de dicho IComparer mantendrá un orden de clasificación coherente y aleatorio, por lo que tiene la opción de permitir que su clasificación aleatoria sea consistentemente el mismo orden aleatorio o uno diferente cada vez. La modificación menor incluso permitirá que los elementos iguales se "clasifiquen" en diferentes posiciones de pedido, si prefiere leer "al azar" de esa manera.

Answer 4

No lo hagas

Todos los algoritmos propuestos hasta ahora introducen algún tipo de sesgo en la salida (algunos más grandes que otros).

@Princess y @Luke proponen almacenar un número aleatorio junto con los datos. Sin embargo, debido a que existe la posibilidad de que dos de estos números aleatorios tengan el mismo valor que otro, el orden de clasificación entre esos dos elementos será deterministamente sesgado.

El peor caso para esto sería si la rutina de clasificación es "estable" (es decir, los objetos que se consideran iguales siempre salen en el mismo orden en que se ingresaron). Array.Sort no es estable (usa QuickSort internamente) pero todavía hay un sesgo que ocurre cada vez que dos elementos tienen el mismo valor que depende de dónde están en la entrada (y específicamente donde están relacionados con el QuickSort pivote).

A medida que aumenta el espacio de teclado para este número aleatorio, la probabilidad de una colisión disminuye (con una buena fuente de aleatoriedad), pero tenga en cuenta que a medida que aumenta el número de valores que está ordenando, la paradoja del cumpleaños dicta que la probabilidad de al menos un par entre ellos colisiona sube muy rápido.

Para una clave entera, hay 2 ^ 32 valores únicos para la clave e, incluso suponiendo que haya una distribución perfectamente pareja de valores aleatorios, con 75,000 filas, hay un 50% de probabilidad de que haya una colisión. Wikipedia .

El enfoque hash criptográfico que usted propuso tiene potencialmente un espacio de teclado lo suficientemente grande (160) para que la posibilidad de una colisión sea despreciable, pero su algoritmo descompone toda esa aleatoriedad hasta una sola int antes de hacer la comparación que niega el beneficio de ese espacio de teclas más grande.

Su mejor enfoque es asociar un valor distinto de "ordenar orden" con cada uno de sus elementos de datos mezclar estos valores usando un algoritmo comprobado, y luego ordenar los resultados por ese valor.

Si está utilizando Array.Sort, hay una sobrecarga que toma una matriz de "claves" y una matriz de "valores". La matriz de claves se clasifica normalmente, pero cada vez que se mueve un valor en la matriz de claves, también se mueve la entrada correspondiente en la matriz de valores.

Algo como:

Something[] data;//populated somewhere
int[] keys = new int[data.Length];//or long if you might have lots of data
for(int i=0;i<keys.Length;++i) {
 keys[i] = i;
}

Shuffle(keys);

Array.Sort(keys, data);

Answer 5

Un esfuerzo interesante Muy probablemente un mal uso / abuso de IComparer.

Está intentando hacer una ordenación ponderada aleatoriamente mediante el uso de un mecanismo que no se creó para ese fin.

¿Por qué no implementar su propia rutina de clasificación y su propio comparador? Tengo la sensación de que incluso eso sería insuficiente.

Answer 6

Una sugerencia que obtuve en otro lugar fue crear una interfaz IArranger separada que describa una sola operación para Organizar una colección. Esto puede funcionar donde IComparer / IComparable no puede porque opera en una colección completa, en lugar de elementos individuales. Puede parecerse a esto:

public interface IArranger<T>
{
    IEnumerable<T> Arrange(IEnumerable<T> items);
}

Luego podría implementar un Shuffle desde la interfaz IArranger utilizando un algoritmo Fisher-Yates adecuado, y también tener implementaciones que envuelvan cada IEnumerable.Sort()/IComparable/IComparer adicional IEnumerable.Sort()/IComparable/IComparer que me importa. Eso podría verse más o menos así:

public class ComparerArranger<T> : IArranger<T>
{
    private IComparer<T> comparer;

    public ComparableArranger(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i, comparer);
    }
}

o

//uses the default Comparer for the type (Comparer<T>.Default)
public class TypeArranger<T> : IArranger<T> 
{
    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i);
    }
}

o

public class ShuffleArranger<T> : IArranger<T>
{
    //naive implementation for demonstration
    // if I ever develop this more completely I would try to
    // avoid needing to call .ToArray() in here
    // and use a better prng
    private Random r = new Random();

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
        var values = items.ToArray();

        //valid Fisher-Yates shuffle on the values array
        for (int i = values.Length; i > 1; i--)
        {
            int j = r.Next(i);
            T tmp = values[j];
            values[j] = values[i - 1];
            values[i - 1] = tmp;
        }
        foreach (var item in values) yield return item;
    }
}

Para un último paso, agrego soporte para esto a cualquier IEnumerable a través de un método de extensión. Entonces todavía obtienes el simple intercambio de algoritmos en tiempo de ejecución, tienes una mejor implementación del algoritmo de mezcla y el código para usarlo se siente natural:

public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
    return arranger.Arrange(items);
}

Answer 7

Me sorprendió un poco en este hilo cuántas respuestas incorrectas se publicaron. Solo por el bien de otros que presentan una solución similar a la publicada por el OP, el siguiente código parece correcto:

int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = i;
}

Random r = new Random();
Array.Sort<int>(nums, (x, y) => r.Next(-1, 2));

foreach(var num in nums)
{
    Console.Write("{0} ", num);
}

Sin embargo, el código emitirá una excepción ocasionalmente, pero no siempre. Eso es lo que hace que sea divertido depurar :) Si lo ejecuta suficientes veces, o ejecuta el procedimiento de ordenación en un bucle 50 o más veces, obtendrá un error que dice:

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: ''0'' x''s type: ''Int32'' The IComparer: ''''.

En otras palabras, el tipo rápido comparó un número x consigo mismo y obtuvo un resultado distinto de cero. La solución obvia al código sería escribir:

Array.Sort<int>(nums, (x, y) =>
    {
        if (x == y) return 0;
        else return r.NextDouble() < 0.5 ? 1 : -1;
    });

Pero incluso esto no funciona, porque hay ocasiones en que .NET compara 3 números uno contra el otro y devuelve resultados inconsistentes, como A> B, B> C y C> A (¡Uy!). No importa si utiliza un Guid, GetHashCode o cualquier otra entrada generada aleatoriamente, una solución como la que se muestra arriba sigue siendo incorrecta.

Habiendo dicho eso, Fisher-Yates es la forma estándar de barajar matrices, por lo que no hay una razón real para usar IComparer en primer lugar. Fisher-Yates es O (n) mientras que cualquier implementación que use IComparer usa una ruta rápida detrás de escena que tiene una complejidad temporal de O (n log n). Simplemente no hay una buena razón para no usar el conocido algoritmo estándar eficiente para resolver este tipo de problema.

Sin embargo, si realmente insistes en usar un IComparer y un rand, entonces aplica tus datos aleatorios antes de ordenarlos. Esto requiere una proyección de los datos en otro objeto para que no pierda sus datos aleatorios:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Pair<T, U>
    {
        public T Item1 { get; private set; }
        public U Item2 { get; private set; }
        public Pair(T item1, U item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Pair<int, double>[] nums = new Pair<int, double>[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair<int, double>(i, r.NextDouble());
            }

            Array.Sort<Pair<int, double>>(nums, (x, y) => x.Item2.CompareTo(y.Item2));

            foreach (var item in nums)
            {
                Console.Write("{0} ", item.Item1);
            }

            Console.ReadKey(true);
        }
    }
}

O consigue LINQy con tu mal yo:

Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
           orderby r.NextDouble()
           select x;