• wordpress CMS主题:ssmay主题 wordpress CMS主题:ssmay主题
  • 首页 > 前端开发 > 解锁多种JavaScript数组去重姿势

    解锁多种JavaScript数组去重姿势

    作者: 分类:前端开发 点击: 105 次
    wordpress CMS主题:ssmay主题

      扫描下面的二维码,“关注”我的头条号,我会每天更新免费视频课程。

      JavaScript数组去重,一个老生常谈的问题了,但这次是解锁多种JavaScript数组去重姿势。

      对以下所有的实现算法,都使用以下代码进行粗略测试:

      const arr = [];
      // 生成[0, 100000]之间的随机数
      for (let i = 0; i < 100000; i++) {
        arr.push(0 + Math.floor((100000 - 0 + 1) * Math.random()))
      }
      
      // ...实现算法
      
      console.time('test');
      arr.unique();
      console.timeEnd('test');
      

      双重循环

      双重循环去重实现比较容易。
      实现一:

      Array.prototype.unique = function () {
        const newArray = [];
        let isRepeat;
        for (let i = 0; i < this.length; i++) {
          isRepeat = false;
          for (let j = 0; j < newArray.length; j++) {
            if (this[i] === newArray[j]) {
              isRepeat = true;
              break;
            }
          }
          if (!isRepeat) {
            newArray.push(this[i]);
          }
        }
        return newArray;
      }
      

      实现二:

      Array.prototype.unique = function () {
        const newArray = [];
        let isRepeat;
        for (let i = 0; i < this.length; i++) {
          isRepeat = false;
          for (let j = i + 1; j < this.length; j++) {
            if (this[i] === this[j]) {
              isRepeat = true;
              break;
            }
          }
          if (!isRepeat) {
            newArray.push(this[i]);
          }
        }
        return newArray;
      }
      

      基于思路二的写法改进版,实现三:

      Array.prototype.unique = function () {
        const newArray = [];
        
        for (let i = 0; i < this.length; i++) {
          for (let j = i + 1; j < this.length; j++) {
            if (this[i] === this[j]) {
              j = ++i;
            }
          }
          newArray.push(this[i]);
        }
        return newArray;
      }
      

      经过测试代码测试的时间如下:

      test1: 3688.440185546875ms
      test2: 4641.60498046875ms
      test3: 17684.365966796875ms
      

      Array.prototype.indexOf()

      基本思路:如果索引不是第一个索引,说明是重复值。
      实现一:

      • 利用Array.prototype.filter()过滤功能
      • Array.prototype.indexOf()返回的是第一个索引值
      • 只将数组中元素第一次出现的返回
      • 之后出现的将被过滤掉
      Array.prototype.unique = function () {
        return this.filter((item, index) => {
          return this.indexOf(item) === index;
        })
      }
      

      实现二:

      let arr = [1, 2, 3, 22, 233, 22, 2, 233, 'a', 3, 'b', 'a'];
      Array.prototype.unique = function () {
        const newArray = [];
        this.forEach(item => {
          if (newArray.indexOf(item) === -1) {
            newArray.push(item);
          }
        });
        return newArray;
      }
      

      经过测试代码测试的时间如下:

      test1: 4887.201904296875ms
      test2: 3766.324951171875ms
      

      Array.prototype.sort()

      基本思路:先对原数组进行排序,然后再进行元素比较。
      实现一:

      Array.prototype.unique = function () {
        const newArray = [];
        this.sort();
        for (let i = 0; i < this.length; i++) {
          if (this[i] !== this[i + 1]) {
            newArray.push(this[i]);
          }
        }
        return newArray;
      }
      

      经过测试代码测试的时间如下:

      test: 4300.39990234375ms
      

      实现二:

      Array.prototype.unique = function () {
        const newArray = [];
        this.sort();
        for (let i = 0; i < this.length; i++) {
          if (this[i] !== newArray[newArray.length - 1]) {
            newArray.push(this[i]);
          }
        }
        return newArray;
      }
      

      经过测试代码测试的时间如下:

      test1: 121.6259765625ms
      test2: 123.02197265625ms
      

      Array.prototype.includes()

      Array.prototype.unique = function () {
        const newArray = [];
        this.forEach(item => {
          if (!newArray.includes(item)) {
            newArray.push(item);
          }
        });
        return newArray;
      }
      

      经过测试代码测试的时间如下:

      test: 4123.377197265625ms
      

      Array.prototype.reduce()

      Array.prototype.unique = function () {
        return this.sort().reduce((init, current) => {
          if(init.length === 0 || init[init.length - 1] !== current){
            init.push(current);
          }
          return init;
        }, []);
      }
      

      经过测试代码测试的时间如下:

      test: 180.401123046875ms
      

      对象键值对

      基本思路:利用了对象的key不可以重复的特性来进行去重。
      但需要注意:

      • 无法区分隐式类型转换成字符串后一样的值,比如 1 和 '1'
      • 无法处理复杂数据类型,比如对象(因为对象作为 key 会变成 [object Object])
      • 特殊数据,比如 'proto',因为对象的 proto 属性无法被重写

      解决第一、第三点问题,实现一:

      Array.prototype.unique = function () {
        const newArray = [];
        const tmp = {};
        for (let i = 0; i < this.length; i++) {
          if (!tmp[typeof this[i] + this[i]]) {
            tmp[typeof this[i] + this[i]] = 1;
            newArray.push(this[i]);
          }
        }
        return newArray;
      }
      

      解决第二点问题,实现二:

      Array.prototype.unique = function () {
        const newArray = [];
        const tmp = {};
        for (let i = 0; i < this.length; i++) {
          // 使用JSON.stringify()进行序列化
          if (!tmp[typeof this[i] + JSON.stringify(this[i])]) {
            // 将对象序列化之后作为key来使用
            tmp[typeof this[i] + JSON.stringify(this[i])] = 1;
            newArray.push(this[i]);
          }
        }
        return newArray;
      }
      

      经过测试代码测试的时间如下:

      test1: 113.849365234375ms
      test2: 157.030029296875ms
      

      Map

      实现一:

      Array.prototype.unique = function () {
        const newArray = [];
        const tmp = new Map();
        for(let i = 0; i < this.length; i++){
              if(!tmp.get(this[i])){
                  tmp.set(this[i], 1);
                  newArray.push(this[i]);
              }
          }
          return newArray;
      }
      

      实现二:

      Array.prototype.unique = function () {
        const tmp = new Map();
        return this.filter(item => {
          return !tmp.has(item) && tmp.set(item, 1);
        })
      }
      

      经过测试代码测试的时间如下:

      test1: 27.89697265625ms
      test2: 21.945068359375ms
      

      Set

      Array.prototype.unique = function () {
        const set = new Set(this);
        return Array.from(set);
      }
      
      Array.prototype.unique = function () {
        return [...new Set(this)];
      }
      

      经过测试代码测试的时间如下:

      test1: 36.8046875ms
      test2: 31.98681640625ms
      

      总结

      除了考虑时间复杂度外、性能之外,还要考虑数组元素的数据类型(例如下面的例子)等问题权衡选择出采用哪种算法,例如:

      const arr = [1, 1, '1', '1', 0, 0, '0', '0', undefined, undefined, null, null, NaN, NaN, {}, {}, [], [], /a/, /a/];
      

      经过综合考虑,最优的数组去重算法是采用Map数据结构实现的算法。



      欢迎“关注”我的头条号,我会每天更新免费视频课程。

      头条二维码
      关注我的头条号
      头条二维码
      加入我的QQ群

    文章作者:sunny
    本文地址:http://wanlimm.com/77202006208287.html
    版权所有 © 转载时必须以链接形式注明作者和原始出处!

    上一篇:
    下一篇:
    wordpress CMS主题:ssmay主题

    或许你会感兴趣的文章:

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    This site uses Akismet to reduce spam. Learn how your comment data is processed.