使用JavaScript Array.sort()方法进行混洗是否正确？

我用他的JavaScript代码帮助了一个人,我的眼睛被一个看起来像这样的部分抓住了:

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

我的第一个是:嘿,这不可能奏效!但后来我做了一些实验,发现它确实至少似乎提供了很好的随机结果.

然后我做了一些网络搜索,几乎在顶部发现了一篇文章,这段代码最简单地被复制.看起来像一个相当可敬的网站和作者......

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

但你怎么看？

而另一个问题是......现在我将如何衡量这种改组技术的结果是多么随机？

更新:我做了一些测量并将结果发布在下面作为答案之一.

1> Christoph..：

---

在Jon已经涵盖理论之后,这是一个实现:

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

该算法是O(n),而排序应该是O(n log n).根据执行JS代码与本机sort()函数相比的开销,这可能会导致性能的显着差异,这应该随阵列大小而增加.

---

在对bobobobo的回答的评论中,我说有问题的算法可能不会产生均匀分布的概率(取决于实现sort()).

我的论点是这样的:排序算法需要一定数量c的比较,例如c = n(n-1)/2Bubblesort.我们的随机比较函数使得每次比较的结果同样可能,即2^c 同样可能的结果.现在,每个结果必须对应于n!数组条目的一个排列,这使得在一般情况下均匀分布是不可能的.(这是一种简化,因为所需的实际比较数取决于输入数组,但断言应该仍然有效.)

正如乔恩指出的那样,仅凭这一点就没有理由更喜欢Fisher-Yates使用sort(),因为随机数生成器也会将有限数量的伪随机值映射到n!排列.但Fisher-Yates的结果应该更好:

Math.random()在该范围内产生一个伪随机数[0;1[.由于JS使用双精度浮点值,这对应于2^x可能的值52 ? x ? 63(我懒得找实际数字).Math.random()如果原子事件的数量具有相同的数量级,则使用生成的概率分布将停止表现良好.

当使用Fisher-Yates时,相关参数是阵列的大小,2^52由于实际限制,它不应该接近.

使用随机比较函数进行排序时,该函数基本上只关心返回值是正还是负,所以这永远不会成为问题.但是有一个类似的:因为比较函数表现良好,如上所述,2^c可能的结果同样可能.如果c ~ n log n然后2^c ~ n^(a·n)在那里a = const,这使得它的至少可能的2^c是相同的大小作为(或甚至小于)n!和因此导致的不均匀分布,即使排序算法何处映射到permutaions均匀.如果这有任何实际影响超出我.

真正的问题是不能保证排序算法均匀地映射到排列上.很容易看出Mergesort的确是对称的,但是像Bubblesort或更重要的是Quicksort或Heapsort这样的推理并不是.

---

底线:只要sort()使用Mergesort,你应该合理安全,除非在角落的情况下(至少我希望这2^c ? n!是一个角落的情况),如果没有,所有的赌注都关闭.

2> Jon Skeet..：

---

它从来都不是我最喜欢的洗牌方式,部分原因是因为它是特定于实现的.特别是,我记得好象标准库无论从Java或.NET(不知道这)如果你结束了一些元素(例如,你首先要求之间的矛盾比较可以经常检测分选A < B和B < C,但后来C < A).

它最终会比你真正需要的更复杂(在执行时间方面)洗牌.

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

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

这种方法称为Fisher-Yates shuffle.

我认为最好的做法是对这个洗牌进行一次编码,然后在需要随机播放项目的任何地方重复使用它.然后,您无需担心可靠性或复杂性方面的排序实现.它只有几行代码(我不会在JavaScript中尝试!)

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

---

Raymond Chen深入探讨了排序比较函数遵循规则的重要性:http://blogs.msdn.com/oldnewthing/archive/2009/05/08/9595334.aspx

---

Fisher-Yates洗牌？

3> Rene Saarsoo..：

---

我做了一些关于随机排序结果随机性的测量结果......

我的技术是采用一个小数组[1,2,3,4]并创建它的所有(4!= 24)排列.然后,我会将洗牌函数多次应用于数组,并计算每个排列生成的次数.一个好的改组算法会在所有排列上非常均匀地分配结果,而一个糟糕的算法不会产生统一的结果.

使用下面的代码我在Firefox,Opera,Chrome,IE6/7/8中进行了测试.

令我惊讶的是,随机排序和真正的随机排序都创造了同样均匀的分布.所以似乎(正如许多人所建议的)主浏览器正在使用合并排序.这当然并不意味着,那里不会有浏览器,这有不同的,但我想说这意味着,这种随机排序方法足够可靠,可以在实践中使用.

编辑:这个测试没有真正正确地测量随机性或缺乏.看到我发布的其他答案.

但在表演方面,Cristoph给出的随机播放功能是一个明显的赢家.即使对于小型四元素阵列,真正的shuffle执行速度也是随机排序的两倍!

// The shuffle function posted by Cristoph.
var shuffle = function(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
};

// the random sort function
var rnd = function() {
  return Math.round(Math.random())-0.5;
};
var randSort = function(A) {
  return A.sort(rnd);
};

var permutations = function(A) {
  if (A.length == 1) {
    return [A];
  }
  else {
    var perms = [];
    for (var i=0; i

        
+1用于基准而不是主观争论. 

4> Rene Saarsoo..：
有趣的是,微软在他们的随机浏览器页面中使用了相同的技术.

他们使用了略微不同的比较功能:

function RandomSort(a,b) {
    return (0.5 - Math.random());
}


看起来和我几乎一样,但结果却不是那么随意......

因此,我使用链接文章中使用的相同方法再次进行了一些测试,事实证明 - 随机排序方法产生了有缺陷的结果.这里有新的测试代码:

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));

        

5> Phrogz..：
我在我的网站上放置了一个简单的测试页面,显示当前浏览器与使用不同方法进行混洗的其他流行浏览器的偏差.它显示了刚刚使用的可怕偏见Math.random()-0.5,另一个没有偏差的"随机"shuffle,以及上面提到的Fisher-Yates方法.

你可以看到,在某些浏览器中,在'shuffle'期间,某些元素根本不会改变位置的可能性高达50%!

注意:通过将代码更改为以下内容,您可以通过@Christoph实现Fisher-Yates shuffle稍微快一点的Safari:

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}


测试结果:http://jsperf.com/optimized-fisher-yates

        

6> Nosredna..：
我认为这对你不喜欢发行并且希望源代码很小的情况很好.

在JavaScript(源不断传输)中,small会对带宽成本产生影响.