打造属于自己的underscore系列(六)- 洗牌算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:javascript如何将一个无序的数组变成一个有序的数组,我们有很多的排序算法可以实现,例如冒泡算法,快速排序,插入排序等。然而我们是否想过,如何将一个有序的数组乱序输出呢?本文将从经典的洗牌算法出发,详细讲解underscore中关于乱序排列的实现。在介绍洗牌算法的概念前,我们先引入现实生活的一个经典例子。当我们和多人一起玩扑克牌的时候,我们需要先将一份全新的扑克牌打乱,让牌组随机化,以确保游戏的公平性。这个将牌组随机化的过程,我们衍生到代码中可以概括为: 一个有序的数组[1,2,3,4,5],如何随机

javascript如何将一个无序的数组变成一个有序的数组,我们有很多的 排序 算法可以实现,例如冒泡算法,快速排序,插入排序等。然而我们是否想过,如何将一个有序的数组乱序输出呢?本文将从经典的洗牌算法出发,详细讲解underscore中关于乱序排列的实现。

六,洗牌算法

6.1 问题探讨

在介绍洗牌算法的概念前,我们先引入现实生活的一个经典例子。当我们和多人一起玩扑克牌的时候,我们需要先将一份全新的扑克牌打乱,让牌组随机化,以确保游戏的公平性。这个将牌组随机化的过程,我们衍生到代码中可以概括为: 一个有序的数组[1,2,3,4,5],如何随机打乱,使生成一个随机的数组,如[3,2,5,1,4],且需要保证数组中的数出现在每个位置的概率相同。如何实现呢?

利用es5的sort函数,其实我们很容易找到一种简洁的方法。

var shuffle = (arr) => arr.sort(() => Math.random() - 0.5)
复制代码

本质上利用es6原生的sort函数,我们可以达到数组乱序,然而sort方法本身却无法保证元素出现在每个位置上出现的概率随机。在 关于 JavaScript 的数组随机排序 一文中,作者详细讲解了使用sort排序并不能保证随机,并且列举了造成无法随机化的原因。文章较长,大概可以总结为以下两点。

  • 1.各个浏览器对于sort中使用 排序算法 的差异导致sort本身随机排序概率的差异,例如chrome浏览器对排序算法做了优化,小于等于10的数组使用相对稳定的插入排序,大于10的采用相对不稳定的快速排序,而FireFox使用的排序算法是归并排序等。显然,排序算法的不同,导致使用sort排序的概率结果也不可能相同。
  • 2.sort排序的本质还是两两比较,而我们知道,一个n位数组,要进行两两比较,它的时间复杂度为n(n-1)/2, 而不管什么排序算法,它的时间复杂度都要小于n(n-1)/2,那既然如此,又如何保证新数组已经是两两比较后生成的随机数组呢。

6.2 洗牌算法概念

其实,为了实现这一场景,前人已经给出了问题的答案,也就是公认成熟的洗牌算法(Fisher-Yates),简单的思路如下:

    1. 定义一个数组,以数组的最后一个元素为基准点。
    1. 在数组开始位置到基准点之间随机取一个位置,将所取位置上的元素和基准点上的元素互换。
    1. 基准点左移一位。
    1. 重复2,3步骤,直到基准点为数组的开始位置。

由于第二步生成随机位置的随机性,所以整个洗牌算法保证了乱序的随机性。将文字转化为代码,javascript的简单实现如下:

function shuffle(arr) {
    var length = arr.length,
        j = length;
    for (var i = 0; i < length; i++) {
        var random = Math.floor(Math.random() * (j--)); // 生成起始位置到基准位置之间的随机位置,并将基准从结束位置不停左移。
        // es3实现
        var newA = arr[i];
        arr[i] = arr[random];
        arr[random] = newA
        // es6 实现
        [arr[i], arr[random]] = [arr[random], arr[i]]; // 本质为交换元素位置。
    }
    return arr
}
复制代码

underscore中在乱序方面同样用到了洗牌算法,有了洗牌算法的概念和实现基础后,接下来我们将关注点放在underscore中乱序方法的实现中。

6.3 random - _.random(min, max)

洗牌算法的第二步,生成随机数的过程,无疑需要使用到原生 Math.random() (产生一个[0,1)之间的随机数),而underscore在原生的 Math.random() 方法上,重新包装了random函数,实现在给定范围内生成随机整数,如果只传递一个参数,那么将返回0和这个参数之间的整数。

// 随机函数
_.random = function (min, max) {
    if (max == null) { // max == null即代表只传递一个参数,此时最大值为传递的最小值,最小值为0
        max = min;
        min = 0;
    }
    return min + Math.floor(Math.random() * (max - min + 1)); // 生成[min, max]之前的随机数
};
复制代码

6.4 sample - _.sample(list, [n])

在underscore 1.8版本以前,洗牌算法的实现直接放在了 _.shuffle 方法中实现,而1.9的版本直接抛弃了这种写法,我们将放在下文分析这种写法。在1.9版本中,洗牌算法的实现放在了sample函数中,sample会在 list中产生一个随机样本。n则代表返回多少个随机数。同时list不仅可以是数组,也可以是对象或者类数组,当list为对象时,随机返回的是对象的值,如

console.log(_.sample({a: 123, b: 234}, 2)) // 234 123
复制代码

实现思路如下

_.sample = function(list, n) {
    if(n == null) { // 不指定个数时,默认在数组中随机取出一个。
        if (!isArrayLike(obj)) list = _.values(list); // list为对象时,取出对象值的集合。
        return list[_.random(list.length - 1)] // 生成数组的随机位置,返回该位置的值。
    }
    var sample = isArrayLike(obj) ? _.clone(obj) : _.values(obj); // 数组类数组得到克隆的数组,对象得到值的集合。
    var length = getLength(sample);
    n = Math.max(Math.min(n, length), 0); // 对n的大小做限制,不能大于新数组的长度,不能小于0。
    var last = length - 1;
    for (var index = 0; index < n; index++) { //  for循环下的操作为洗牌算法的核心步骤,和前面讲解的实现方式相同。
        var rand = _.random(index, last);
        var temp = sample[index];
        sample[index] = sample[rand];
        sample[rand] = temp;
    }
    return sample.slice(0, n);
}
复制代码

6.5 shuffle - _.shuffle(list)

shuffle是洗牌算法的用法函数,返回一个随机乱序的list副本。有了_.sample的基础,shuffle只需要传递一个n值为数组长度的参数给sample函数即可。

_.shuffle = function(list) {
    return _.sample(obj, Infinity); // n值传递无穷大,由于sample函数内部对n值的限制,真正执行洗牌算法时,n的值为数组的长度。
}
复制代码

6.6 underscore其他版本的实现

前面提到,1.8版本以前underscore对于洗牌算法的实现放在了shuffle函数中,它的实现相比于1.9版本来说,有很多的巧妙之处,我们来看看实现代码。

_.shuffle = function(obj) {
    var set = obj && obj.length === +obj.length ? 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;
};
复制代码
// 交换位置代码 
    if (rand !== index) shuffled[index] = shuffled[rand];
    shuffled[rand] = set[index];
复制代码

中间关系乱序的实现看起来很巧妙,我们来详细分析每一步是如何进行的。

  1. 我们定义一个数组 [1,2,3,4]
  2. 生成一个长度相同的空数组作为乱序后的新数组 shuffle = [undefined, undefined, undefined, undefined]
  3. index从第一个数开始,也就0开始,生成一个 0 - index 之间的随机数,第一个固定为0
  4. 随机数和 index相同,所以执行 shuffled[0] = set[0] = 1 shuffle依然为 shuffle = [1, undefined, undefined, undefined]
  5. index = 1, 生成 0 -1 之间的随机数,假设随机数为0
  6. 此时执行交换代码 shuffled[1] = shuffled[0] = 1 ; shuffled[0] = set[1] = 2; 即 shuffle改变成 shuffle = [2, 1, undefined, undefined]
  7. index = 2, 生成 0 - 2 之间的随机数,假设随机数为1
  8. 此时执行交换代码 shuffled[2] = shuffled[1] = 1 ; shuffled[1] = set[2] = 3; 即 shuffle改变成 shuffle = [2, 3, 1, undefined]
  9. index = 3, 生成 0 - 3 之间的随机数,假设随机数为0
  10. 此时执行交换代码 shuffled[3] = shuffled[0] = 3 ; shuffled[0] = set[3] = 4; 即 shuffle改变成 shuffle = [4, 3, 1, 2] 经过以上十步,乱序数组也随之生成

以上所述就是小编给大家介绍的《打造属于自己的underscore系列(六)- 洗牌算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

HTML5与CSS3基础教程(第7版)

HTML5与CSS3基础教程(第7版)

[美] Elizabeth Castro、[美] Bruce Hyslop / 望以文 / 人民邮电出版社 / 2013-1 / 59.00元

代表下一代网页编写技术的HTML5,为网页提供布局和格式的CSS3,这两者构成了Web开发的基石,也是Web程序员和设计师必须熟练掌握的最基本技能。 本书是风靡全球的HTML和CSS最佳入门教程的最新版,上一版单单英文版的销量就超过100万册,被翻译为十多种语言,并长期雄踞亚马逊书店计算机图书排行榜榜首。 最新的第7版秉承前一版直观、透彻、全面、循序渐进的讲授特色,仍然采用独特的双栏图......一起来看看 《HTML5与CSS3基础教程(第7版)》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

在线进制转换器
在线进制转换器

各进制数互转换器

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具