Il modo più efficiente per “ordinare” (Shuffle) in modo casuale una lista di numeri interi in C #

Ho bisogno di “ordinare” a caso un elenco di numeri interi (0-1999) nel modo più efficiente ansible. Qualche idea?

Attualmente, sto facendo qualcosa del genere:

bool[] bIndexSet = new bool[iItemCount]; for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++) { int iSwapIndex = random.Next(iItemCount); if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex) { int iTemp = values[iSwapIndex]; values[iSwapIndex] = values[iCurIndex]; values[iCurIndex] = values[iSwapIndex]; bIndexSet[iCurIndex] = true; bIndexSet[iSwapIndex] = true; } } 

Un buon algoritmo shuffling lineare è il rimescolamento di Fisher-Yates .

Un problema che troverai con il tuo algoritmo proposto è che mentre ti avvicini alla fine della shuffle, il tuo ciclo passerà molto tempo alla ricerca di elementi scelti a caso che non sono ancora stati scambiati. Questo può richiedere un tempo indeterminato una volta che arriva all’ultimo elemento da scambiare.

Inoltre, sembra che il tuo algoritmo non terminerà mai se ci sono un numero dispari di elementi da ordinare.

 static Random random = new Random(); public static IEnumerable RandomPermutation(IEnumerable sequence) { T[] retArray = sequence.ToArray(); for (int i = 0; i < retArray.Length - 1; i += 1) { int swapIndex = random.Next(i, retArray.Length); if (swapIndex != i) { T temp = retArray[i]; retArray[i] = retArray[swapIndex]; retArray[swapIndex] = temp; } } return retArray; } 

modificato per gestire elenchi o altri oggetti che implementano IEnumerable

Possiamo creare un metodo di estensione per ottenere un enumeratore casuale per qualsiasi raccolta IList

 class Program { static void Main(string[] args) { IList l = new List(); l.Add(7); l.Add(11); l.Add(13); l.Add(17); foreach (var i in l.AsRandom()) Console.WriteLine(i); Console.ReadLine(); } } public static class MyExtensions { public static IEnumerable AsRandom(this IList list) { int[] indexes = Enumerable.Range(0, list.Count).ToArray(); Random generator = new Random(); for (int i = 0; i < list.Count; ++i ) { int position = generator.Next(i, list.Count); yield return list[indexes[position]]; indexes[position] = indexes[i]; } } } 

Questo usa un rimescolamento di Fisher-Yates inverso sugli indici della lista che vogliamo elencare casualmente. È un po 'di dimensioni hog (allocando 4 * list.Count bytes), ma viene eseguito in O (n).

Come ha sottolineato Greg, lo shuffle di Fisher-Yates sarebbe l’approccio migliore. Ecco un’implementazione dell’algoritmo da Wikipedia:

 public static void shuffle (int[] array) { Random rng = new Random(); // ie, java.util.Random. int n = array.length; // The number of items left to shuffle (loop invariant). while (n > 1) { int k = rng.nextInt(n); // 0 < = k < n. n--; // n is now the last pertinent index; int temp = array[n]; // swap array[n] with array[k] (does nothing if k == n). array[n] = array[k]; array[k] = temp; } } 

L'implementazione sopra si basa su Random.nextInt (int) che fornisce risultati sufficientemente casuali e imparziali

Non sono sicuro del fattore di efficienza, ma ho usato qualcosa di simile al seguente, se non si è contrari all’uso di un ArrayList:

 private ArrayList ShuffleArrayList(ArrayList source) { ArrayList sortedList = new ArrayList(); Random generator = new Random(); while (source.Count > 0) { int position = generator.Next(source.Count); sortedList.Add(source[position]); source.RemoveAt(position); } return sortedList; } 

Usando questo, non devi preoccuparti dello scambio intermedio.

Per migliorare la tua efficienza puoi mantenere un insieme di valori / indici che sono stati scambiati piuttosto che un valore booleano per indicare che sono stati scambiati. Scegli il tuo indice di swap randomizzato dal pool rimanente. Quando la piscina è 0, o quando hai fatto la lista iniziale, hai finito. Non è ansible provare a selezionare un valore di indice di scambio casuale.

Quando fai uno scambio, rimuovili dalla piscina.

Per la dimensione dei dati che stai guardando non è un grosso problema.

 itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList() 

La risposta dell’ICR è molto veloce, ma gli array risultanti non sono distribuiti normalmente. Se vuoi una distribuzione normale, ecco il codice:

  public static IEnumerable RandomPermutation(this IEnumerable sequence, int start,int end) { T[] array = sequence as T[] ?? sequence.ToArray(); var result = new T[array.Length]; for (int i = 0; i < start; i++) { result[i] = array[i]; } for (int i = end; i < array.Length; i++) { result[i] = array[i]; } var sortArray=new List>(array.Length-start-(array.Length-end)); lock (random) { for (int i = start; i < end; i++) { sortArray.Add(new KeyValuePair(random.NextDouble(), array[i])); } } sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key)); for (int i = start; i < end; i++) { result[i] = sortArray[i - start].Value; } return result; } 

Si noti che nei miei test, questo algoritmo era 6 volte più lento di quello fornito dall'ICR, tuttavia questo è l'unico modo che ho potuto ottenere per ottenere una normale distribuzione dei risultati

Non sarebbe qualcosa di simile a questo lavoro?

 var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; var random = new Random(); list.Sort((a,b)=>random.Next(-1,1)); 

Immagino che le ultime due righe debbano essere intercambiate nella risposta di Michea. Quindi, il codice potrebbe essere simile

  public static void shuffle(int[] array) { Random rng = new Random(); // ie, java.util.Random. int n = array.Length; // The number of items left to shuffle (loop invariant). while (n > 1) { int k = rng.Next(n); // 0 < = k < n. n--; // n is now the last pertinent index; int temp = array[n]; // swap array[n] with array[k] (does nothing if k == n). array[n] = array[k]; array[k] = temp; } } 

che dire :

 System.Array.Sort(arrayinstance, RandomizerMethod); ... //any evoluated random class could do it ! private static readonly System.Random Randomizer = new System.Random(); private static int RandomizerMethod(T x, T y) where T : IComparable { if (x.CompareTo(y) == 0) return 0; return Randomizer.Next().CompareTo(Randomizer.Next()); } 

Ecco!

Ho creato un metodo utilizzando una Hashtable temporanea, consentendo alla sequenza di chiavi naturali di Hashtable di essere randomizzata. Basta aggiungere, leggere e scartare.

 int min = 1; int max = 100; Random random; Hashtable hash = new Hashtable(); for (int x = min; x < = max; x++) { random = new Random(DateTime.Now.Millisecond + x); hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x); } foreach (int key in hash.Keys) { HttpContext.Current.Response.Write("
" + hash[key] + "::" + key); } hash.Clear(); // cleanup