La mejor manera de aleatorizar una matriz con .NET
¿Cuál es la mejor manera de aleatorizar una serie de cadenas con .NET? Mi matriz contiene alrededor de 500 cadenas y me gustaría crear una nueva Arraycon las mismas cadenas pero en orden aleatorio.
Incluya un ejemplo de C# en su respuesta.
La siguiente implementación utiliza el algoritmo de Fisher-Yates , también conocido como Knuth Shuffle. Se ejecuta en tiempo O(n) y se mezcla en el lugar, por lo que tiene un mejor rendimiento que la técnica de "ordenar aleatoriamente", aunque tiene más líneas de código. Consulte aquí para conocer algunas mediciones comparativas de rendimiento. He utilizado System.Random, que está bien para fines no criptográficos.*
static class RandomExtensions
{
public static void Shuffle<T> (this Random rng, T[] array)
{
int n = array.Length;
while (n > 1)
{
int k = rng.Next(n--);
T temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
}
Uso:
var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle
* Para matrices más largas, para que el número (extremadamente grande) de permutaciones sea igualmente probable, sería necesario ejecutar un generador de números pseudoaleatorios (PRNG) a través de muchas iteraciones para que cada intercambio produzca suficiente entropía. ¡Para una matriz de 500 elementos sólo una fracción muy pequeña de los 500 posibles! Las permutaciones serán posibles de obtener usando un PRNG. Sin embargo, el algoritmo de Fisher-Yates es imparcial y, por lo tanto, la reproducción aleatoria será tan buena como el RNG que utilice.
Primero, debes usar la respuesta más votada a esta pregunta hasta ahora, que es https://stackoverflow.com/a/110570/1757994 .
Puedes mezclar usando LINQ.
var myShuffledArray = myArray.Shuffle().
Agregue el siguiente código como un archivo llamado EnumerableExtensions.csa su proyecto:
public static class EnumerableExtensions
{
public static IList<T> Shuffle<T>(this IEnumerable<T> sequence)
{
return sequence.Shuffle(new Random());
}
public static IList<T> Shuffle<T>(this IEnumerable<T> sequence, Random randomNumberGenerator)
{
if (sequence == null)
{
throw new ArgumentNullException("sequence");
}
if (randomNumberGenerator == null)
{
throw new ArgumentNullException("randomNumberGenerator");
}
T swapTemp;
List<T> values = sequence.ToList();
int currentlySelecting = values.Count;
while (currentlySelecting > 1)
{
int selectedElement = randomNumberGenerator.Next(currentlySelecting);
--currentlySelecting;
if (currentlySelecting != selectedElement)
{
swapTemp = values[currentlySelecting];
values[currentlySelecting] = values[selectedElement];
values[selectedElement] = swapTemp;
}
}
return values;
}
}
Adaptado de https://github.com/microsoft/driver-utilities/blob/master/src/Sarif.Driver/EnumerableExtensions.cs
Es una mala idea utilizar algoritmos aleatorios creados de manera informal, ya que son difíciles de analizar en busca de fallas.
Si está utilizando C# 7.0 o superior, este otro enfoque es lento para muchos elementos pero funciona correctamente en todos los entornos en los que se utiliza C#:
var rnd = new Random();
var myRandomArray = myArray
.Select(x => (x, rnd.Next()))
.OrderBy(tuple => tuple.Item2)
.Select(tuple => tuple.Item1)
.ToArray();
Esto es casi tan detallado como la reproducción aleatoria de Fisher-Yates, que es mucho más rápida para una gran cantidad de elementos. Esto crea números aleatorios para cada elemento y luego los ordena por número aleatorio.
Esta respuesta solía decir algo como .OrderBy(x => random()).
Los desarrolladores experimentados sabrán correctamente que eso .OrderBy(x => random())por sí solo está mal. Entonces, si confirmas un código que lo contiene, quedarás mal.
¿Por qué está mal? OrderBy espera que keySelector, la función que se le pasa, sea pura. Eso significa que keySelector debería devolver la misma respuesta cada vez que se llame y no causar efectos secundarios.
Las implementaciones de C# como las de Unity no almacenan en caché el resultado del selector pasado a OrderBy. Los juegos tienden a mezclar las cosas. Es difícil generalizar en todas las implementaciones de CLR, por lo que es mejor usar lo correcto. Para no quedar mal con el código que usted crea, debe utilizar Fisher-Yates en su lugar.
Para Visual Basic y versiones de C# anteriores a la 7.0, utilice Fisher-Yates. Una implementación correcta usando solo LINQ es más detallada que implementar Fisher-Yates, por lo que habrá escrito más código para hacer una implementación peor.
Estás buscando un algoritmo de mezcla, ¿verdad?
Bien, hay dos formas de hacer esto: la inteligente, pero la gente siempre parece malinterpretarlo y hacerlo mal, por lo que tal vez no sea tan inteligente después de todo. manera, y la manera-tonta-como-una-piedra-pero-a quién-le-importa-porque-funciona.
manera tonta
- Cree un duplicado de su primera matriz, pero etiquete cada cadena con un número aleatorio.
- Ordena la matriz duplicada con respecto al número aleatorio.
Este algoritmo funciona bien, pero asegúrese de que es poco probable que su generador de números aleatorios etiquete dos cadenas con el mismo número. Debido a la llamada paradoja del cumpleaños , esto sucede con más frecuencia de lo que cabría esperar. Su complejidad temporal es O ( n log n ).
manera inteligente
Describiré esto como un algoritmo recursivo:
Para mezclar una matriz de tamaño n (índices en el rango [0.. n -1]):
si norte = 0si norte > 0
- hacer nada
- (paso recursivo) barajar los primeros n -1 elementos de la matriz
- elija un índice aleatorio, x , en el rango [0.. n -1]
- intercambiar el elemento en el índice n -1 con el elemento en el índice x
El equivalente iterativo es recorrer un iterador a través de la matriz, intercambiando con elementos aleatorios a medida que avanza, pero tenga en cuenta que no puede intercambiar con un elemento después del que apunta el iterador. Este es un error muy común y conduce a una mezcla aleatoria sesgada.
La complejidad del tiempo es O ( n ).
Este algoritmo es simple pero no eficiente, O(N 2 ). Todos los algoritmos de "ordenar por" suelen ser O (N log N). Probablemente no haga una diferencia debajo de cientos de miles de elementos, pero sí lo haría en listas grandes.
var stringlist = ... // add your values to stringlist
var r = new Random();
var res = new List<string>(stringlist.Count);
while (stringlist.Count >0)
{
var i = r.Next(stringlist.Count);
res.Add(stringlist[i]);
stringlist.RemoveAt(i);
}
La razón por la que es O(N 2 ) es sutil: List.RemoveAt() es una operación O(N) a menos que la elimine en orden desde el final.
