lodash源码分析之去重uniq方法

作者: 沐风之境

lodash.js包是node开发中常用的js工具包,里面有许多实用的方法,今天分析常用的一个去重方法—uniq

用法

    _.uniq([2, 1, 2])
    // => [2, 1]

源码包

    // uniq.js
    import baseUniq from './.internal/baseUniq.js'

    function uniq(array) {
          return (array != null && array.length) ? baseUniq(array) : []
    }

    export default uniq

可以看到,uniq函数这边只做了一个针对baseUniq的封装,所以继续看baseUniq源码😂

    // baseUniq.js
    import SetCache from './SetCache.js'
    import arrayIncludes from './arrayIncludes.js'
    import arrayIncludesWith from './arrayIncludesWith.js'
    import cacheHas from './cacheHas.js'
    import createSet from './createSet.js'
    import setToArray from './setToArray.js'

    const LARGE_ARRAY_SIZE = 200 // 作为数组处理的最大数组长度
    function baseUniq(array, iteratee, comparator) {
      let index = -1
      let includes = arrayIncludes // 向下兼容,内部使用使用while做循环
      let isCommon = true

      const  = array
      const result = []
      let seen = result

      if (comparator) {
        // 如果有comparator,标注为非普通函数处理
        isCommon = false
        includes = arrayIncludesWith // includes 判重方法更换为 arrayIncludesWith
      }
      else if (length >= LARGE_ARRAY_SIZE) { // 长度超过200后启用,大数组优化策略
        // 判断是否有迭代器,没有则设为Set类型(支持Set类型的环境直接调用生成Set实例去重)
        const set = iteratee ? null : createSet(array) 
        if (set) {
          return setToArray(set) //Set类型转数组(Set类型中不存在重复元素,相当于去重了)直接返回
        }
        isCommon = false // 非普通模式
        includes = cacheHas // includes 判重方法更换为hash判断
        seen = new SetCache // 实例化hash缓存容器
      }
      else {
        // 存在迭代器的情况下,新开辟内存空间为缓存容器,否则直接指向结果数组容器
        seen = iteratee ? [] : result
      }
      outer:
      while (++index < length) { // 循环遍历每一个元素
        let value = array[index] // 取出当前遍历值
        // 存在迭代器函数执行迭代器函数后返回结果,否则直接返回自身
        const computed = iteratee ? iteratee(value) : value 

        value = (comparator || value !== 0) ? value : 0
        if (isCommon && computed === computed) { // 普通模式执行下面代码
          let seenIndex = seen.length // 取当前容器的长度为下一个元素的角标
          while (seenIndex--) { // 循环遍历每一个容器中每一个元素
            if (seen[seenIndex] === computed) { // 匹配到重复的元素
              continue outer // 直接跳出当前循环直接进入下一轮outer:
            }
          }
          if (iteratee) { // 有迭代器的情况下
            seen.push(computed) // 结果推入缓存容器
          }
          result.push(value) // 追加入结果数组
        }
         // 非正常数组处理模式下,调用includes方法,判断缓存容器中是否存在重复的值
        else if (!includes(seen, computed, comparator)) {
          if (seen !== result) { // 非普通模式下,result和seen内存空间地址不一样
            seen.push(computed)
          }
          result.push(value) // 追加入结果数组
        }
      }
      return result // 循环完成,返回去重后的数组
    }

    export default baseUniq

大致的流程:

逻辑流程

分析

1.注意下面的代码:

    else if (length >= LARGE_ARRAY_SIZE) { // 长度超过200后启用,大数组优化策略
    // 判断是否有迭代器,没有则设为Set类型(支持Set类型的环境直接调用生成Set实例去重)
    const set = iteratee ? null : createSet(array) 
    if (set) {
      return setToArray(set) //Set类型转数组(Set类型中不存在重复元素,相当于去重了)直接返回
    }
  }

lodash 会去判断当前数组的长度,如果数组过大会调用ES6的新的Set数据类型,Set类型中不会存在重复的元素。也就是说做到了数组的去重,最后调用setToArray方法返回数组,Set类型是可迭代的类型,可以使用 ...扩展运算符。
在性能方面,因为js是单线程执行,大数组的循环会长时间占用CPU时间,导致线程被阻塞。而使用Set类型后将去重的工作交个底层去处理,提高了性能。所以平时在有去重需求时可以考虑Set类型的去重,而不是在js执行层去做循环,也是一种性能优化。

2.接着看不采用Set去重的代码处理策略:

    outer:
      while (++index < length) { // 循环遍历每一个元素
        let value = array[index] // 取出当前遍历值

        value = (comparator || value !== 0) ? value : 0
        if (isCommon && computed === computed) { // 普通模式执行下面代码
          let seenIndex = seen.length // 取当前容器的长度为下一个元素的角标
          while (seenIndex--) { // 循环遍历每一个容器中每一个元素
            if (seen[seenIndex] === computed) { // 匹配到重复的元素
              continue outer // 直接跳出当前循环直接进入下一轮outer:
            }
          }
        }
      }

可以看到这里使用两个嵌套while去遍历数组,并判断是否存在重复元素。这样的逻辑并没有问题,也是平时工作中最常见的去重代码逻辑,代码的执行时间复杂度为 O(n^2),执行时间会随着数组的增大指数级增加,所以也就是为什么lodash的uniq函数要规定最大的可迭代数组长度,超过长度采用Set去重法。避免性能浪费

尾巴

ES6的出现真的很大程度上方便代码的编写,ES6这么方便为什么还喜欢lodash这种库,既臃肿复杂,又需要记忆很多API。的回答是高效、优雅、省心。工作时使用成熟库是对代码质量的保证,并且成熟的库一般会对性能部分进行优化。

原文创作:沐风之境

原文链接:https://www.cnblogs.com/mufeng3421/p/10262636.html

更多推荐

更多
  • 二、创建模式— 单例、构建者、工厂、原型和抽象工厂设计模式 单例设计模式-在整个程序中具有唯一的类型实例,你曾经为软件工程师做过面试吗?有趣的是,当你问他们设计模式时,超过 ...
  • 五、行为模式—策略、责任链和命令设计模式 ...
  • 六、行为模式—模板、备忘录和解释器设计模式 模板设计模式,模板模式是广泛使用的模式之一,非常有用,尤其是在编写库和框架时。其思想是为用户提供某种在算法中执行代码的方法。匿名函数,这不是实现模板设计模式的唯一方法。我们还可以使用匿名函数来实现ExecuteAlgorithm方法。 Go...
  • 三、结构模式——组合、适配器和桥接设计模式 复合设计模式,复合设计模式倾向于组合,总之,Go ...
  • 四、结构模式——代理、外观、装饰和享元设计模式 代理设计模式,我们将从代理模式开始关于结构模式的最后一章。代理模式的可能性很多,但一般来说,它们都试图提供相同的以下功能:将对象隐藏在代理后面,以便可以隐藏、限制特征等,提供一个易于使用且易于更改的新抽象层,从 Go 的 1.7 ...
  • 十、并发模式—工作池和发布/订阅设计模式 其思想是学习使用惯用的 Go 设计并发应用程序的模式。我们大量使用通道和 goroutine,而不是锁或共享变量。我们将研究一种发展员工队伍的方法。这对于控制执行中 goroutine ...
  • 七、行为模式—访客、状态、中介和观察者设计模式 访客设计模式,在下一个设计模式中,我们将把对象类型的一些逻辑委托给称为访问者的外部类型,访问者将访问我们的对象以对其执行操作。在 Visitor ...
  • Go设计模式-八、Go 并发介绍 CSP 与基于参与者的并发,考虑并发性的最常见、也许也是最直观的方式是与 actor 模型的工作方式相近的方式。在 actor 模型中,如果actor 1想要与actor 2通信,那么actor 1必须先知道actor 2;在 Go ...
  • 九、并发模式—屏障、未来和管道设计模式 障碍是一种非常常见的模式,尤其是当我们必须等待来自不同 goroutine 的多个响应之后,才能让程序继续,未来模式允许我们编写最终由同一个 Goroutine 或另一个 Goroutine ...
  • Go设计模式-Go 设计模式 文章列表,Go设计模式-Go 设计模式,Go设计模式-一、准备,出发,Go设计模式-八、Go 并发介绍,Go设计模式-零、序言,七、行为模式——访客、状态、中介和观察者设计模式
  • 近期文章

    更多
    文章目录

      推荐作者

      更多