这种改组算法的效率和质量如何？

Question

最近关于使用C#随机排序的这个问题让我想到了我有时在Perl中改组数组的方式.

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

在上述问题中提出的解决方案是Fisher-Yates shuffle,它在线性时间内工作.

问题是:我的代码片段效率如何,并且是如此随机"真正"随机？

Answer 1

我不是Perl的内部专家,所以我不知道"sort"在这里是如何工作的.但是,大多数排序函数都希望它们的比较具有一致性,如果函数本身是随机的,我希望它们能够无法预测地工作.不幸的是,不可预测性与随机性不一样,所以我对你的洗牌阵列没有信心.它可能倾向于以某种顺序放置元素,就像匆忙创建和复杂的递归关系可能不是随机的一样.

而不是分析排序函数,我建议与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

我实际上有点惊讶你提议的洗牌工作.在Perl sort函数的实现中,它尝试根据比较函数的值以升序获取数组的元素.问题是,你的比较函数没有返回一致的答案!有时它可能会说"foo" lt "bar",而有时可能会说"bar" lt "foo".这有可能将排序算法混淆到它永远不会终止的地步,或者以致命错误或其他一些灾难性故障终止.