lodash源码分析之数组的差集

Noodles 发布于2019-08-22 15:23 / 2667人阅读

摘要：依赖源码分析之缓存使用方式的进一步封装源码分析之源码分析之源码分析之的实现源码分析之源码分析的调用如果有传递，则先调用，使用生成要比较数组的映射数组。循环完毕，没有在第二个数组中发现相同的项时，将该项存入数组中。

外部世界那些破旧与贫困的样子，可以使我内心世界得到平衡。

——卡尔维诺《烟云》

本文为读 lodash 源码的第十七篇，后续文章会更新到这个仓库中，欢迎 star：pocket-lodash

gitbook也会同步仓库的更新，gitbook地址：pocket-lodash

作用与用法

baseDifference 可以用来获取指定数组与另一个数组的差集。

这个函数是内部函数，是后面实现其它比较函数的核心函数。

baseDifference 的方法签名如下：

baseDifference(array, values, iteratee, comparator)

第一和第二个参数是需要比较的两个数组；iteratee 可以返回一值映射值，比较时，可以使用映射的值来进行比较； comparator 是自定义比较函数，如果有传递，则调用自定义的比较函数来进行交集的比较。

依赖

import SetCache from "./SetCache.js"
import arrayIncludes from "./arrayIncludes.js"
import arrayIncludesWith from "./arrayIncludesWith.js"
import map from "../map.js"
import cacheHas from "./cacheHas.js"

lodash源码分析之缓存使用方式的进一步封装

lodash源码分析之arrayIncludes

lodash源码分析之arrayIncludesWith

lodash源码分析之map的实现

lodash源码分析之cacheHas

源码分析

const LARGE_ARRAY_SIZE = 200
function baseDifference(array, values, iteratee, comparator) {
  let includes = arrayIncludes
  let isCommon = true
  const result = []
  const valuesLength = values.length

  if (!array.length) {
    return result
  }
  if (iteratee) {
    values = map(values, (value) => iteratee(value))
  }
  if (comparator) {
    includes = arrayIncludesWith
    isCommon = false
  }
  else if (values.length >= LARGE_ARRAY_SIZE) {
    includes = cacheHas
    isCommon = false
    values = new SetCache(values)
  }
  outer:
  for (let value of array) {
    const computed = iteratee == null ? value : iteratee(value)

    value = (comparator || value !== 0) ? value : 0
    if (isCommon && computed === computed) {
      let valuesIndex = valuesLength
      while (valuesIndex--) {
        if (values[valuesIndex] === computed) {
          continue outer
        }
      }
      result.push(value)
    }
    else if (!includes(values, computed, comparator)) {
      result.push(value)
    }
  }
  return result
}

iteratee的调用

if (iteratee) {
  values = map(values, (value) => iteratee(value))
}

如果有传递 iteratee ，则先调用 map ，使用 iteratee 生成要比较数组的映射数组 values。

因为后面会有嵌套循环，避免重复调用 iteratee ，影响性能，所以一开始就需要生成 values 的映射数组。

性能优化

这里使用了 isCommon 来标志是否使用普通方式来处理。

if (comparator) {
  includes = arrayIncludesWith
  isCommon = false
}

如果有传递比较函数，则将 isCommon 标记为 false，表示不用普通的方式来处理，后面可以看到，最后会使用 includes 方法来处理，也即 arrayIncludesWith 方法。

else if (values.length >= LARGE_ARRAY_SIZE) {
  includes = cacheHas
  isCommon = false
  values = new SetCache(values)
}

如果不需要使用自定义的比较方式，并且数组较大时（这里限定了200），则使用 SetCache 类来缓存数组。

SetChche 其实使用的是 Map/Set 或者对象的方式来存储，避免大数组嵌套循环时造成的性能损耗。

### 循环比较

接下来就遍历第一个数组 array，将数组中的每一项和第二个数组的每一项比较。

if (isCommon && computed === computed) {
  let valuesIndex = valuesLength
  while (valuesIndex--) {
    if (values[valuesIndex] === computed) {
      continue outer
    }
  }
  result.push(value)
}
else if (!includes(values, computed, comparator)) {
  result.push(value)
}

可以看到，如果 isCommon 没有标记为 false，或者需要比较的值 computed 不为 NaN 时，都采用嵌套循环的方式来比较。循环完毕，没有在第二个数组中发现相同的项时，将该项存入数组 result 中。

如果 isCommon 为 false 或者需要比较的值为 NaN 时，则调用 includes 方法来比较。

由之前的分析得知：

如果指定 comparator ，则 includes 为 arrayIncludesWith

如果被比较的数组 values 的长度超过 200 ，则 includes 为 cacheHas

否则，includes 为 arrayIncludes

+0与-0的处理

在看代码的时候，有一段十分奇怪：

value = (comparator || value !== 0) ? value : 0

这段代码的意思是，在没有提供 comparator 的情况下，如果 value === 0 ，则将 value 赋值为 0 。

value === 0 时，可能为 +0 、-0 和 0 ，lodash 为什么要将它们都转为 0 呢？

后来看到 lodash 作者在 issue 中说，因为比较会用到 Set ，而 Set 是不能区分 +0 和 -0 的。

参考

Lodash系列——difference函数源码解析

value = (comparator || value !== 0) ? value : 0; does it work?

License

署名-非商业性使用-禁止演绎 4.0 国际 (CC BY-NC-ND 4.0)

最后，所有文章都会同步发送到微信公众号上，欢迎关注,欢迎提意见：

作者：对角另一面

云服务器 GPU云服务器源码中文说明之大数据之数据挖掘分析 lodash cdn lodash

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/93421.html

lodash源码分析之缓存使用方式的进一步封装

摘要：但是在类中，要初始化缓存和设置缓存都需要提供和组成的二维数组，因此在类中，提供了一种更方便的缓存设置方式，只需要提供缓存的值即可。这里构造函数不需要再传入的二维数组了，只需要传入包含所有缓存值的数组即可。在世界上所有的民族之中，支配着他们的喜怒选择的并不是天性，而是他们的观点。——卢梭《社会与契约论》本文为读 lodash 源码的第九篇，后续文章会更新到这个仓库中，欢迎 star...

neroneroffy 2019-08-06 13:29 评论0 收藏0
lodash源码分析之缓存使用方式的进一步封装

摘要：但是在类中，要初始化缓存和设置缓存都需要提供和组成的二维数组，因此在类中，提供了一种更方便的缓存设置方式，只需要提供缓存的值即可。这里构造函数不需要再传入的二维数组了，只需要传入包含所有缓存值的数组即可。在世界上所有的民族之中，支配着他们的喜怒选择的并不是天性，而是他们的观点。——卢梭《社会与契约论》本文为读 lodash 源码的第九篇，后续文章会更新到这个仓库中，欢迎 star...

wapeyang 2019-08-26 11:30 评论0 收藏0
lodash源码分析之chunk的尺与刀

摘要：万条数据依赖读源码之从看稀疏数组与密集数组原理的原理归结起来就是切割和放置。尺在切割之前，需要用尺确定切割的数量。容器的长度刚好与块的数量一致。当与块的数量相等时，表示已经切割完毕，停止切割，最后将结果返回。以不正义开始的事情，必须用罪恶使它巩固。——莎士比亚《麦克白》最近很多事似乎印证了这句话，一句谎言最后要用一百句谎言来圆谎。本文为读 lodash 源码的第二篇，后续文章会...

ZweiZhao 2019-08-21 17:56 评论0 收藏0
lodash源码分析之自减的两种形式

摘要：作用与用法是的内部函数，之前在源码分析之缓存介绍过一种这样的数据结构这是一个二维数组，每项中的第一项作为缓存对象的，第二项为缓存的值。这个世界需要一个特定的恶人，可以供人们指名道姓，千夫所指：全都怪你。——村上春树《当我谈跑步时我谈些什么》本文为读 lodash 源码的第六篇，后续文章会更新到这个仓库中，欢迎 star：pocket-lodash gitbook也会同步仓库的更新...

Keven 2019-08-21 18:44 评论0 收藏0
lodash源码分析之List缓存

摘要：在之前的文章中已经介绍过，检测的是对应的数组在二维数组中的索引，其行为跟一致，不存在于二维数组中时，返回，否则返回索引值。最后将缓存数量减少。昨日我沿着河岸/漫步到/芦苇弯腰喝水的地方顺便请烟囱/在天空为我写一封长长的信潦是潦草了些/而我的心意/则明亮亦如你窗前的烛光/稍有暧昧之处/势所难免/因为风的缘故 ——洛夫《因为风的缘故》本文为读 lodash 源码的第七篇，后续文章会...

leon 2019-08-06 13:28 评论0 收藏0