perl - 这种洗牌算法的效率和质量如何？

Question

最近这个关于使用 C# 随机排序的问题让我想到了我有时在 Perl 中对数组进行洗牌的方式。

@shuffled = sort { rand() <=> rand() } @array;

上述问题中建议的解决方案是Fisher-Yates shuffle，它在线性时间内工作。

问题是：我的片段效率如何，这种随机播放“真的”是随机的吗？

Answer 1

我不是 Perl 内部专家，所以我不知道“排序”在这里如何工作。但是，大多数排序函数都希望它们的比较具有一致性，如果函数本身是随机的，我希望它们会以不可预测的方式工作。不幸的是，不可预测性与随机性不同，所以我对你的洗牌数组没有信心。它可能倾向于将元素按某种顺序排列，就像仓促创建的复杂递归关系可能不是随机的一样。

我建议不要分析排序函数，而是使用 Fisher-Yates。

正如 Knuth 所说，随机性太重要了，不能靠运气。

Answer 2

$ perldoc List::Util
⋮
  shuffle LIST
       Returns the elements of LIST in a random order

           @cards = shuffle 0..51      # 0..51 in a random order
⋮

那将是我的建议。

Answer 3

我实际上有点惊讶你提出的洗牌工作。在 Perlsort函数的实现中，它尝试根据比较函数的值将数组的元素按升序排列。问题是，您的比较函数不会返回一致的答案！有时它可能会说"foo" lt "bar"，而其他时候它可能会说"bar" lt "foo"。这有可能将排序算法混淆到它永远不会终止，或者以致命错误或其他一些灾难性故障而终止的程度。

Answer 4

perl 文档说明了sort这一点

比较功能需要表现。如果它返回不一致的结果（例如，有时说 $x[1] 小于 $x[2]，有时说相反），则结果定义不明确。

所以这样做是个坏主意。

ETA：我刚刚做了一个基准测试。在 100000 个元素的数组上，使用 FY-shuffle 也快 10 倍以上。

Answer 5

一方面，您知道无论您使用什么比较器，sort() 都不可能比 O(n log n) 快。因此，即使它执行的 shuffle 是公平的，它的性能也会更差。

那么洗牌公平吗？对于某些（易于分析的）排序算法来说，这显然是不公平的。考虑一个简单的冒泡排序——为了让一个元素从一端移动到另一端，比较函数必须对 n 次连续调用评估为正值——对于应该是 n 中的 1 事件的概率为 2^n 中的 1。对于快速排序，很难分析，并且最终可能是公平的。但如果它是正确的很重要，那就以正确的方式去做。

Answer 6

这只是直觉，但我认为使用这样的排序会产生一个集合，其顺序在某种程度上取决于原始集合的顺序。真正随机排序的结果根本不应该依赖于原始集合的顺序。我无法解释为什么/如何，也许其他人可以（或表明它实际上是随机的）？

至于它的效率如何，我不确定，但它可能不会比任何其他使用 AFAIK 的效率低很多sort，因为 AFAIKrand()相对便宜。不过，我可能错了。

Answer 7

有一个更好的 Fisher-Yates shuffle 函数，它不使用perlfaq4sort中的内置函数：How do I shuffle an array random? .

Answer 8

@shuffled = map {
  $_->[1]
} sort {
  $a->[0] <=> $b->[0]
} map {
  [ rand(), $_ ]
} @array;