算法-数组去重

2020-02-13

关键词: 去重unique

这是一篇考古文,2013玉伯在优化SeaJs性能时提出的一个问题,原文出处在这里从js数组去重谈性能优化, 以数组去重为切入点,比较辩证的谈了解决问题的方法论。 核心观点可以看下原文,本文只讲数组去重的最优方法以及其他几种方法。

最优方法

利用对象的属性不会重复这一特性,首先创建一个空对象,然后用 for 循环遍历,来校验数组元素是否重复。

let a = [0,1,1,2,3,4,4,4];
let result = [];
let obj = {};

for(let i of a){
    if (!obj[i]){
      result.push(i);
      obj[i] = 1;
  }
}
Object.keys(obj)

上面这种方法,无论从代码量和执行的时间复杂度上讲都是不错的。

最优方法2

高版本的运行环境,使用ES6的Set结构来去重,使用起来更方便:

let set = new Set([1,2,3,3,3,3]); // 数组转成set
console.log(set ); // set结构{1,2,3}
console.log([...set]) // set转成数组 [1,2,3]

这两种方法对于多少场景已经够用了,但需求往往都不是那么“纯粹的”,实际工作中要求数组去重算法可以和不同的算法逻辑组合实现一个复合的需求。

个人理解代码优化就是一个对内优化,对外兼容的过程,不管是向内还是向外,坚持去做我理解是可以收获到以下几点:

  1. 训练自己的代码优化思路,并且对优化过程复盘
  2. 将最优结果实现思路写成一条流程线
  3. 将多个最优结果的流程线横向对齐比较,总结出处理问题的公共节点
  4. 形成一套自己的方法论,该套用时就套用(没研究过八股文,就不要去批判,有套路的东西是有可取之处的),套用模板可以节约时间,用节约出来的时间再去创造才是最高效的。
  • 这是必须要养成的一个能力,这个能力可以帮助自己去看懂别人写的代码。
  • 看好的框架的代码比零碎的学习更能学到东西,就像好的老师让学习更容易。

向内实现

简单讲就是提供一个完整的兼容方案,也可以理解成内聚,对外只提供一个函数。 例如 underscore中的uniq函数,不仅可以对数据去重,也可以对object类型去重呀。

  1. 能有多少种思路去实现数组去重算法
  2. 识别问题,并且能合理的去优化
  3. 这一个问题有多少知识点呢?例如:IE8下不支持indexOf(知识点只有结合实际才能清晰记得和灵活使用

--未完--

underscore的uniq函数源码及注释:

_.uniq = _.unique = function(array, isSorted, iteratee, context) {
    if (array == null) return [];
    if (!_.isBoolean(isSorted)) {
      //如果没有排序
      context = iteratee;
      iteratee = isSorted;
      isSorted = false;
    }
    /**
    ** 此处_.iteratee
    **  function (key){
    *      return function(obj){
    *        return obj[key];
    *      }
    **  }
    **  key就是这里的iteratee(对象的属性),这里使用了闭包
    **/
    if (iteratee != null) iteratee = _.iteratee(iteratee, context); 
    var result = [];//返回去重后的数组(副本)
    var seen = [];
    for (var i = 0, length = array.length; i < length; i++) {
      var value = array[i];//当前比较值
      if (isSorted) {
        //如果i=0时,或者seen(上一个值)不等于当前值,放入去重数组中
        if (!i || seen !== value) result.push(value); 
        seen = value;//保存当前值,用于下一次比较
      } else if (iteratee) {
        var computed = iteratee(value, i, array);
        if (_.indexOf(seen, computed) < 0) {
          seen.push(computed);
          result.push(value);
        }
      } else if (_.indexOf(result, value) < 0) {
        result.push(value);
      }
    }
    return result;
  };
原文链接:juejin.im

上一篇:ReactNatve项目的升级
下一篇:重学css盒模型
相关教程
关注微信

扫码加入 JavaScript 社区

相关文章

首次访问,需要验证
微信扫码,关注即可
(仅需验证一次)

欢迎加入 JavaScript 社区

号内回复关键字:

回到顶部