我在Coding Horror阅读了一篇关于各种 shuffle 算法的文章。我已经看到人们在某处这样做是为了对列表进行洗牌：
var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());
这是一个好的洗牌算法吗？它是如何工作的？这是一种可接受的方式吗？
问问题
49448 次
13 回答
218
这不是我喜欢的洗牌方式，主要是因为它是 O(n log n) 没有充分理由，因为它很容易实现 O(n) 洗牌。问题中的代码通过基本上给每个元素一个随机（希望是唯一的！）数字来“工作”，然后根据该数字对元素进行排序。
我更喜欢 Durstenfeld 的Fisher-Yates shuffle变体，它可以交换元素。
实现一个简单的Shuffle扩展方法基本上包括调用ToList或ToArray输入，然后使用现有的 Fisher-Yates 实现。（Random作为参数传递，使生活总体上更美好。）周围有很多实现......我可能在某个地方得到了一个答案。
这种扩展方法的好处是，读者会很清楚你实际上想要做什么。
编辑：这是一个简单的实现（没有错误检查！）：
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;
}
}
编辑：下面对性能的评论提醒我，我们实际上可以在洗牌时返回元素：
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's irrelevant.
int swapIndex = rng.Next(i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
}
}
这现在只会做它需要做的工作。
请注意，在这两种情况下，您都需要小心Random使用的实例：
Random大致同时创建两个实例将产生相同的随机数序列（以相同方式使用时）Random不是线程安全的。
我有一篇文章Random更详细地介绍了这些问题并提供了解决方案。
于 2009-08-17T12:02:20.597 回答
72
这是基于 Jon Skeet 的回答。
在那个答案中，数组被打乱，然后使用yield. 最终结果是数组在 foreach 的持续时间内保存在内存中，以及迭代所需的对象，但成本都在开始 - 产量基本上是一个空循环。
该算法在游戏中被大量使用，其中前三个项目被选中，其他项目仅在以后才需要。我的建议是yield一旦交换了数字。这将降低启动成本，同时将迭代成本保持在 O(1)（基本上每次迭代 5 次操作）。总成本将保持不变，但洗牌本身会更快。在调用collection.Shuffle().ToArray()它的情况下，理论上它不会产生任何影响，但在上述用例中，它将加速启动。此外，这将使该算法适用于您只需要一些独特项目的情况。例如，如果你需要从一副 52 张牌中抽出三张牌，你可以跟注deck.Shuffle().Take(3)，并且只会发生 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];
}
于 2009-11-03T03:33:17.790 回答
10
从 Skeet 的这句话开始：
这不是我喜欢的洗牌方式，主要是因为它是 O(n log n) 没有充分理由，因为它很容易实现 O(n) 洗牌。问题中的代码通过基本上给每个元素一个随机（希望是唯一的！）数字来“工作”，然后根据该数字对元素进行排序。
我将继续解释希望独特的原因！
现在，从Enumerable.OrderBy：
该方法执行稳定排序；也就是说，如果两个元素的键相等，则保留元素的顺序
这个非常重要！如果两个元素“接收”相同的随机数会发生什么？碰巧它们保持在数组中的相同顺序。现在，这种情况发生的可能性有多大？很难准确计算，但是生日问题正是这个问题。
现在，这是真的吗？这是真的吗？
与往常一样，如有疑问，请编写几行程序： http: //pastebin.com/5CDnUxPG
这个小代码块使用向后完成的Fisher-Yates算法，向前完成的Fisher-Yates算法将3个元素的数组洗牌一定次数（在wiki页面中有两个伪代码算法......它们产生等效结果，但一个是从第一个到最后一个元素完成，而另一个是从最后一个到第一个元素完成），http://blog.codinghorror.com/the-danger-of-naivete/的天真错误算法并使用.OrderBy(x => r.Next())和.OrderBy(x => r.Next(someValue)).
现在，Random.Next是
大于或等于 0 且小于 MaxValue 的 32 位有符号整数。
所以它相当于
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 个元素）的数组进行排序
于 2015-03-15T09:04:10.463 回答
6
对于大多数用途来说可能没问题，并且几乎总是会生成真正的随机分布（除非 Random.Next() 生成两个相同的随机整数）。
它的工作原理是为序列的每个元素分配一个随机整数，然后按这些整数对序列进行排序。
对于 99.9% 的应用程序来说，这是完全可以接受的（除非您绝对需要处理上述边缘情况）。此外，skeet 对其运行时的反对是有道理的，所以如果你正在改组一个长列表，你可能不想使用它。
于 2009-08-17T12:03:02.093 回答
4
这在之前已经出现过很多次了。在 StackOverflow 上搜索 Fisher-Yates。
这是我为此算法编写的C# 代码示例。如果您愿意，可以将其参数化为其他类型。
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;
}
}
}
于 2009-08-17T13:17:36.107 回答
3
如果您不太担心性能，这似乎是一个很好的洗牌算法。我要指出的唯一问题是它的行为是不可控的，所以你可能很难测试它。
一种可能的选择是将种子作为参数传递给随机数生成器（或将随机生成器作为参数），这样您就可以拥有更多的控制权并更轻松地对其进行测试。
于 2009-08-17T12:03:47.867 回答
3
寻找算法？您可以使用我的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
于 2015-11-06T11:06:41.493 回答
3
我发现 Jon Skeet 的回答完全令人满意，但我客户的机器人扫描仪会将任何实例报告Random为安全漏洞。所以我把它换成了System.Security.Cryptography.RNGCryptoServiceProvider. 作为奖励，它修复了提到的线程安全问题。另一方面，RNGCryptoServiceProvider被测量为比使用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];
}
}
于 2016-07-05T17:52:36.350 回答
1
该算法通过为列表中的每个值生成一个新的随机值，然后按这些随机值对列表进行排序来进行混洗。可以把它想象成在内存表中添加一个新列，然后用 GUID 填充它，然后按该列排序。对我来说似乎是一种有效的方法（尤其是使用 lambda 糖！）
于 2009-08-17T12:03:05.340 回答
1
有点不相关，但这里有一个有趣的方法（尽管它真的很过分，但已经真正实现了），用于真正随机生成掷骰子！
我在此处发布此内容的原因是，他提出了一些有趣的观点，说明他的用户对使用算法在实际骰子上随机播放的想法有何反应。当然，在现实世界中，这种解决方案仅适用于随机性具有如此大影响并且可能影响金钱的极端极端情况;)。
于 2009-08-17T13:30:44.147 回答
1
我会说这里的许多答案，例如“此算法通过为列表中的每个值生成一个新的随机值，然后按这些随机值对列表进行排序”来进行洗牌，这可能是非常错误的！
我认为这不会为源集合的每个元素分配随机值。取而代之的可能是运行类似 Quicksort 的排序算法，它会调用一个比较函数大约 n log n 次。某种算法真的希望这个比较函数是稳定的并且总是返回相同的结果！
难道 IEnumerableSorter 会为快速排序的每个算法步骤调用一个比较函数，并且每次都x => r.Next()为两个参数调用该函数而不缓存这些参数！
在这种情况下，您可能真的会弄乱排序算法并使其比算法所基于的期望更糟糕。当然，它最终会变得稳定并返回一些东西。
稍后我可能会通过将调试输出放在一个新的“Next”函数中来检查它，看看会发生什么。在 Reflector 中，我无法立即了解它是如何工作的。
于 2012-04-26T17:42:21.290 回答
0
值得注意的是，由于 LINQ 的延迟执行，使用随机数生成器实例可能OrderBy()会导致可能的意外行为：在读取集合之前不会发生排序。这意味着每次您阅读或枚举集合时，顺序都会更改。人们可能期望元素被洗牌一次，然后每次访问时都保持顺序。
Random random = new();
var shuffled = ordered.OrderBy(x => random.Next())
上面的代码将 lambda 函数x => random.Next()作为参数传递给OrderBy(). 这将捕获by 引用的实例random并将其与 lambda by 一起保存，以便它可以调用Next()此实例以稍后执行排序，这发生在它被枚举之前（当从集合中请求第一个元素时）。这里的问题是，由于此执行被保存以供以后使用，因此每次都Next()在使用通过调用同一随机实例获得的新数字枚举集合之前进行排序。
例子
为了演示这种行为，我使用了 Visual Studio 的 C# Interactive Shell：
> List<int> list = new() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
> Random random = new();
> var shuffled = list.OrderBy(element => random.Next());
> shuffled.ToList()
List<int>(10) { 5, 9, 10, 4, 6, 2, 8, 3, 1, 7 }
> shuffled.ToList()
List<int>(10) { 8, 2, 9, 1, 3, 6, 5, 10, 4, 7 } // Different order
> shuffled.ElementAt(0)
9 // First element is 9
> shuffled.ElementAt(0)
7 // First element is now 7
>
This behavior can even be seen in action by placing a breakpoint just after where the IOrderedEnumerable is created when using Visual Studio's debugger: each time you hover on the variable, the elements show up in a different order.
This, of course, does not apply if you immediately enumerate the elements by calling ToList() or an equivalent. However, this behavior can lead to bugs in many cases, one of them being when the shuffled collection is expected to contain a unique element at each index.
于 2021-05-12T19:40:57.553 回答
-5
在清除所有线程并缓存每个新测试的代码上运行的启动时间，
第一个不成功的代码。它在 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 推荐。）
第二次之后他们都在同一时间使用。
编辑：
Intel Core i7 4@2.1GHz、Ram 8 GB DDR3 @1600、HDD SATA 5200 rpm 上的测试代码 [数据：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()) 不比第一个解决方案中的用户定义的随机播放方法差。
答：它们是矛盾的。
于 2014-02-26T17:47:32.883 回答