-
Notifications
You must be signed in to change notification settings - Fork 642
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
Comments
@dayuoba 啥意思? |
@dayuoba for (var index = 0, rand; index < length; index++) {
rand = ~~(Math.random() * (index + 1));
// .....
} |
@ecmadao 不知道你说的没明白是没明白哪块? |
@ecmadao 首元素被洗掉的概率确实越来越低了,但是首元素一直在变的呀,而且我们关心的是每个元素随机到每个位置的概率是否一致。 |
@hanzichi |
请教一下,_.intersection这个求数组交集的方法,为什么if (j === argsLength)的时候,就可以result.push(item);,这个判断条件没想明白 |
@zhoucumt 其实我觉得源码注释说的好像蛮清楚了 ... // 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 |
感觉 GitHub 怎么自动把 |
请问 _.sample 里面有个参数n 代表 返回n个元素 源码中 |
如果没记错的话,不是Math.random影像了结果,而是sort的实现,在20以内是插入排序,大于20是快排,而且不同浏览器的实现也不一样,ff好像是合并排序解决长数组的,恩,maybe吧 |
Fisher–Yates Shuffle 这个算法从尾部开始,将index 的内容和index 之前的数组中随机的一个交换,index 一直往前移动,但是到快要终止的时候,只能是 index =1 的索引和 index =0的索引交换,这样的新的数组,首部的数字相对固定。 在一些场景下,有一定缺陷。 第一种的方式则不会存在这个问题。 |
从循环开始时起,首部数字即有被后面数字交换的概率,并不是当循环往前移动到相应位置时才能发生交换。所以不存在首部相对固定的问题。 |
前言
终于可以开始 Collection Functions 部分了。
可能有的童鞋是第一次看楼主的系列文章,这里再做下简单的介绍。楼主在阅读 underscore.js 源码的时候,学到了很多,同时觉得有些知识点可以独立出来,写成文章与大家分享,而本文正是其中之一(完整的系列请猛戳 https://github.com/hanzichi/underscore-analysis)。之前楼主已经和大家分享了 Object 和 Array 的扩展方法中一些有意思的知识点,今天开始解读 Collection 部分。
看完 Collection Functions 部分的源码,首先迫不及待想跟大家分享的正是本文主题 —— 数组乱序。这是一道经典的前端面试题,给你一个数组,将其打乱,返回新的数组,即为数组乱序,也称为洗牌问题。
一个好的方案需要具备两个条件,一是正确性,毋庸置疑,这是必须的,二是高效性,在确保正确的前提下,如何将复杂度降到最小,是我们需要思考的。
splice
几年前楼主还真碰到过洗牌问题,还真的是 "洗牌"。当时是用 cocos2d-js(那时还叫 cocos2d-html5)做牌类游戏,发牌前毫无疑问需要洗牌。
当时我是这样做的。每次 random 一个下标,看看这个元素有没有被选过,如果被选过了,继续 random,如果没有,将其标记,然后存入返回数组,直到所有元素都被标记了。后来经同事指导,每次选中后,可以直接从数组中删除,无需标记了,于是得到下面的代码。
这个解法的正确性应该是没有问题的(有兴趣的可以自己去证明下)。我们假设数组的元素为 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() 函数。
同样是 [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)。
其实它的思想非常的简单,遍历数组元素,将其与之前的任意元素交换。因为遍历有从前向后和从后往前两种方式,所以该算法大致也有两个版本的实现。
从后往前的版本:
underscore 中采用从前往后遍历元素的方式,实现如下:
将其解耦分离出来,如下:
跟前面一样,做了下数据图表,猛戳 http://hanzichi.github.io/test-case/shuffle/Fisher-Yates/。
关于证明,引用自月影老师的文章:
随机性的数学归纳法证明
对 n 个数进行随机:
小结
关于数组乱序,如果面试中被问到,能说出 "Fisher–Yates Shuffle",并且能基本说出原理(你也看到了,其实代码非常的简单),那么基本应该没有问题了;如果能更进一步,将其证明呈上(甚至一些面试官都可能一时证明不了),那么就牛逼了。千万不能只会用 Math.random() 投机取巧!
Read More:
The text was updated successfully, but these errors were encountered: