使用JavaScript Array.sort（）方法进行混洗是否正确？ [英] Is it correct to use JavaScript Array.sort() method for shuffling?

问题描述

我正在用他的JavaScript代码帮助某人，我的眼睛被一个看起来像这样的部分抓住了：

I was helping somebody out with his JavaScript code and my eyes were caught by a section that looked like that:

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

我的第一个是：嘿，这不可行！但后来我做了一些实验，发现它确实至少提供了很好的随机结果。

My first though was: hey, this can't possibly work! But then I did some experimenting and found that it indeed at least seems to provide nicely randomized results.

然后我做了一些网络搜索，几乎在顶部找到了文章，此代码最容易被复制。看起来像一个相当可敬的网站和作者...

Then I did some web search and almost at the top found an article from which this code was most ceartanly copied. Looked like a pretty respectable site and author...

但我的直觉告诉我，这一定是错的。特别是因为ECMA标准没有规定排序算法。我认为不同的排序算法会导致不同的非均匀混洗。有些排序算法甚至可能无限循环......

But my gut feeling tells me, that this must be wrong. Especially as the sorting algorithm is not specified by ECMA standard. I think different sorting algoritms will result in different non-uniform shuffles. Some sorting algorithms may probably even loop infinitely...

但您怎么看？

另一种问题...我现在怎么去测量这种改组技术的结果是多么随机？

And as another question... how would I now go and measure how random the results of this shuffling technique are?

更新：我做了一些测量，将结果公布在下面作为答案之一。

update: I did some measurements and posted the results below as one of the answers.

推荐答案

它从来都不是我最喜欢的洗牌方式，部分原因是因为它正如你所说，特定于实现。特别是，我似乎记得从Java或.NET（不确定哪个）排序的标准库经常可以检测到你是否最终在一些元素之间进行了不一致的比较（例如，你首先要求 A< ; B 和 B< C ，但是 C< A ）。

It's never been my favourite way of shuffling, partly because it is implementation-specific as you say. In particular, I seem to remember that the standard library sorting from either Java or .NET (not sure which) can often detect if you end up with an inconsistent comparison between some elements (e.g. you first claim A < B and B < C, but then C < A).

它最终会比你真正需要的更复杂（就执行时间而言）洗牌。

It also ends up as a more complex (in terms of execution time) shuffle than you really need.

我更喜欢shuffle算法，它有效地将集合划分为shuffled（在集合的开头，最初为空）和unshuffled（集合的其余部分）。在算法的每一步，选择一个随机的非抽动元素（可能是第一个）并将其与第一个未抽褶的元素交换 - 然后将其视为混洗（即精神上移动分区以包含它）。

I prefer the shuffle algorithm which effectively partitions the collection into "shuffled" (at the start of the collection, initially empty) and "unshuffled" (the rest of the collection). At each step of the algorithm, pick a random unshuffled element (which could be the first one) and swap it with the first unshuffled element - then treat it as shuffled (i.e. mentally move the partition to include it).

这是O（n），只需要对随机数生成器进行n-1次调用，这很好。它还会产生真正的随机播放 - 任何元素都有1 / n的机会在每个空间中结束，无论其原始位置如何（假设合理的RNG）。排序版本近似到均匀分布（假设随机数生成器不会选择相同的值两次，如果它返回随机双精度则不太可能），但我发现更容易推理shuffle版本：）

This is O(n) and only requires n-1 calls to the random number generator, which is nice. It also produces a genuine shuffle - any element has a 1/n chance of ending up in each space, regardless of its original position (assuming a reasonable RNG). The sorted version approximates to an even distribution (assuming that the random number generator doesn't pick the same value twice, which is highly unlikely if it's returning random doubles) but I find it easier to reason about the shuffle version :)

这种方法称为 Fisher-Yates洗牌。

我认为最好的做法是对这次洗牌进行一次编码，然后在需要随意洗牌的地方重复使用。然后，您无需担心可靠性或复杂性方面的排序实现。它只有几行代码（我不会在JavaScript中尝试！）

I would regard it as best practice to code up this shuffle once and reuse it everywhere you need to shuffle items. Then you don't need to worry about sort implementations in terms of reliability or complexity. It's only a few lines of code (which I won't attempt in JavaScript!)

关于改组的维基百科文章（特别是洗牌算法部分）讨论了对随机投影进行排序的问题 - 值得一读的关于洗牌的不良实现的部分，所以你知道该避免什么。

The Wikipedia article on shuffling (and in particular the shuffle algorithms section) talks about sorting a random projection - it's worth reading the section on poor implementations of shuffling in general, so you know what to avoid.

这篇关于使用JavaScript Array.sort（）方法进行混洗是否正确？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！