Le meilleur moyen de randomiser un tableau avec .NET
https://stackoverflow.com/questions/108819
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quel est le meilleur moyen de randomiser un tableau de chaînes avec .NET? Mon tableau contient environ 500 chaînes et j'aimerais créer un nouveau Tableau avec les mêmes chaînes mais dans un ordre aléatoire.
Veuillez inclure un exemple en C # dans votre réponse.
La solution
Si vous êtes sur .NET 3.5, vous pouvez utiliser la fraîcheur IEnumerable suivante (VB.NET, pas C #, mais l’idée doit être claire ...):
Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();
Édition: OK et voici le code VB.NET correspondant:
Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()
Deuxième édition, en réponse aux remarques selon lesquelles System.Random "n'est pas threadsafe". et "ne convient qu'aux applications de jouets". en raison du retour d'une séquence temporelle: telle qu'utilisée dans mon exemple, Random () est parfaitement adaptée aux threads, à moins que vous n'autorisiez la routine dans laquelle vous randomisez le tableau à entrer de nouveau, auquel cas vous aurez besoin quelque chose comme lock (MyRandomArray) afin de ne pas corrompre vos données, ce qui protégera également rnd .
En outre, il faut bien comprendre que System.Random, en tant que source d'entropie, n'est pas très puissant. Comme indiqué dans la documentation MSDN , vous devez utiliser un élément dérivé de System.Security.Cryptography.RandomNumberGenerator si vous faites quelque chose lié à la sécurité. Par exemple:
using System.Security.Cryptography;
...
RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();
...
static int GetNextInt32(RNGCryptoServiceProvider rnd)
{
byte[] randomInt = new byte[4];
rnd.GetBytes(randomInt);
return Convert.ToInt32(randomInt[0]);
}
Autres conseils
L’implémentation suivante utilise l’ algorithme de Fisher-Yates AKA. Knuth Shuffle. Il fonctionne dans le temps O (n) et mélange en place, il est donc plus performant que la technique du «tri par hasard», bien que ce soit plus de lignes de code. Voir ici pour des mesures de performances comparatives. J'ai utilisé System.Random, ce qui convient parfaitement à des fins non cryptographiques. *
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;
}
}
}
Utilisation:
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
* Pour les tableaux plus longs, afin de rendre le nombre (extrêmement grand) de permutations également probable, il serait nécessaire de lancer un générateur de nombres pseudo-aléatoires (PRNG) au travers de nombreuses itérations pour que chaque échange génère suffisamment d'entropie. Pour un tableau de 500 éléments, seule une très petite fraction des 500 possibles! Il est possible d'obtenir des permutations à l'aide d'un PRNG. Néanmoins, l’algorithme de Fisher-Yates n’est pas biaisé et le brassage sera donc aussi bon que le RNG que vous utilisez.
Vous recherchez un algorithme de mélange, n'est-ce pas?
D'accord, il y a deux façons de faire cela: le malin, mais les gens semblent toujours avoir du mal à comprendre, et à le faire-mal-alors-peut-être-ce-que-ce-n'est-pas-malin- après tout, et la manière idiote, mais qui s’inquiète parce que ça marche.
Voie muette
- Créez une copie de votre premier tableau, mais attribuez à chaque chaîne un nombre aléatoire.
- Triez le tableau en double en fonction du nombre aléatoire.
Cet algorithme fonctionne bien, mais assurez-vous qu'il est peu probable que votre générateur de nombres aléatoires balise deux chaînes avec le même nombre. En raison du soi-disant Birthday Paradox , cela se produit plus souvent que prévu. Sa complexité temporelle est O ( n journal n ).
Manière intelligente
Je décrirai cela comme un algorithme récursif:
Pour mélanger un tableau de taille n (indices compris dans l'intervalle [0 .. n -1]):
si n = 0si n > 0
- ne rien faire
- (étape récursive) mélange les premiers n -1 éléments du tableau
- choisissez un index aléatoire, x , dans l'intervalle [0 .. n -1]
- échangez l'élément à l'index n -1 avec l'élément à l'index x
L'équivalent itératif consiste à parcourir un tableau, en échangeant des éléments aléatoires au fil du temps, mais en remarquant que vous ne pouvez pas permuter avec un élément après celui indiqué par l'itérateur. Ceci est une erreur très courante et conduit à un remaniement partial.
La complexité temporelle est O ( n ).
Cet algorithme est simple mais peu efficace, O (N 2 ). Tous les " ordre par " les algorithmes sont typiquement O (N log N). Cela ne fait probablement pas de différence en dessous de centaines de milliers d'éléments, mais ce serait le cas pour les grandes listes.
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 raison pour laquelle il s’agit de O (N 2 ) est subtile: List.RemoveAt () est une opération O (N) à moins que vous ne supprimiez dans l’ordre à partir de la fin.
Vous pouvez également créer une méthode d’extension à partir de Matt Howells. Exemple.
namespace System
{
public static class MSSystemExtenstions
{
private static Random rng = new Random();
public static void Shuffle<T>(this T[] array)
{
rng = new Random();
int n = array.Length;
while (n > 1)
{
int k = rng.Next(n);
n--;
T temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
}
}
Ensuite, vous pouvez simplement l'utiliser comme:
string[] names = new string[] {
"Aaron Moline1",
"Aaron Moline2",
"Aaron Moline3",
"Aaron Moline4",
"Aaron Moline5",
"Aaron Moline6",
"Aaron Moline7",
"Aaron Moline8",
"Aaron Moline9",
};
names.Shuffle<string>();
La randomisation du tableau est intensive car vous devez déplacer un tas de chaînes. Pourquoi ne pas simplement lire au hasard dans le tableau? Dans le pire des cas, vous pouvez même créer une classe wrapper avec une méthode getNextString (). Si vous avez vraiment besoin de créer un tableau aléatoire, vous pouvez faire quelque chose comme
for i = 0 -> i= array.length * 5
swap two strings in random places
Le * 5 est arbitraire.
En y réfléchissant bien, vous pourriez faire ceci:
public string[] Randomize(string[] input)
{
List<string> inputList = input.ToList();
string[] output = new string[input.Length];
Random randomizer = new Random();
int i = 0;
while (inputList.Count > 0)
{
int index = r.Next(inputList.Count);
output[i++] = inputList[index];
inputList.RemoveAt(index);
}
return (output);
}
Génère un tableau de nombres flottants ou entiers aléatoires de même longueur. Triez ce tableau et effectuez les échanges correspondants sur votre tableau cible.
Cela donne une sorte vraiment indépendante.
Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();
while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}
Jacco, votre solution est de créer un IComparer personnalisé. Les routines de tri exigent que le comparateur se conforme à plusieurs exigences afin de fonctionner correctement. Le premier d'entre eux est la cohérence. Si le comparateur est appelé sur la même paire d'objets, il doit toujours renvoyer le même résultat. (la comparaison doit également être transitive).
Le non-respect de ces exigences peut entraîner de nombreux problèmes dans la routine de tri, notamment la possibilité d’une boucle infinie.
En ce qui concerne les solutions associant une valeur numérique aléatoire à chaque entrée, puis triées selon cette valeur, elles entraînent un biais inhérent dans la sortie, car chaque fois que deux entrées se voient attribuer la même valeur numérique, le caractère aléatoire de la sortie être compromis. (Dans une routine de tri "stable", la première entrée dans l'entrée sera la première dans la sortie. Array.Sort n'est pas stable, mais il existe toujours un biais basé sur le partitionnement effectué par l'algorithme Quicksort) .
Vous devez réfléchir au niveau d’aléatoire dont vous avez besoin. Si vous exploitez un site de poker sur lequel vous avez besoin de niveaux de chiffrement aléatoires pour vous protéger contre un attaquant déterminé, vos exigences sont très différentes de celles de quelqu'un qui souhaite simplement randomiser une liste de lecture de chansons.
Pour le remaniement de la liste de chansons, l’utilisation d’un PRNG en grappe (comme System.Random) ne pose aucun problème. Pour un site de poker, ce n'est même pas une option et vous devez réfléchir au problème beaucoup plus durement que quiconque ne le fera pour vous sur stackoverflow. (L'utilisation d'un GNA cryptographique n'est qu'un début. Vous devez vous assurer que votre algorithme n'introduit pas de biais, que vous disposez de sources d'entropie suffisantes et que vous n'exposez aucun état interne susceptible de compromettre le caractère aléatoire ultérieur.)
Ce message a déjà été très bien répondu - utilisez une implémentation de Durstenfeld du shuffle Fisher-Yates pour un résultat rapide et impartial. Certaines mises en œuvre ont même été publiées, même si certaines sont en réalité incorrectes.
J'ai écrit quelques articles il y a quelque temps sur implémentant des remaniements complets et partiels à l'aide de cette technique , et (ce second lien est l'endroit où j'espère ajouter de la valeur) également un article de suivi sur comment vérifier si votre implémentation est impartiale , ce qui peut être utilisé pour vérifier n'importe quel algorithme de lecture aléatoire. Vous pouvez voir à la fin du deuxième message l’effet d’une simple erreur dans la sélection de nombres aléatoires peut avoir.
Ok, c’est clairement une bosse de mon côté (excuse-moi ...), mais j’utilise souvent une méthode assez générale et très cryptographique.
public static class EnumerableExtensions
{
static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
{
var randomIntegerBuffer = new byte[4];
Func<int> rand = () =>
{
RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
return BitConverter.ToInt32(randomIntegerBuffer, 0);
};
return from item in enumerable
let rec = new {item, rnd = rand()}
orderby rec.rnd
select rec.item;
}
}
Shuffle () est une extension de tout type IEnumerable. Il est donc possible d’obtenir des nombres de 0 à 1000 dans un ordre aléatoire dans une liste avec
Enumerable.Range(0,1000).Shuffle().ToList()
Cette méthode ne donnera également aucune surprise en ce qui concerne le tri, car la valeur de tri est générée et mémorisée exactement une fois par élément dans la séquence.
Vous n'avez pas besoin d'algorithmes complexes.
Une simple ligne:
Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();
Notez que nous devons d'abord convertir Array en List , si vous n'utilisez pas List à la première place.
Notez également que cela n’est pas efficace pour les très grands tableaux! Sinon, c'est propre & amp; simple.
Il s'agit d'une solution de console complète fonctionnant sur l'exemple fourni ici :
class Program
{
static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };
static void Main()
{
var result = Shuffle(words1);
foreach (var i in result)
{
Console.Write(i + " ");
}
Console.ReadKey();
}
static string[] Shuffle(string[] wordArray) {
Random random = new Random();
for (int i = wordArray.Length - 1; i > 0; i--)
{
int swapIndex = random.Next(i + 1);
string temp = wordArray[i];
wordArray[i] = wordArray[swapIndex];
wordArray[swapIndex] = temp;
}
return wordArray;
}
}
int[] numbers = {0,1,2,3,4,5,6,7,8,9};
List<int> numList = new List<int>();
numList.AddRange(numbers);
Console.WriteLine("Original Order");
for (int i = 0; i < numList.Count; i++)
{
Console.Write(String.Format("{0} ",numList[i]));
}
Random random = new Random();
Console.WriteLine("\n\nRandom Order");
for (int i = 0; i < numList.Capacity; i++)
{
int randomIndex = random.Next(numList.Count);
Console.Write(String.Format("{0} ", numList[randomIndex]));
numList.RemoveAt(randomIndex);
}
Console.ReadLine();
Ce code mélange les nombres dans un tableau.
using System;
// ...
static void Main(string[] args)
{
Console.ForegroundColor = ConsoleColor.Cyan;
int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Shuffle(numbers);
for (int i = 0; i < numbers.Length; i++)
Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
Console.WriteLine();
string[] words = { "this", "is", "a", "string", "of", "words" };
Shuffle(words);
for (int i = 0; i < words.Length; i++)
Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Gray;
Console.Write("Press any key to quit . . . ");
Console.ReadKey(true);
}
static void Shuffle<T>(T[] array)
{
Random random = new Random();
for (int i = 0; i < array.Length; i++)
{
T temporary = array[i];
int intrandom = random.Next(array.Length);
array[i] = array[intrandom];
array[intrandom] = temporary;
}
}
Voici un moyen simple d'utiliser OLINQ:
// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());
// Output array
List<String> lstRandom = new List<string>();
// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);
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;
}
