lodash源碼分析之數組的差集

Noodles 發布于2019-08-22 15:23 / 2669人閱讀

摘要：依賴源碼分析之緩存使用方式的進一步封裝源碼分析之源碼分析之源碼分析之的實現源碼分析之源碼分析的調用如果有傳遞，則先調用，使用生成要比較數組的映射數組。循環完畢，沒有在第二個數組中發現相同的項時，將該項存入數組中。

外部世界那些破舊與貧困的樣子，可以使我內心世界得到平衡。

——卡爾維諾《煙云》

本文為讀 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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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