Eventuali duplicati:
Randomize a List<T> in C#Lista Shuffle <T>
Ho una lista che contiene molte migliaia di FilePath alle sedi di file audio, e si chiedeva che sarebbe il modo più efficiente "mischiare" una lista?
Qualsiasi aiuto è molto apprezzato :)
Grazie
Fisher-Yates Shuffle o come è noto anche come, Knuth shuffle.
... che è O (n), quindi non puoi ottenere di meglio. – Guffa
... Ti ho appena sviato perché mi è piaciuta la tua risposta :) Non so perché è stato sottotitolato? –
btw, per un rimescolamento più veloce, ti suggerirei di mescolare un elenco/array di numeri interi (usando qualsiasi metodo tu scelga) e di usare l'elenco/array mischiato come un indice nell'elenco dei nomi di file. Scambiare i nomi dei file potrebbe rivelarsi un collo di bottiglia. –
myList.OrderBy(Guid.NewGuid())
Alcuni algoritmi di generazione GUID generano valori monotoni, pertanto potrebbe non dare risultati casuali. Tuttavia, qualcosa di simile usando un'altra fonte di casualità (probabilmente casuale) funzionerebbe. – heneryville
Ecco un semplice (ma efficace) attuazione del riordino 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 leggera variazione:
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;
}
Poiché si tratta di un O (n) operazione, è il modo più efficace per mischiare una lista. Poiché tutti gli elementi nell'elenco devono avere la possibilità di essere spostati, non è possibile mescolare un elenco in modo più efficiente di O (n).
Ho eseguito un piccolo test delle prestazioni mescolando un milione di articoli mille volte ciascuno utilizzando questo metodo e la risposta attualmente accettata (LINQ OrderBy), e questo è circa 15 volte (!) Più veloce.
Stai confondendo il limite asintotico con l'efficienza. L'efficienza è definita come risorse consumate per unità di lavoro svolto. Il limite asintotico descrive come le risorse consumate aumentano all'aumentare della dimensione del problema. L'algoritmo "trova una sottostringa di lunghezza m in una stringa di lunghezza n" nella classe System.String è O (nm) ma è * lontano * più * efficiente * su * tipici * problemi rispetto a O (n + m) algoritmi che avremmo potuto implementare. Per calcolare l'efficienza devi considerare i * casi probabili *, non i confini asintotici. –
Ho anche notato che la tua implementazione di Fischer-Yates ha un pregiudizio; non produce tutte le mescolanze possibili con uguale probabilità. Questo probabilmente non è un problema per un algoritmo di mescolamento musicale, ma è un problema se lo si stesse usando per mischiare un mazzo di carte per un gioco di poker; data la mia mano, ho potuto determinare rapidamente cosa avevano in mano tutti gli altri. –
@Eric: Perché pensi che l'implementazione abbia un pregiudizio? Dà ad ogni oggetto la stessa possibilità di finire in ogni posizione nella lista. Inoltre ho verificato l'implementazione facendo milioni di shuffles, e non c'è pregiudizio evidente. – Guffa
Ho aggiunto la soluzione di Jon Skeet da this question alla mia libreria Estensioni. Ho implementato metodi che prendono entrambi un generatore di numeri casuali esterno e ne creano uno utilizzando un'implementazione predefinita (casuale).
Vuoi davvero la * soluzione più efficiente possibile * o vuoi una * soluzione accettabilmente efficiente *? Perché ci sono algoritmi ancora più efficienti che Fischer-Yates ti ha fornito di voler abbandonare certe proprietà, come la mancanza di pregiudizi. (Non che Fischer-Yates come implementato sotto è imparziale, è profondamente prevenuto.) –
@Eric: Fischer-Yates _is_ imparziali. L'implementazione indicata di seguito non è corretta, come hai notato. Naturalmente ci sono implementazioni più efficienti se si è disposti ad avere pregiudizi. Ad esempio, fai _nothing_ a tutti. Non capisco davvero il tuo punto. L'OP non ha specificato nulla ed è ragionevole (IMO) presumere che stiano cercando uno shuffle uniforme. –
È * veramente * ragionevole? L'algoritmo shuffle in questione è per i file multimediali. Si potrebbe voler spingere lo shuffle a ripetere più frequentemente le canzoni più apprezzate. –