Duplicar posible:
Randomize a List<T> in C#lista de forma aleatoria <T>
Tengo una lista que contiene muchos miles de FilePath de a ubicaciones de archivos de audio, y se preguntaba cuál sería la forma más eficiente para "mezclar" una lista?
Cualquier ayuda es muy apreciada :)
Gracias
Fisher-Yates Shuffle o como también se le conoce como, Knuth aleatoria.
... que es O (n), por lo que no se puede obtener nada mejor que eso. – Guffa
... Te acabo de votar porque me gustó tu respuesta :) ¿Por qué se votó negativamente? –
Por cierto, para barajar más rápido, le sugiero que mezcle una lista/matriz de enteros (utilizando el método que elija) y use esa lista/matriz mezclada como un índice en la lista de nombres de archivos. El intercambio de nombres de archivo podría ser un cuello de botella. –
myList.OrderBy(Guid.NewGuid())
Algunos algoritmos de generación GUID generan valores monótonos, por lo que es posible que no proporcionen resultados aleatorios. Sin embargo, algo similar usando otra fuente de aleatoriedad (Probablemente aleatorio) funcionaría. – heneryville
Aquí es una sencilla aplicación (pero efectivo) de la reproducción aleatoria de Fischer-Yates/Knuth:
Random rnd = new Random();
for (int i = files.Length; i > 1; i--) {
int pos = rnd.Next(i);
var x = files[i - 1];
files[i - 1] = files[pos];
files[pos] = x;
}
O una ligera variación:
Random rnd = new Random();
for (int i = 1; i < files.Length; i++) {
int pos = rnd.Next(i + 1);
var x = files[i];
files[i] = files[pos];
files[pos] = x;
}
Como se trata de una Operación O (n), es la forma más eficiente de barajar una lista. Como todos los elementos de la lista tienen que poder moverse, no es posible barajar una lista de manera más eficiente que O (n).
Hice una pequeña prueba de rendimiento mezclando un millón de artículos mil veces cada uno utilizando este método y la respuesta actualmente aceptada (LINQ OrderBy), y esto es aproximadamente 15 veces (!) Más rápido.
Estás confundiendo el límite asintótico con la eficiencia. La eficiencia se define como los recursos consumidos por unidad de trabajo realizado. El límite asintótico describe cómo los recursos consumidos aumentan a medida que aumenta el tamaño del problema. El algoritmo "encontrar una subcadena de longitud m en una cadena de longitud n" en la clase System.String es O (nm) pero es * mucho * más * eficiente * en problemas * típicos * que el O (n + m) Algoritmos que podríamos haber implementado. Para calcular la eficiencia, debe considerar los * casos probables *, no los límites asintóticos. –
También observo que su implementación de Fischer-Yates tiene un sesgo; no produce todas las mezclas posibles con la misma probabilidad. Esto probablemente no sea un problema para un algoritmo de mezcla de música, pero es un problema si estuviera usando esto para barajar una baraja de cartas para un juego de póker; dada mi mano, pude determinar rápidamente lo que todos los demás tenían en sus manos. –
@Eric: ¿Por qué crees que la implementación tiene un sesgo? Le da a cada elemento la misma oportunidad de terminar en cada posición de la lista. También he verificado la implementación haciendo millones de mezclas, y no hay ningún sesgo notable. – Guffa
He agregado la solución de Jon Skeet desde this question a mi biblioteca de extensiones. Implementé métodos que toman un generador externo de números aleatorios y crean uno usando una implementación predeterminada (aleatorio).
¿Realmente desea la * solución más eficiente posible * o desea una * solución aceptablemente eficiente *? Porque hay algoritmos que son aún más eficientes que Fischer-Yates siempre que esté dispuesto a abandonar ciertas propiedades agradables, como la falta de parcialidad. (No es que Fischer-Yates implementado a continuación sea imparcial, sino que está profundamente sesgado) –
@Eric: Fischer-Yates _es_ imparcial. La implementación dada a continuación es incorrecta, como ha señalado. Por supuesto, hay implementaciones más eficientes si está dispuesto a tener sesgos. Por ejemplo, haz _nothing_ en absoluto. Realmente no entiendo tu punto. El OP no ha especificado nada, y es razonable (IMO) suponer que está buscando una mezcla uniforme. –
¿Es eso * realmente * razonable? El algoritmo de mezcla en cuestión es para archivos multimedia. Es posible que desee desviar la mezcla hacia la repetición más frecuente de las canciones más valoradas. –