Я прочитал статью о различных алгоритмах перетасовки в Coding Horror. Я видел, что где-то люди сделали это, чтобы перетасовать список:
var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());
Это хороший алгоритм перетасовки? Как это работает? Это приемлемый способ сделать это?
Это не способ перетасовки, который мне нравится, в основном на том основании, что он O (n log n) не имеет веских оснований, когда легко реализовать перетасовку O (n). Код в вопросе "работает", в основном предоставляя случайный (надеюсь, уникальный!) Номер для каждого элемента, а затем упорядочивая элементы в соответствии с этим числом.
Я предпочитаю вариант Durstenfield Fisher-Yates shuffle, который меняет элементы.
Реализация простого метода расширения Shuffle будет состоять в основном из вызова ToList или ToArray на входе, а затем с использованием существующей реализации Fisher-Yates. (Перейдите в Random в качестве параметра, чтобы сделать жизнь в целом более приятной.) Существует множество реализаций... Я, вероятно, получил один ответ.
Хорошая вещь о таком методе расширения заключается в том, что для читателя было бы очень ясно, что вы на самом деле пытаетесь сделать.
EDIT: здесь простая реализация (без проверки ошибок!):
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
T[] elements = source.ToArray();
// Note i > 0 to avoid final pointless iteration
for (int i = elements.Length-1; i > 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
int swapIndex = rng.Next(i + 1);
T tmp = elements[i];
elements[i] = elements[swapIndex];
elements[swapIndex] = tmp;
}
// Lazily yield (avoiding aliasing issues etc)
foreach (T element in elements)
{
yield return element;
}
}
EDIT: комментарии к производительности ниже напомнили мне, что мы можем фактически вернуть элементы при их тасовании:
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
T[] elements = source.ToArray();
for (int i = elements.Length - 1; i >= 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
// ... except we don't really need to swap it fully, as we can
// return it immediately, and afterwards it irrelevant.
int swapIndex = rng.Next(i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
}
}
Теперь будет выполняться столько же работы, сколько нужно.
Обратите внимание, что в обоих случаях вы должны быть осторожны с экземпляром Random, который вы используете как:
Random примерно в одно и то же время приведет к той же последовательности случайных чисел (при использовании таким же образом)Random не является потокобезопасным.У меня статья о Random, которая более подробно описывает эти проблемы и предоставляет решения.
Это основано на Jon Skeet answer.
В этом ответе массив перетасовывается, а затем возвращается с помощью yield. Конечным результатом является то, что массив хранится в памяти в течение времени foreach, а также объектов, необходимых для итерации, и все же стоимость все в начале - выход в основном пустой цикл.
Этот алгоритм используется много в играх, где выбираются первые три элемента, а остальные будут нужны позже, если вообще. Мое предложение состоит в том, чтобы yield цифры, как только они были заменены. Это уменьшит затраты на запуск, сохраняя при этом итерационные затраты на O (1) (в основном 5 операций за итерацию). Общая стоимость останется прежней, но перетасовка сама по себе будет быстрее. В тех случаях, когда это называется collection.Shuffle().ToArray(), теоретически это не имеет никакого значения, но в вышеупомянутых случаях использования это ускорит запуск. Кроме того, это сделает алгоритм полезным для случаев, когда вам нужно всего несколько уникальных элементов. Например, если вам нужно вытащить три карты из колоды из 52, вы можете вызвать deck.Shuffle().Take(3) и произойдет только три свопа (хотя весь массив нужно будет скопировать первым).
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
T[] elements = source.ToArray();
// Note i > 0 to avoid final pointless iteration
for (int i = elements.Length - 1; i > 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
int swapIndex = rng.Next(i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
// we don't actually perform the swap, we can forget about the
// swapped element because we already returned it.
}
// there is one item remaining that was not returned - we return it now
yield return elements[0];
}
Начиная с этой цитаты Skeet:
Это не способ перетасовки, который мне нравится, в основном на том основании, что он O (n log n) не имеет веских оснований, когда легко реализовать перетасовку O (n). Код в вопросе "работает", в основном предоставляя каждому элементу случайный (hopefully unique!) номер, а затем упорядочивая элементы в соответствии с этим числом.
Я немного объясню причину , надеюсь, уникальной!
Теперь из Enumerable.OrderBy:
Этот метод выполняет стабильную сортировку; то есть, если ключи из двух элементов равны, порядок элементов сохраняется
Это очень важно! Что произойдет, если два элемента "получат" одно и то же случайное число? Бывает, что они остаются в том же порядке, что и в массиве. Теперь, какова вероятность этого? Трудно точно рассчитать, но есть проблема с днем рождения, и это именно эта проблема.
Теперь, это реально? Это правда?
Как всегда, когда есть сомнения, напишите несколько строк программы: http://pastebin.com/5CDnUxPG
Этот маленький блок кода перемещает массив из трех элементов определенное количество раз, используя алгоритм Фишера-Йейтс, выполненный назад, алгоритм Фишера-Йейса, выполненный вперед (в wiki есть два алгоритма псевдокода... Они дают эквивалентные результаты, но каждый выполняется от первого до последнего элемента, а другой - от последнего к первому элементу), наивный неправильный алгоритм http://blog.codinghorror.com/the-danger-of-naivete/ и используя .OrderBy(x => r.Next()) и .OrderBy(x => r.Next(someValue)).
Теперь Random.Next является
32-разрядное целое число со знаком, которое больше или равно 0 и меньше MaxValue.
что эквивалентно
OrderBy(x => r.Next(int.MaxValue))
Чтобы проверить, существует ли эта проблема, мы могли бы увеличить массив (что-то очень медленное) или просто уменьшить максимальное значение генератора случайных чисел (int.MaxValue не является "специальным" числом... Это просто очень большое число). В конце концов, если алгоритм не будет предвзятым с точки зрения устойчивости OrderBy, то любой диапазон значений должен дать тот же результат.
Затем программа проверяет некоторые значения в диапазоне 1... 4096. Посмотрев на результат, совершенно ясно, что при низких значениях (< 128) алгоритм очень предвзятый (4-8%). С 3 значениями требуется не менее r.Next(1024). Если вы сделаете массив больше (4 или 5), то даже r.Next(1024) недостаточно. Я не эксперт в перетасовке и в математике, но я думаю, что для каждого дополнительного бита длины массива вам нужно 2 дополнительных бита максимального значения (потому что парадокс дня рождения связан с sqrt (numvalues)), поэтому что если максимальное значение равно 2 ^ 31, я скажу, что вы должны иметь возможность сортировать массивы до 2 ^ 12/2 ^ 13 бит (4096-8192 элементов)
Вероятно, это нормально для большинства целей, и почти всегда он генерирует действительно случайное распределение (за исключением случаев, когда Random.Next() создает два одинаковых случайных числа).
Он работает, назначая каждому элементу серии случайное целое число, а затем упорядочивая последовательность этими целыми числами.
Это абсолютно приемлемо для 99,9% приложений (если вам не нужно полностью обрабатывать крайний вариант). Кроме того, допустимо отклонение skeet к его времени выполнения, поэтому, если вы перетасовываете длинный список, вы можете не захотеть его использовать.
Похоже на хороший алгоритм перетасовки, если вы не слишком беспокоитесь о производительности. Единственная проблема, которую я хотел бы указать, заключается в том, что ее поведение не поддается контролю, поэтому вам может быть трудно его протестировать.
Один из возможных вариантов состоит в том, что в качестве параметра генератор случайных чисел (или случайный генератор в качестве параметра) передается семя, поэтому вы можете более легко контролировать и тестировать его.
Это произошло много раз. Найдите Fisher-Yates в StackOverflow.
Вот пример кода С#, который я написал для этого алгоритма. Вы можете параметризовать его на каком-то другом типе, если хотите.
static public class FisherYates
{
// Based on Java code from wikipedia:
// http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
static public void Shuffle(int[] deck)
{
Random r = new Random();
for (int n = deck.Length - 1; n > 0; --n)
{
int k = r.Next(n+1);
int temp = deck[n];
deck[n] = deck[k];
deck[k] = temp;
}
}
}
Я нашел, что Jon Skeet отвечает, что он полностью удовлетворительный, но мой робоскандер-клиент будет сообщать о любом случае Random в качестве недостатка безопасности. Поэтому я заменил его на System.Security.Cryptography.RNGCryptoServiceProvider. В качестве бонуса он исправляет эту проблему безопасности потоков, о которой упоминалось. С другой стороны, RNGCryptoServiceProvider было измерено как 300x медленнее, чем при использовании Random.
Использование:
using (var rng = new RNGCryptoServiceProvider())
{
var data = new byte[4];
yourCollection = yourCollection.Shuffle(rng, data);
}
Метод:
/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data)
{
var elements = source.ToArray();
for (int i = elements.Length - 1; i >= 0; i--)
{
rng.GetBytes(data);
var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
}
}
Немного несвязанный, но вот интересный метод (хотя он действительно избыточен, ДЕЙСТВИТЕЛЬНО реализован) для действительно случайного генерации бросков кубиков!
Причина, по которой я публикую это здесь, заключается в том, что он делает несколько интересных моментов о том, как его пользователи отреагировали на идею использования алгоритмов для перетасовки по фактическим кубикам. Конечно, в реальном мире такое решение есть только для действительно экстремальных концов спектра, где случайность имеет такое большое влияние и, возможно, влияние влияет на деньги;).
Я бы сказал, что многие ответы здесь похожи на "Этот алгоритм перетасовывается, создавая новое случайное значение для каждого значения в списке, а затем упорядочивая список этими случайными значениями" может быть очень неправильным!
Я бы подумал, что это НЕ присваивает случайное значение каждому элементу исходной коллекции. Вместо этого может существовать алгоритм сортировки, работающий как Quicksort, который будет вызывать функцию сравнения приблизительно n log n раз. Некоторый сорт algortihm действительно ожидает, что эта функция сравнения будет стабильной и всегда возвращает тот же результат!
Не может быть, что IEnumerableSorter вызывает функцию сравнения для каждого шага алгоритма, например. quicksort и каждый раз вызывает функцию x => r.Next() для обоих параметров без их кэширования!
В этом случае вы действительно можете испортить алгоритм сортировки и сделать его намного хуже ожиданий, которые создает алгоритм. Конечно, он в конечном итоге станет стабильным и что-то вернет.
Я могу проверить это позже, поставив вывод отладки внутри новой функции "Далее", чтобы посмотреть, что произойдет. В Reflector я не мог сразу узнать, как это работает.
Ищете алгоритм? Вы можете использовать класс ShuffleList:
class ShuffleList<T> : List<T>
{
public void Shuffle()
{
Random random = new Random();
for (int count = Count; count > 0; count--)
{
int i = random.Next(count);
Add(this[i]);
RemoveAt(i);
}
}
}
Затем используйте его следующим образом:
ShuffleList<int> list = new ShuffleList<int>();
// Add elements to your list.
list.Shuffle();
Пусть возьмем начальный отсортированный список из 5 первых целых чисел: { 0, 1, 2, 3, 4 }.
Метод начинается с подсчета нумерации элементов и вызывает его count. Затем, когда count уменьшается на каждом шаге, он принимает случайное число между 0 и count и перемещает его в конец списка.
В следующем поэтапном примере элементы, которые могут быть перемещены, выделены курсивом, выбранный элемент жирный:
0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2
Этот алгоритм перемещается путем создания нового случайного значения для каждого значения в списке, а затем упорядочивает список по этим случайным значениям. Подумайте об этом, добавив новый столбец в таблицу в памяти, затем заполнив его идентификаторами GUID, а затем отсортировав по этому столбцу. Похож на эффективный способ для меня (особенно с лямбда-сахаром!)
Время запуска для запуска кода с очисткой всех потоков и кешем каждого нового теста,
Первый неудачный код. Он работает на LINQPad. Если вы выполните тест для этого кода.
Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
list.Add(new String[] {"1","X"});
list.Add(new String[] {"2","A"});
list.Add(new String[] {"3","B"});
list.Add(new String[] {"4","C"});
list.Add(new String[] {"5","D"});
list.Add(new String[] {"6","E"});
//list.OrderBy (l => r.Next()).Dump();
list.OrderBy (l => Guid.NewGuid()).Dump();
st.Stop();
Console.WriteLine(st.Elapsed.TotalMilliseconds);
list.OrderBy(x = > r.Next()) использует 38.6528 мс
list.OrderBy(x = > Guid.NewGuid()) использует 36.7634 мс (рекомендуется из MSDN.)
после второго раза оба они используют в одно и то же время.
EDIT:
ИСПЫТАТЕЛЬНЫЙ КОД на Intel Core i7 [email protected], RAM 8 ГБ DDR3 @1600, HDD SATA 5200 об/мин с [Данные: www.dropbox.com/s/pbtmh5s9lw285kp/data]
using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;
namespace Algorithm
{
class Program
{
public static void Main(string[] args)
{
try {
int i = 0;
int limit = 10;
var result = GetTestRandomSort(limit);
foreach (var element in result) {
Console.WriteLine();
Console.WriteLine("time {0}: {1} ms", ++i, element);
}
} catch (Exception e) {
Console.WriteLine(e.Message);
} finally {
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
}
public static IEnumerable<double> GetTestRandomSort(int limit)
{
for (int i = 0; i < 5; i++) {
string path = null, temp = null;
Stopwatch st = null;
StreamReader sr = null;
int? count = null;
List<string> list = null;
Random r = null;
GC.Collect();
GC.WaitForPendingFinalizers();
Thread.Sleep(5000);
st = Stopwatch.StartNew();
#region Import Input Data
path = Environment.CurrentDirectory + "\\data";
list = new List<string>();
sr = new StreamReader(path);
count = 0;
while (count < limit && (temp = sr.ReadLine()) != null) {
// Console.WriteLine(temp);
list.Add(temp);
count++;
}
sr.Close();
#endregion
// Console.WriteLine("--------------Random--------------");
// #region Sort by Random with OrderBy(random.Next())
// r = new Random();
// list = list.OrderBy(l => r.Next()).ToList();
// #endregion
// #region Sort by Random with OrderBy(Guid)
// list = list.OrderBy(l => Guid.NewGuid()).ToList();
// #endregion
// #region Sort by Random with Parallel and OrderBy(random.Next())
// r = new Random();
// list = list.AsParallel().OrderBy(l => r.Next()).ToList();
// #endregion
// #region Sort by Random with Parallel OrderBy(Guid)
// list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
// #endregion
// #region Sort by Random with User-Defined Shuffle Method
// r = new Random();
// list = list.Shuffle(r).ToList();
// #endregion
// #region Sort by Random with Parallel User-Defined Shuffle Method
// r = new Random();
// list = list.AsParallel().Shuffle(r).ToList();
// #endregion
// Result
//
st.Stop();
yield return st.Elapsed.TotalMilliseconds;
foreach (var element in list) {
Console.WriteLine(element);
}
}
}
}
}
Результат Описание: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
Статистика результатов: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG
Вывод:
Предположим: LINQ OrderBy (r.Next()) и OrderBy (Guid.NewGuid()) не хуже пользовательского метода случайного воспроизведения в первом решении.
Ответ: Это противоречие.