Лучший способ рандомизировать массив с помощью .NET
https://stackoverflow.com/questions/108819
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Каков наилучший способ рандомизировать массив строк с помощью .NET?Мой массив содержит около 500 строк, и я хотел бы создать новую Array с теми же строками, но в случайном порядке.
Пожалуйста, включите в свой ответ пример C #.
Решение
Если вы используете .NET 3.5, вы можете использовать следующую IEnumerable cool (VB.NET, не C #, но идея должна быть понятна ...):
Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();
Редактировать:Хорошо, и вот соответствующий VB.NET код:
Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()
Вторая правка, в ответ на замечания этой системы.Случайное "не является потокобезопасным" и "подходит только для игрушечных приложений" из-за возврата последовательности, основанной на времени:как используется в моем примере, Random() абсолютно потокобезопасен, если только вы не разрешаете повторный ввод процедуры, в которой вы рандомизируете массив, и в этом случае вам понадобится что-то вроде lock (MyRandomArray) в любом случае, чтобы не повредить ваши данные, которые защитят rnd также хорошо.
Кроме того, следует хорошо понимать, что система.Случайность как источник энтропии не очень сильна.Как отмечалось в Документация MSDN, вы должны использовать что - то производное от System.Security.Cryptography.RandomNumberGenerator если вы делаете что-то, связанное с безопасностью.Например:
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]);
}
Другие советы
Следующая реализация использует Алгоритм Фишера-Йейтса ОН ЖЕ Шаффл Кнута.Он выполняется за O (n) раз и перетасовывается на месте, поэтому работает лучше, чем метод "сортировки случайным образом", хотя это больше строк кода.Видишь здесь для некоторых сравнительных измерений производительности.Я использовал System.Random, который подходит для некриптографических целей.*
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;
}
}
}
Использование:
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
* Для более длинных массивов, чтобы сделать (чрезвычайно большое) количество перестановок равновероятными, было бы необходимо запустить генератор псевдослучайных чисел (PRNG) через множество итераций для каждой замены, чтобы получить достаточную энтропию.Для массива из 500 элементов это лишь очень малая часть от возможных 500!перестановки можно будет получить с помощью PRNG.Тем не менее, алгоритм Фишера-Йейтса беспристрастен, и поэтому перетасовка будет такой же хорошей, как и используемый вами ГСЧ.
Вы ищете алгоритм перетасовки, верно?
Ладно, есть два способа сделать это:в clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-все пути, и тупой как скалы-но-кто-заботится-потому что это работает так.
Глупый способ
- Создайте дубликат вашего первого массива, но помечать каждую строку следует случайным числом.
- Отсортируйте повторяющийся массив по случайному числу.
Этот алгоритм работает хорошо, но убедитесь, что ваш генератор случайных чисел вряд ли будет помечать две строки одним и тем же номером.Из-за так называемого Парадокс Дня рождения, это происходит чаще, чем вы могли бы ожидать.Его временная сложность равна O(n журнал регистрации n).
Умный способ
Я опишу это как рекурсивный алгоритм:
Чтобы перетасовать массив нужного размера n (индексы в диапазоне [0..n-1]):
если n = 0если n > 0
- ничего не делай
- (рекурсивный шаг) перетасуйте первый n-1 элемент массива
- выберите случайный индекс, x, в диапазоне [0..n-1]
- поменяйте местами элемент по индексу n-1 с элементом по индексу x
Итеративный эквивалент заключается в прохождении итератора по массиву, меняясь местами со случайными элементами по мере продвижения, но обратите внимание, что вы не можете поменяться местами с элементом после тот, на который указывает итератор.Это очень распространенная ошибка, которая приводит к предвзятой перетасовке.
Временная сложность равна O(n).
Этот алгоритм прост, но не эффективен, O (N2).Все алгоритмы "упорядочивания по" обычно имеют значение O (N log N).Вероятно, это не имеет значения ниже сотен тысяч элементов, но это было бы для больших списков.
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);
}
Причина, по которой это O (N2) является тонким: Список.RemoveAt() является операцией O (N), если вы не удаляете по порядку с конца.
Вы также можете создать метод расширения на основе Matt Howells.Пример.
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;
}
}
}
}
Тогда вы можете просто использовать его как:
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>();
Рандомизация массива является трудоемкой, так как вам приходится перемещать множество строк.Почему бы просто не выполнить случайное считывание из массива?В худшем случае вы могли бы даже создать класс-оболочку с помощью getNextString().Если вам действительно нужно создать случайный массив, то вы могли бы сделать что-то вроде
for i = 0 -> i= array.length * 5
swap two strings in random places
*5 является произвольным.
Просто шальная мысль пришла мне в голову, что ты мог бы это сделать:
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);
}
Сгенерируйте массив случайных чисел с плавающей точкой или целых чисел одинаковой длины.Отсортируйте этот массив и выполните соответствующие замены в вашем целевом массиве.
Это дает действительно независимую сортировку.
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);
}
Джакко, ваше решение заключается в том, что использование пользовательского IComparer небезопасно.Процедуры сортировки требуют, чтобы средство сравнения соответствовало нескольким требованиям для правильной работы.Первое из них - это последовательность.Если средство сравнения вызывается для одной и той же пары объектов, оно всегда должно возвращать один и тот же результат.(сравнение также должно быть транзитивным).
Несоблюдение этих требований может вызвать любое количество проблем в процедуре сортировки, включая возможность бесконечного цикла.
Что касается решений, которые связывают случайное числовое значение с каждой записью и затем сортируют по этому значению, то они приводят к неизбежному смещению выходных данных, поскольку каждый раз, когда двум записям присваивается одно и то же числовое значение, случайность выходных данных будет нарушена.(В "стабильной" процедуре сортировки то, что стоит первым на входе, будет первым и на выходе.Массив.Сортировка не является стабильной, но все еще существует смещение, основанное на разбиении, выполняемом алгоритмом быстрой сортировки).
Вам нужно немного подумать о том, какой уровень случайности вам требуется.Если вы управляете покерным сайтом, где вам нужны криптографические уровни случайности для защиты от решительного злоумышленника, у вас совсем другие требования, чем у кого-то, кто просто хочет рандомизировать список воспроизведения песен.
Для перетасовки списка композиций нет проблем с использованием заполненного PRNG (например, System.Random).Для покерного сайта это даже не вариант, и вам нужно подумать над проблемой намного усерднее, чем кто-либо собирается сделать за вас на stackoverflow.(использование криптографического RNG - это только начало, вам нужно убедиться, что ваш алгоритм не вносит смещения, что у вас достаточно источников энтропии и что вы не раскрываете никакого внутреннего состояния, которое поставило бы под угрозу последующую случайность).
На этот пост уже был довольно хороший ответ - используйте реализацию Durstenfeld метода Фишера-Йейтса в случайном порядке для быстрого и непредвзятого результата.Были даже опубликованы некоторые реализации, хотя я отмечаю, что некоторые из них на самом деле неверны.
Некоторое время назад я написал пару постов о реализация полной и частичной перетасовки с использованием этой техники, и (по этой второй ссылке я надеюсь добавить ценность) также последующий пост о том, как проверить, является ли ваша реализация непредвзятой, который может быть использован для проверки любого алгоритма перетасовки.Вы можете увидеть в конце второго поста, какой эффект может произвести простая ошибка при выборе случайного числа.
Хорошо, это явно удар с моей стороны (приношу извинения ...), но я часто использую довольно общий и криптографически надежный метод.
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() является расширением для любого IEnumerable, поэтому получение, скажем, чисел от 0 до 1000 в случайном порядке в списке может быть выполнено с помощью
Enumerable.Range(0,1000).Shuffle().ToList()
Этот метод также не преподнесет никаких сюрпризов, когда дело дойдет до сортировки, поскольку значение сортировки генерируется и запоминается ровно один раз для каждого элемента в последовательности.
Вам не нужны сложные алгоритмы.
Всего одна простая строчка:
Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();
Обратите внимание, что нам нужно преобразовать Array к a List во-первых, если вы не используете List в первую очередь.
Кроме того, имейте в виду, что это неэффективно для очень больших массивов!В остальном все чисто и просто.
Это комплексное решение для рабочей консоли, основанное на пример, приведенный здесь:
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();
Этот код перетасовывает числа в массиве.
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;
}
}
Вот простой способ с помощью 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;
}
