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

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

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

我的第一个虽然是: 嘿,这不可能工作! 但后来我做了一些实验,发现至less似乎提供了很好的随机结果。

然后,我做了一些networkingsearch,几乎在顶部find了一个文件,从这个代码是最ceartanly复制。 看起来像一个相当可敬的网站和作者…

但我的直觉告诉我,这一定是错的。 特别是由于ECMA标准没有规定sortingalgorithm。 我认为不同的sortingalgorithm会导致不同的非均匀混洗。 一些sortingalgorithm可能甚至无限循环…

但你觉得呢?

另外还有一个问题,我现在怎么去衡量这个混洗技术的结果是多么的随意?

更新:我做了一些测量,并发布了下面的结果作为答案之一。

这从来都不是我最喜欢的洗牌方式,部分原因在于它像你说的那样特定于实现的。 特别是,我似乎记得,从Java或.NET(不知道是哪一种)的标准库sorting,如果最终得出一些元素之间不一致的比较(例如,您首先声明A < BB < C ,但是C < A )。

它也最终是一个比你真正需要的更复杂的(在执行时间上)洗牌。

我更喜欢shufflealgorithm,它有效地将收集分为“混洗”(在收集开始时,最初是空的)和“不混杂”(收集的其余部分)。 在algorithm的每一步,select一个随机的非混洗元素(可能是第一个),并与第一个非混洗元素进行交换 – 然后将其视为混洗(即精神上移动分区以包含它)。

这是O(n),只需要对随机数发生器进行n-1次调用,这很好。 它也产生真正的洗牌 – 任何元素有1 / n的机会结束在每个空间,无论其原始位置(假设一个合理的RNG)。 sorting后的版本接近于均匀分布(假设随机数生成器不会select相同的值两次,如果它返回随机双数,这是不太可能的),但我觉得更容易推理关于洗牌版本:)

这种方法被称为Fisher-Yates shuffle 。

我认为这是最好的做法,编码这个洗牌一次,并随时随地重复使用它来洗牌项目。 那么你不需要担心在可靠性或复杂性方面的sorting实现。 这只是几行代码(我不会尝试JavaScript!)

关于洗牌的维基百科文章 (特别是洗牌algorithm部分)讨论了对随机投影进行sorting的问题 – 值得一读关于糟糕的洗牌实现的部分,所以你知道该怎么回避。

在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; } 

algorithm是O(n) ,而sorting应该是O(n log n) 。 根据与本地sort()函数相比执行JS代码的开销,这可能会导致性能的显着差异,这应该随着数组大小而增加。


在对bobobobo的回答的评论中,我指出所讨论的algorithm可能不会产生均匀分布的概率(取决于sort()的实现)。

我的观点如下:sortingalgorithm需要一定数量的比较,例如Bubblesort的c = n(n-1)/2 。 我们的随机比较函数使得每个比较的结果具有相同的可能性,即有2^c 相等的可能结果。 现在,每个结果都必须对应一个n! 数组条目的排列,这在一般情况下是不可能均匀分布的。 (这是一个简化,因为需要比较的实际数量取决于input数组,但断言仍应该保持。)

正如Jon指出的那样,单独使用sort()就没有理由selectFisher-Yates,因为随机数生成器也会将有限数量的伪随机值映射到n! 排列。 但是Fisher-Yates的结果应该还是比较好的:

Math.random()产生范围[0;1[的伪随机数。 由于JS使用双精度浮点值,这对应于2^x可能的值,其中52 ≤ x ≤ 63 (我懒得find实际的数字)。 如果primefaces事件的数量是相同的数量级,使用Math.random()生成的概率分布将停止行为。

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

当使用随机比较函数进行sorting时,函数基本上只关心返回值是正数还是负数,所以这不会成为问题。 但也有一个类似的结论:由于比较函数的性能良好,所以2^c可能的结果如上所述是相同的。 如果c ~ n log n那么2^c ~ n^(a·n)其中a = const ,这使得至less有可能2^c的大小与(或者甚至小于) n!相等n! 从而导致分布不均匀,即使将sortingalgorithm均匀地映射到置换上。 如果这有什么实际影响超出我的话。

真正的问题是sortingalgorithm不能保证均匀映射到排列上。 很容易看出Mergesort是对称的,但推理像Bubblesort,更重要的是,Quicksort或Heapsort不是。


底线:只要sort()使用Mergesort,除了在angular落的情况下(至less我希望2^c ≤ n!是一个angular落的情况),你应该是合理安全的,如果不是,所有的投注都closures。

我做了一些随机sorting结果的随机测量。

我的技术是采取一个小数组[1,2,3,4],并创build它的所有(4!= 24)排列。 然后我将这个混洗函数应用到数组中,并计算每个排列产生的次数。 一个好的洗牌algorithm会将结果相当均匀地分布在所有的排列上,而坏的algorithm则不会产生统一的结果。

使用下面的代码我在Firefox,Opera,Chrome,IE6 / 7/8testing。

令我惊奇的是,随机sorting和真正的洗牌都创造了同样均匀的分布。 所以似乎(如许多人所build议的),主要的浏览器正在使用合并sorting。 这当然不意味着在那里不能有一个浏览器,这样做是不一样的,但我想这意味着,这种随机sorting方法在实践中足够可靠。

编辑:这个testing没有真正测量正确的随机性或缺乏。 看到我张贴的其他答案。

但在性能方面,克里斯托弗给出的洗牌function是明显的赢家。 即使对于小型四元素arrays,真正的洗牌也是随机sorting的两倍!

 // Cristoph发布的shuffle函数
 var shuffle = function(array){
     var tmp,current,top = array.length;

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

    返回数组;
 };

 //随机sortingfunction
 var rnd = function(){
  返回Math.round(Math.random()) -  0.5;
 };
 var randSort = function(A){
  返回A.sort(rnd);
 };

 var permutations = function(A){
  如果(A.length == 1){
    返回[A];
   }
   else {
     var perms = [];
     for(var i = 0; i <A.length; i ++){
       var x = A.slice(i,i + 1);
       var xs = A.slice(0,i).concat(A.slice(i + 1));
       var subperms = permutations(xs);
       for(var j = 0; j <subperms.length; j ++){
         perms.push(x.concat(subperms [J]));
       }
     }
    返回烫发;
   }
 };

 var test = function(A,iterations,func){
   //初始化排列
   var stats = {};
   var perms =排列(A);
   for(var i perms){
     stats [“”+ perms [i]] = 0;
   }

   //洗牌多次并收集统计信息
   var start = new Date();
   for(var i = 0; i <iterations; i ++){
     var shuffled = func(A);
    统计[ “” +改组] ++;
   }
   var end = new Date();

   //格式结果
   var arr = [];
   for(var i in stats){
     arr.push(i +“”+ stats [i]);
   }
  返回arr.join(“\ n”)+“\ n \ nlogging时间:”+((结束 - 开始)/ 1000)+“秒”。
 };

 alert(“random sort:”+ test([1,2,3,4],100000,randSort));
 alert(“shuffle:”+ test([1,2,3,4],100000,shuffle));

有趣的是, 微软在pick-random-browser-page中使用了相同的技术

他们使用了稍微不同的比较function:

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

看起来几乎和我一样,但结果并不是那么随意的…

所以我再次用相同的方法做了一些testruns,事实上 – 这个随机sorting方法的结果是错误的。 新的testing代码在这里:

 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")); 

我在我的网站上放置了一个简单的testing页面 ,显示了当前浏览器与使用不同方法混洗的其他stream行浏览器之间的偏见。 它显示了使用Math.random()-0.5 ,另一个没有偏见的“随机”混洗以及上面提到的Fisher-Yates方法的糟糕的偏见。

你可以看到,在一些浏览器上,在“洗牌”过程中,某些元素根本不会改变的可能性高达50%。

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

 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; } 

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

我认为对于分发不够挑剔的情况并且希望源代码很小的情况就可以。

在JavaScript(源代码不断传输)中,小带宽成本是有差别的。

当然,这是一个黑客。 实际上,无限循环algorithm是不可能的。 如果你正在sorting对象,你可以循环访问coords数组,并执行如下操作:

 for (var i = 0; i < coords.length; i++) coords[i].sortValue = Math.random(); coords.sort(useSortValue) function useSortValue(a, b) { return a.sortValue - b.sortValue; } 

(然后再次遍历它们以移除sortValue)

还是一个黑客。 如果你想做得很好,你必须这样做:)

如果您使用D3,则有一个内置的洗牌function(使用Fisher-Yates):

 var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche']; d3.shuffle(days); 

这里是迈克详细介绍它:

http://bost.ocks.org/mike/shuffle/

已经四年了,但是我想指出的是,无论使用什么sortingalgorithm,这可能都不会起作用。

certificate:有n! n个元素的排列。 每次你做一个比较,你都是在这组排列的两个子集之间进行select。 所以每个置换的概率都是分数,对于某个k,分母2 ^ k。

对于n = 3,有六个同样可能的排列。 那么每个排列的机会是1/6。 1/6不能表示为2的幂作为分母。 尝试用不同的方式绘制决策树。

唯一可能正确分布的大小是n = 0,1,2。

这是一个使用单个数组的方法:

基本的逻辑是:

  • 从n个元素的数组开始
  • 从数组中删除一个随机元素,并将其推到数组上
  • 从数组的前n-1个元素中移除一个随机元素,并将其推送到数组上
  • 从数组的前n – 2个元素中移除一个随机元素,并将其推到数组上
  • 删除数组的第一个元素,并将其推到数组上
  • 码:

     for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]); 

    你可以使用Array.sort()函数来洗牌数组 – 是的。

    结果足够随机 – 可能不是。 我用这个JavaScript进行testing:

     var array = ["a", "b", "c", "d", "e"]; var stats = {}; for (var i = 0; i < array.length; i++) { stats[array[i]] = []; for (var j = 0; j < array.length; j++) { stats[array[i]][j] = 0; } } //stats = { // a: [0, 0, 0, ...] // b: [0, 0, 0, ...] // c: [0, 0, 0, ...] // ... // ... //} for (var i = 0; i < 100; i++) { var clone = array.slice(0); clone.sort(function() { return Math.random() - 0.5; }); for (var j = 0; j < clone.length; j++) { stats[clone[j]][j]++; } } for (var i in stats) { console.log(i, stats[i]); } 

    示例输出:

     a [29, 38, 20, 6, 7] b [29, 33, 22, 11, 5] c [17, 14, 32, 17, 20] d [16, 9, 17, 35, 23] e [ 9, 6, 9, 31, 45] 

    理想情况下,计数应该均匀分布(对于上面的例子,所有计数应该在20左右)。 但他们不是。 显然,分布依赖于浏览器实现的sortingalgorithm,以及它如何迭代数组项以进行sorting。

    本文提供了更多的见解:
    Array.sort()不应该用来洗牌数组

    Addi Osmani实施了这个版本的Fisher-Yates shuffle :

     function shuffle(array) { var rand, index = -1, length = array.length, result = Array(length); while (++index < length) { rand = Math.floor(Math.random() * (index + 1)); result[index] = result[rand]; result[rand] = array[index]; } return result; } 

    对于那些回头看看这个,这里是certificatesort()不工作随机: http : //phrogz.net/JS/JavaScript_Random_Array_Sort.html

    没有什么问题。

    传递给.sort()的函数通常看起来像这样

    函数sortingFunc(第一,第二)
     {
       //示例:
      返回一秒钟;
     }
    

    您在sortingFunc中的工作是返回:

    • 一个负数,如果第一个在第二个之前
    • 如果第一个应该是第二个是正数
    • 如果它们完全相等则为0

    上面的sortingfunction是按顺序排列的。

    如果你随机地返回“+”和“+”,你会得到一个随机的sorting。

    像在MySQL中一样:

     SELECT * from table ORDER BY rand()