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 { length } = 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。我的回答是高效、優雅、省心。工作時使用成熟庫是對代碼品質的保證，并且成熟的庫一般會對性能部分進行優化。

沐風的原創文章