lodash源码分析之数组的差集

外部世界那些破旧与贫困的样子,可以使我内心世界得到平衡。 ——卡尔维诺《烟云》

本文为读 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'

源码分析

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 中。

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

由之前的分析得知:

  • 如果指定 comparator ,则 includesarrayIncludesWith
  • 如果被比较的数组 values 的长度超过 200 ,则 includescacheHas
  • 否则,includesarrayIncludes

+0与-0的处理

在看代码的时候,有一段十分奇怪:

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

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

value === 0 时,可能为 +0-00 ,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)

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

作者:对角另一面

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏文武兼修ing——机器学习与IC设计

开放地址法散列开放地址法代码实现

开放地址法 开放地址法是另一种(相对于分离链接法)解决散列冲突的方法。适用于装填因子(散列表中元素个数和散列表长度比)较小(小于0.5)的散列表。 开放地址法中...

47312
来自专栏Spark生态圈

[spark] Shuffle Write解析 (Sort Based Shuffle)

从 Spark 2.0 开始移除了Hash Based Shuffle,想要了解可参考Shuffle 过程,本文将讲解 Sort Based Shuffle。

1522
来自专栏文武兼修ing——机器学习与IC设计

Python解决大规模二进制数据错位问题描述解决方法实验代码最终代码

问题描述 有一些二进制数据,每八位按顺序存为一个十进制数保存成CSV文件,每行为一个二进数数据,每个单元格均为一个十进制数。若数据为0000 0001 1000...

35110
来自专栏前端那些事

自制刻度尺插件-前端简易实现"腾讯信用"界面

依据我现有的知识,在前端上"简易"的实现了腾讯信用的界面,同时自己自制了一个竖直的刻度尺插件,曲线的位置可以根据传入的数值动态的改变,这次主要也想总结一下关于j...

31111
来自专栏北京马哥教育

Python 中被忽略的 else

1444
来自专栏祝威廉

ElasticSearch Aggregations GroupBy 实现源码分析

也就是按newtype 字段进行group by,然后对num求平均值。在我们实际的业务系统中,这种统计需求也是最多的。

4503
来自专栏Java进阶架构师

一文读懂JDK7,8,JD9的hashmap,hashtable,concurrenthashmap及他们的区别

图中,紫色部分即代表哈希表,也称为哈希数组(默认数组大小是16,每对key-value键值对其实是存在map的内部类entry里的),数组的每个元素...

973
来自专栏SDNLAB

POF技术分享(三):Packet处理流程

前言: 之前对POF基本原理、POF交换机源码结构进行解读,但是,要想完成POF交换机的二次开发和拓展,有必要对POF交换机特有的数据包处理流程、POF交换机和...

38612
来自专栏butterfly100

ConcurrentHashMap源码阅读

1. 前言 HashMap是非线程安全的,在多线程访问时没有同步机制,并发场景下put操作可能导致同一数组下的链表形成闭环,get时候出现死循环,导致CPU利用...

3147
来自专栏DOTNET

.Net多线程编程—Parallel LINQ、线程池

Parallel LINQ 1 System.Linq.ParallelEnumerable 重要方法概览: 1)public static ParallelQ...

3017

扫码关注云+社区

领取腾讯云代金券