New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JavaScript 数组乱序 #15

Open
hanzichi opened this Issue Jul 4, 2016 · 13 comments

Comments

Projects
None yet
7 participants
@hanzichi
Copy link
Owner

hanzichi commented Jul 4, 2016

前言

终于可以开始 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/

关于证明,引用自月影老师的文章

随机性的数学归纳法证明

对 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() 投机取巧!

Read More:

@hanzichi

This comment has been minimized.

Copy link
Owner Author

hanzichi commented Jul 5, 2016

@dayuoba 啥意思?

@ecmadao

This comment has been minimized.

Copy link

ecmadao commented Jul 5, 2016

@dayuoba
同求,没有明白什么意思。。
我能想到的是,在循环过程中,随着index的增大,~~(Math.random() * (index + 1))能够选到首元素的概率会降低。但其实因为被random基数的增加,之前的每个元素被随机选到的可能性是一样的(不考虑Math.random伪随机的情况下)

for (var index = 0, rand; index < length; index++) {
    rand = ~~(Math.random() * (index + 1));
   // .....
}
@hanzichi

This comment has been minimized.

Copy link
Owner Author

hanzichi commented Jul 6, 2016

@ecmadao 不知道你说的没明白是没明白哪块?

@ecmadao

This comment has been minimized.

Copy link

ecmadao commented Jul 6, 2016

@hanzichi
就是 @dayuoba 所说的Fisher–Yates Shuffle 算法,首元素被洗掉的概率会越来越低

@hanzichi

This comment has been minimized.

Copy link
Owner Author

hanzichi commented Jul 6, 2016

@ecmadao 首元素被洗掉的概率确实越来越低了,但是首元素一直在变的呀,而且我们关心的是每个元素随机到每个位置的概率是否一致。

@ecmadao

This comment has been minimized.

Copy link

ecmadao commented Jul 6, 2016

@hanzichi
嗯那其实我们理解的一致,每个元素分配到的概率是总相同的。其实之前我都不知道有Fisher–Yates Shuffle,THX

@zhoucumt

This comment has been minimized.

Copy link

zhoucumt commented Sep 5, 2016

请教一下,_.intersection这个求数组交集的方法,为什么if (j === argsLength)的时候,就可以result.push(item);,这个判断条件没想明白

@hanzichi

This comment has been minimized.

Copy link
Owner Author

hanzichi commented Sep 5, 2016

@zhoucumt
遍历其他数组,如果其他数组中不存在 item 这个元素,那么就会 break 掉,这时 j 肯定小于 argsLength;而如果每个数组都存在 item 元素,则 for 循环可以执行到最后,for 循环结束时 j === argsLength,所以 j === argsLength 满足则说明每个数组都存在 item 元素。

其实我觉得源码注释说的好像蛮清楚了 ...

// Produce an array that contains every item shared between all the
// passed-in arrays.
// 寻找几个数组中共有的元素
// 将这些每个数组中都有的元素存入另一个数组中返回
// _.intersection(*arrays)
// _.intersection([1, 2, 3, 1], [101, 2, 1, 10, 1], [2, 1, 1])
// => [1, 2]
// 注意:返回的结果数组是去重的
_.intersection = function(array) {
  // 结果数组
  var result = [];

  // 传入的参数(数组)个数
  var argsLength = arguments.length;

   // 遍历第一个数组的元素
  for (var i = 0, length = getLength(array); i < length; i++) {
    var item = array[i];

    // 如果 result[] 中已经有 item 元素了,continue
    // 即 array 中出现了相同的元素
    // 返回的 result[] 其实是个 "集合"(是去重的)
    if (_.contains(result, item)) continue;

    // 判断其他参数数组中是否都有 item 这个元素
    for (var j = 1; j < argsLength; j++) {
      if (!_.contains(arguments[j], item)) break;
    }

    // 遍历其他参数数组完毕
    // j === argsLength 说明其他参数数组中都有 item 元素
    // 则将其放入 result[] 中
    if (j === argsLength) result.push(item);
  }

  return result;
};

另外,如果跟本主题无关的问题,希望能开个新的 issue ... 第一反应以为是关于数组乱序的问题 ... thanks

@hanzichi

This comment has been minimized.

Copy link
Owner Author

hanzichi commented Nov 17, 2016

感觉 GitHub 怎么自动把 <> 取消掉了 ... 囧

@luoliqiang luoliqiang referenced this issue Feb 9, 2017

Open

文章1 #1

@Mess1ah

This comment has been minimized.

Copy link

Mess1ah commented Mar 31, 2017

请问 _.sample 里面有个参数n 代表 返回n个元素 源码中return _.shuffle(obj).slice(0, Math.max(0,n)) 这里为什么要用Math.max(0,n) ? underscore中有好多地方都用了Math.max(0,n),为什么不能直接写n

@Nanchenk

This comment has been minimized.

Copy link

Nanchenk commented Jun 27, 2017

如果没记错的话,不是Math.random影像了结果,而是sort的实现,在20以内是插入排序,大于20是快排,而且不同浏览器的实现也不一样,ff好像是合并排序解决长数组的,恩,maybe吧

@huyansheng3

This comment has been minimized.

Copy link

huyansheng3 commented Feb 28, 2018

Fisher–Yates Shuffle 这个算法从尾部开始,将index 的内容和index 之前的数组中随机的一个交换,index 一直往前移动,但是到快要终止的时候,只能是 index =1 的索引和 index =0的索引交换,这样的新的数组,首部的数字相对固定。 在一些场景下,有一定缺陷。

第一种的方式则不会存在这个问题。

@zxalfred

This comment has been minimized.

Copy link

zxalfred commented Sep 29, 2018

@huyansheng3

从循环开始时起,首部数字即有被后面数字交换的概率,并不是当循环往前移动到相应位置时才能发生交换。所以不存在首部相对固定的问题。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment