List<T>的随机排序

Question

可能是重复问题：
如何在C#中对List<T>进行随机化？

我的列表中包含很多FilePath，指向音频文件的位置，我想知道最有效的“洗牌”List的方法是什么？

非常感谢任何帮助 :)

谢谢

- anon271334

---

请查看此帖子： https://dev59.com/EnVC5IYBdhLWcg3wfxU8 - dugas

你是真的想要“最有效率的解决方案”还是想要一个“可接受的高效解决方案”？因为有一些算法比Fischer-Yates更有效率，只要你愿意放弃某些好的特性，比如缺乏偏见。（并不是说下面实现的Fischer-Yates是无偏的；它是非常有偏的。） - Eric Lippert

@Eric：我追求的是最高效的解决方案，尽管一个可接受的高效解决方案也不错。目前，我的一个用户在他们8年前的电脑上拥有50万个音频文件库。如果有这样的用户，那么很可能还有更多类似的用户，我希望事情能够尽可能快速。 - anon271334

我将通过解决一个不同的问题来解决你的问题。为什么你必须要生成50万个文件的乱序呢？即使用户整天每天都按“下一个”按钮，几个月也无法到达乱序列表的最后一个文件。也就是说，为什么要完全预先计算所有乱序的顺序呢？随机选择几百个（无需替换）就可以了。这不仅更快，而且比分配一个包含五十万个文件名并对整个数组进行洗牌的方式更加内存高效。 - Eric Lippert

@j-t-s：同意Eric的观点：在处理如此巨大的文件之前尝试洗牌似乎是毫无意义的（而且非常低效）。这里有一个不同于Eric的建议：您可以尝试保留最近播放的10个（或50个）文件的列表。对于下一个文件，您可以生成一个随机数/文件（从1到1/2百万），如果它在最近播放的10个（或50个）中，则尝试再次获取随机数。这应该足以满足所有实际需求。 - Aryabhatta

Answer 1

费舍尔-耶茨洗牌算法，也被称为 Knuth 洗牌算法。

- Aryabhatta

---

这是O(n)的，所以你无法得到比这更好的结果。 - Guffa

我刚刚点赞了你的回答，因为我喜欢它 :) 不知道为什么会被踩？ - anon271334

顺便说一句，为了更快地洗牌，我建议您随意选择一种方法，对整数列表/数组进行洗牌，并使用洗牌后的列表/数组作为索引，然后将其用于文件名列表。交换文件名可能会成为瓶颈。 - Aryabhatta

Answer 2

这是一个简单（但有效）的Fischer-Yates / Knuth洗牌算法实现示例：

Random rnd = new Random();
for (int i = files.Length; i > 1; i--) {
  int pos = rnd.Next(i);
  var x = files[i - 1];
  files[i - 1] = files[pos];
  files[pos] = x;
}

或者稍作变化：

Random rnd = new Random();
for (int i = 1; i < files.Length; i++) {
  int pos = rnd.Next(i + 1);
  var x = files[i];
  files[i] = files[pos];
  files[pos] = x;
}

由于这是O(n)操作，这是最有效的洗牌列表的方法。由于列表中的所有项目都必须有机会被移动，因此不能比O(n)更有效地洗牌列表。

我使用这种方法洗牌一百万个项目，每个项目都进行了一千次，与当前接受的答案（LINQ OrderBy）相比，效率提高了约15倍。

- Guffa

---

我还注意到你的Fischer-Yates实现有偏差；它不能以相等的概率产生所有可能的洗牌。对于音乐随机播放算法来说，这可能不是问题，但如果你想用它来洗扑克牌玩游戏，那就是个问题了；根据我的手牌，我可以很快地确定其他人手中的牌。 - Eric Lippert

@Eric：你为什么认为这个实现有偏差？它给每个项目在列表中以相同的机会出现在每个位置。此外，我通过进行数百万次洗牌来验证了该实现，并且没有明显的偏差。 - Guffa

设x为Random产生的可能随机顺序数量，y为洗牌的可能排序数量。我认为如果你计算出x和y的值，你会发现在你的实现中，x远远小于y，因此洗牌是有偏差的。 - Eric Lippert

@Eric：对于一个n项列表，x = n！而y = n！因此我不明白x怎么可能比y小得多。 - Guffa

@Guffa：抱歉我误读了Eric的评论。我想说的是这不是Fischer Yates算法。至于偏差问题：就你实现的方式而言，我们可以“证明”如果随机生成器是均匀的，那么你产生的洗牌结果是均匀的（或者“无偏”的）。对于造成的困惑，我感到很抱歉。 - Aryabhatta

Answer 3

myList.OrderBy(Guid.NewGuid())

- Esteban Araya

---

一些GUID生成算法会生成单调值，因此可能不会产生随机结果。但是，使用另一个随机源（可能是随机的）进行类似操作将起作用。 - heneryville

Answer 4

我将Jon Skeet在这个问题中提供的解决方案添加到我的扩展库中。我实现了两种方法，一种是使用外部随机数生成器，另一种是使用默认实现（Random）创建一个随机数生成器。

- tvanfosson