使用 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 ).

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).

它也最终成为比您真正需要的更复杂的(在执行时间方面)shuffle.

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 合理).排序版本近似为均匀分布(假设随机数生成器不会两次选择相同的值，如果它返回随机双精度则不太可能)但我发现更容易推理随机版本:)

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 shuffle.

我认为最好的做法是对这种 shuffle 进行一次编码，然后在需要对项目进行 shuffle 的任何地方重用它.然后您无需担心排序实现的可靠性或复杂性.只有几行代码(我不会在 JavaScript 中尝试！)

I would regard it as a 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屋！