In LINQ, orderby() esegue la funzione di confronto solo una volta o la esegue quando necessario?

Question

Ho trovato un metodo per mescolare un array su Internet.

Random rand = new Random(); 
shuffledArray = myArray.OrderBy(x => rand.Next()).ToArray(); 

Tuttavia, sono un po 'preoccupato per la correttezza di questo metodo. Se OrderBy esegue x => rand.Next() molte volte per lo stesso articolo, i risultati potrebbero entrare in conflitto e dare origine a cose strane (possibilmente eccezioni).

Ho provato e tutto va bene, ma voglio ancora sapere se questo è assolutamente sicuro e funziona sempre come previsto, e non riesco a trovare la risposta di Google.

Qualcuno potrebbe darmi qualche spiegazione?

Grazie in anticipo.

Answer 1

L'approccio dovrebbe funzionare ma è lento.

Funziona perché OrderBy prima calcola le chiavi per ogni voce utilizzando il selettore di chiave, quindi ordina i tasti. Quindi il selettore di chiave viene chiamato solo una volta per elemento.

In .NET Reflector, vedere il metodo ComputeKeys nella classe EnumerableSorter.

this.keys = new TKey[count]; 
for (int i = 0; i < count; i++) 
{ 
    this.keys[i] = this.keySelector(elements[i]); 
} 
// etc... 

se questo è assolutamente sicuro e funziona sempre come previsto

È documentato quindi in teoria potrebbe cambiare in futuro.

Per la riproduzione in ordine casuale è possibile utilizzare lo Fisher-Yates shuffle. Questo è anche più efficiente - usando solo O (n) time e shuffling sul posto invece di O (n log (n)) time e O (n) extra di memoria.

questione connessa

• C#: Is using Random and OrderBy a good shuffle algorithm?

Answer 2

L'utilizzo di un shufflebag funzionerà sicuramente.

Per quanto riguarda il metodo orderby, penso che non sia del tutto casuale in quanto viene mantenuto l'ordine degli elementi uguali. Quindi se hai un array casuale [5 6 7 2 6] allora gli elementi ai due sei saranno sempre nello stesso ordine.

Avrei dovuto eseguire un test di frequenza per essere sicuro.

Answer 3

Presumo che si sta parlando di LINQ to Objects, nel qual caso la chiave utilizzata per il confronto viene generato solo una volta per elemento. (Si noti che questo è solo un dettaglio dell'implementazione corrente e potrebbe cambiare, anche se è molto improbabile perché un tale cambiamento introdurrebbe i bug che menzionassi.)

Per rispondere alla tua domanda più generale: il tuo approccio dovrebbe funzionare, ma ci sono modi migliori per farlo. L'utilizzo di OrderBy sarà in genere delle prestazioni O (n log n), mentre un Fisher-Yates-Durstenfeld shuffle sarà O (n).

(C'è uno example Shuffle extension for IEnumerable<T> here o uno in-place equivalent for IList<T> here, se si preferisce.)