微信号:FrontDev

介绍:分享 Web 前端相关的技术文章、工具资源、精选课程、热点资讯

也谈前端面试常见问题之「数组乱序」

2016-07-13 23:47 伯乐专栏\/韩子迟

(点击上方公众号,可快速关注)

作者:伯乐在线专栏作者 - 韩子迟

链接:http://web.jobbole.com/86552/

点击 → 了解如何加入专栏作者


前言


终于可以开始 Collection Functions 部分了。


可能有的童鞋是第一次看楼主的系列文章,这里再做下简单的介绍。楼主在阅读 underscore.js 源码的时候,学到了很多,同时觉得有些知识点可以独立出来,写成文章与大家分享,而本文正是其中之一(完整的系列请猛戳 https://github.com/hanzichi/underscore-analysis)。之前楼主已经和大家分享了 Object 和 Array 的扩展方法中一些有意思的知识点,今天开始解读 Collection 部分。


看完 Collection Functions 部分的源码,首先迫不及待想跟大家分享的正是本文主题 —— 数组乱序。这是一道经典的前端面试题,给你一个数组,将其打乱,返回新的数组,即为数组乱序,也称为洗牌问题。


一个好的方案需要具备两个条件,一是正确性,毋庸置疑,这是必须的,二是高效性,在确保正确的前提下,如何将复杂度降到最小,是我们需要思考的。


splice


几年前楼主还真碰到过洗牌问题,还真的是 “洗牌”。当时是用 cocos2d-js(那时还叫 cocos2d-html5)做牌类游戏,发牌前毫无疑问需要洗牌。


当时我是这样做的。每次 random 一个下标,看看这个元素有没有被选过,如果被选过了,继续 random,如果没有,将其标记,然后存入返回数组,直到所有元素都被标记了。后来经同事指导,每次选中后,可以直接从数组中删除,无需标记了,于是得到下面的代码。


function shuffle(a) {

  var b = [];

 

  while (a.length) {

    var index = ~~(Math.random() * a.length);

    b.push(a[index]);

    a.splice(index, 1);

  }

 

  return b;

}


这个解法的正确性应该是没有问题的(有兴趣的可以自己去证明下)。我们假设数组的元素为 0 – 10,对其乱序 N 次,那么每个位置上的结果加起来的平均值理论上应该接近 (0 + 10) / 2 = 5,且 N 越大,越接近 5。为了能有个直观的视觉感受,我们假设乱序 1w 次,并且将结果做成了图表,猛戳 http://hanzichi.github.io/test-case/shuffle/splice/ 查看,结果还是很乐观的。


验证了正确性,还要关心一下它的复杂度。由于程序中用了 splice,如果把 splice 的复杂度看成是 O(n),那么整个程序的复杂度是 O(n^2)。


Math.random()


另一个为人津津乐道的方法是 “巧妙应用” JavaScript 中的 Math.random() 函数。


function shuffle(a) {

  return a.concat().sort(function(a, b) {

    return Math.random() - 0.5;

  });

}


同样是 [0, 1, 2 … 10] 作为初始值,同样跑了 1w 组 case,结果请猛戳 http://hanzichi.github.io/test-case/shuffle/Math.random/。


看平均值的图表,很明显可以看到曲线浮动,而且多次刷新,折现的大致走向一致,平均值更是在 5 上下 0.4 的区间浮动。如果我们将 [0, 1, 2 .. 9] 作为初始数组,可以看到更加明显不符预期的结果(有兴趣的可以自己去试下)。究其原因,要追究 JavaScript 引擎对于 Math.random() 的实现原理,这里就不展开了(其实是我也不知道)。因为 ECMAScript 并没有规定 JavaScript 引擎对于 Math.random() 应该实现的方式,所以我猜想不同浏览器经过这样的乱序后,结果也不一样。


什么时候可以用这种方法乱序呢?”非正式” 场合,一些手写 DEMO 需要乱序的场合,这不失为一种 clever solution。


但是这种解法不但不正确,而且 sort 的复杂度,平均下来应该是 O(nlogn),跟我们接下来要说的正解还是有不少差距的。


Fisher–Yates Shuffle


关于数组乱序,正确的解法应该是 Fisher–Yates Shuffle,复杂度 O(n)。


其实它的思想非常的简单,遍历数组元素,将其与之前的任意元素交换。因为遍历有从前向后和从后往前两种方式,所以该算法大致也有两个版本的实现。


从后往前的版本:


function shuffle(array) {

  var _array = array.concat();

 

  for (var i = _array.length; i--; ) {

    var j = Math.floor(Math.random() * (i + 1));

    var temp = _array[i];

    _array[i] = _array[j];

    _array[j] = temp;

  }

  

  return _array;

}


underscore 中采用从前往后遍历元素的方式,实现如下:


// Shuffle a collection, using the modern version of the

// [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle).

_.shuffle = function(obj) {

  var set = isArrayLike(obj) ? obj : _.values(obj);

  var length = set.length;

  var shuffled = Array(length);

  for (var index = 0, rand; index < length; index++) {

    rand = _.random(0, index);

    if (rand !== index) shuffled[index] = shuffled[rand];

    shuffled[rand] = set[index];

  }

  return shuffled;

};


将其解耦分离出来,如下:


function shuffle(a) {

  var length = a.length;

  var shuffled = Array(length);

 

  for (var index = 0, rand; index < length; index++) {

    rand = ~~(Math.random() * (index + 1));

    if (rand !== index)

      shuffled[index] = shuffled[rand];

    shuffled[rand] = a[index];

  }

 

  return shuffled;

}


跟前面一样,做了下数据图表,猛戳 http://hanzichi.github.io/test-case/shuffle/Fisher-Yates/。


关于证明,引用自月影老师的文章(https://www.h5jun.com/post/array-shuffle.html):


随机性的数学归纳法证明


对 n 个数进行随机:


  1. 首先我们考虑 n = 2 的情况,根据算法,显然有 1/2 的概率两个数交换,有 1/2 的概率两个数不交换,因此对 n = 2 的情况,元素出现在每个位置的概率都是 1/2,满足随机性要求。

  2. 假设有 i 个数, i >= 2 时,算法随机性符合要求,即每个数出现在 i 个位置上每个位置的概率都是 1/i。

  3. 对于 i + 1 个数,按照我们的算法,在第一次循环时,每个数都有 1/(i+1) 的概率被交换到最末尾,所以每个元素出现在最末一位的概率都是 1/(i+1) 。而每个数也都有 i/(i+1) 的概率不被交换到最末尾,如果不被交换,从第二次循环开始还原成 i 个数随机,根据 2. 的假设,它们出现在 i 个位置的概率是 1/i。因此每个数出现在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1),也是 1/(i+1)。

  4. 综合 1. 2. 3. 得出,对于任意 n >= 2,经过这个算法,每个元素出现在 n 个位置任意一个位置的概率都是 1/n。


小结


关于数组乱序,如果面试中被问到,能说出 “Fisher–Yates Shuffle”,并且能基本说出原理(你也看到了,其实代码非常的简单),那么基本应该没有问题了;如果能更进一步,将其证明呈上(甚至一些面试官都可能一时证明不了),那么就牛逼了。千万不能只会用 Math.random() 投机取巧!


专栏作者简介 ( 点击 → 加入专栏作者 


韩子迟:a JavaScript beginner

打赏支持作者写出更多好文章,谢谢!



【今日微信公号推荐↓】

更多推荐请看值得关注的技术和设计公众号


其中推荐了包括技术设计极客 和 IT相亲相关的热门公众号。技术涵盖:Python、Web前端、Java、安卓、iOS、PHP、C/C++、.NET、Linux、数据库、运维、大数据、算法、IT职场等。点击《值得关注的技术和设计公众号》,发现精彩!


 
前端大全 更多文章 用 JavaScript 构建一个3D引擎 浅谈浏览器http的缓存机制 Web开发的发展史 Web开发技术的演变 抛弃臃肿的 jQuery,用 NodeList.js 操作 DOM
猜您喜欢 剑指酒店业的红利猎人,封杀不了的江湖传说 博赛网络暑假班即将开课 接待工作全面启动 Hadoop启动报Error: JAVA_HOME is not set and could not be found解决办法 双十一来了!阿里巴巴送你两万六千条短信——我们一起共享阿里大数据 深度剖析:摩尔定律何去何从(完整版)