Mezclar usando IComparer
https://stackoverflow.com/questions/557911
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
En primer lugar, conozco la combinación Fisher-Yates.Pero digamos, por el bien de los argumentos, que quiero permitir que el usuario elija una opción de clasificación de una lista desplegable.Esta lista incluiría una opción "Aleatoria".Según el resultado de su selección, solo quiero sustituir mi tipo en una instancia de IComparer.¿Cómo sería el IComparer?
Google muestra una gran cantidad 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 está sesgada e incluso generará 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ías implementar un método aleatorio? IComparer<T> ¿Eso resolvió esos problemas?Se permite exigir que cada llamada .Sort() usar una instancia de IComparer separada, ya que no veo otra forma de hacer esto:elementos debe compararse utilizando algún otro valor verdaderamente aleatorio, pero ese valor debe también ser coherente para un elemento dentro de una operación de clasificación determinada.
tengo un comienzo aquí, pero fue publicado apresuradamente, es extremadamente lento y ni siquiera devuelve todos los tipos posibles (las pruebas muestran que al menos elimina el sesgo, si no se cuentan las opciones que faltan).No espero un rendimiento O(n) como el de Fisher-Yates, pero sí quiero algo razonable (n log n para un n pequeño), y espero que muestre todos los tipos posibles.Desafortunadamente, ese enlace es la respuesta actualmente aceptada para su pregunta, por lo que espero poder reemplazarlo con algo un poco mejor.
Al menos, quiero que esto sea un imán para todas esas consultas de Google que buscan una solución IComparable, que terminarán aquí en lugar de en otro lugar diciéndoles que usen la versión incorrecta.
Solución 2
Una sugerencia que tengo en otro lugar era crear una interfaz IArranger separado que describe una sola operación a Organizar una colección. Esto puede funcionar en IComparer / IComparable no puede porque opera sobre una colección entera, en lugar de los elementos individuales. Podría ser algo como esto:
public interface IArranger<T>
{
IEnumerable<T> Arrange(IEnumerable<T> items);
}
Entonces podría implementar un Shuffle desde la interfaz IArranger utilizando un algoritmo adecuado Fisher-Yates, y también tienen implementaciones que envuelva cada IEnumerable.Sort()/IComparable/IComparer variedades adicionales que me importa. Eso podría ser algo como esto:
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;
}
}
En un paso final, I añadir soporte para esto a cualquier IEnumerable a través de un método de extensión. A continuación, sigue recibiendo el sencillo algoritmo de intercambio de tiempo de ejecución, que tiene una mejor implementación del algoritmo aleatorio, y el código de usar que se siente natural:
public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
return arranger.Arrange(items);
}
Otros consejos
Me sorprendió un poco en este hilo el número de respuestas incorrectas fueron publicadas. Sólo por el bien de otros que vienen con una solución similar a la publicada por el PO, el siguiente código ve correcta:
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 se producirá una excepción de vez en cuando, pero no siempre. Eso es lo que hace que sea divertido para depurar :) Si ejecuta suficientes veces, o ejecutar el procedimiento de clasificación en un circuito de 50 o más veces, obtendrá un error que indica:
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, la ordenación rápida en comparación algún número x a sí mismo y consiguió un resultado distinto de cero. La solución obvia para el 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 las que se compara .NET 3 números uno contra el otro que devuelven resultados inconsistentes, tales como A> B, B> C, y C> A (ups!). No importa si se utiliza un GUID, GetHashCode, o cualquier otra entrada generado al azar, una solución como la que se muestra arriba sigue siendo incorrecto.
Con eso se dice, Fisher-Yates es la manera estándar de barajar las matrices, por lo que no hay ninguna razón real para utilizar IComparer en el primer lugar. Fisher-Yates es O (n), mientras que cualquier implementación usando IComparer utiliza un quicksort Behinds de las escenas que tiene un tiempo-complejidad de O (n log n). Simplemente no hay una buena razón para no usar el bien conocido, eficiente algoritmo estándar para resolver este tipo de problema.
Sin embargo, si realmente insiste en usar un IComparer y una rand, a continuación, aplicar los datos aleatorios antes de a clasificar. Esto requiere una proyección de los datos sobre otro objeto para que no pierda sus datos al azar:
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 conseguir LINQy con su propio mal:
Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
orderby r.NextDouble()
select x;
IComparer requiriendo a cero vuelta en algún punto (por la igualdad de las instancias de T), hace que sea matemáticamente imposible crear un IComparer genérico que imitar un Fisher-Yates aleatoria estadísticamente. Siempre habrá un sesgo. Para una reproducción aleatoria verdadera, que no se desea para obligarlo a devolver ningún valor en particular.
¿Qué tal la clasificación basada en un campo oculto, que está pre-asignado un valor aleatorio?
Para dar seguimiento a la idea de James Curran: dejar que el IComparer mantener la "ordenados" valores como una lista; si se produce un nuevo valor, insertarlo en la lista en una posición aleatoria; comparar por el índice de la lista. Optimizar mediante el mantenimiento de la lista como un árbol equilibrado o algo así. Cada instancia de un IComparer tales mantendrá un orden coherente y al azar por lo que tiene la opción de dejar que su clasificación aleatoria consistentemente el mismo orden aleatorio o una diferente cada vez. modificación menor incluso permitirá que los elementos iguales a ser "ordenados" en diferentes posiciones de pedido, si usted prefiere leer "al azar" de esa manera.
Una tarea interesante. Lo más probable es un mal uso / abuso de IComparer.
Usted está tratando de hacer una especie ponderada aleatoria mediante el uso de un mecanismo que no fue construido para tal 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.
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 estará sesgado deterministamente.
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 fueron ingresados).Array.Sort no es estable (usa QuickSort internamente), pero todavía existe un sesgo que ocurre cuando dos elementos tienen el mismo valor que depende de dónde se encuentran en la entrada (y específicamente de dónde están en relación con el QuickSort). pivote).
A medida que aumenta el espacio de claves 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á clasificando, la paradoja del cumpleaños dicta que la probabilidad de al menos Al menos un par entre ellos que choca sube muy rápidamente.
Para una clave entera, hay 2^32 valores únicos para la clave e incluso suponiendo que exista una distribución perfectamente uniforme de valores aleatorios, con 75.000 filas, existe un 50% de probabilidad de que haya una colisión. Wikipedia.
El enfoque de hash criptográfico que propuso tiene potencialmente un espacio de claves lo suficientemente grande (160) bits para hacer que la posibilidad de una colisión sea insignificante, pero su algoritmo descompone toda esa aleatoriedad en un solo int antes de realizar la comparación, lo que niega el beneficio de ese espacio de claves más grande.
Su mejor enfoque es asociar un valor de "orden de clasificación" distinto con cada uno de sus elementos de datos, mezclar estos valores utilizando un algoritmo probado y luego ordenar los resultados según ese valor.
Si está utilizando Array.Sort, hay una sobrecarga que requiere una serie de "claves" y una serie de "valores".La matriz de claves se ordena 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);
