lodash源码分析(sortIndex和union函数)

sortIndex函数

我的实现

function sortIndex(array,value) {
    let len = array.length;
    let index = 0;



    while(index < len)  {
        if (value <= array[index]) {
            break
        }
        index++
    }

    return index
}

别人的实现

function baseSortedIndex(array, value) {
  let low = 0
  let high = array == null ? low : array.length

  if (typeof value == 'number' && value === value && high <= HALF_MAX_ARRAY_LENGTH) {
    while (low < high) {
      const mid = (low + high) >>> 1
      const computed = array[mid]
      if (computed !== null && !isSymbol(computed) && computed < value) {
        low = mid + 1
      } else {
        high = mid
      }
    }
    return high
  }
}

总结

• 主要是算法比我的好，使用的二分查找法，时间复杂度是logn,比我的快。照理说，这种算法我应该很熟的。当时写代码时应该想得到的。
• 在算Math.floor((1+2) /2)时，用了(1+2) >>>1 来计算。

sortUniq函数

我的实现

function sortedUniq(array) {
    let len = array.length;
    let result = [];

    let preVal
    for(let val of array) {
        if (val != preVal) {
            result.push(val);
            preVal = val
        }
    }

    return result
}

别人的实现

function eq(value, other) {
  return value === other || (value !== value && other !== other)
}
function baseSortedUniq(array, iteratee) {
  let seen
  let index = -1
  let resIndex = 0

  const { length } = array
  const result = []

  while (++index < length) {
    const value = array[index], computed = iteratee ? iteratee(value) : value
    if (!index || !eq(computed, seen)) {
      seen = computed
      result[resIndex++] = value === 0 ? 0 : value
    }
  }
  return result
}

我的总结

• 算法是一致的。因为注意到是已经排序过的数组。所以没有使用hash字典的算法来去重，虽然时间复杂度一致，但是后者浪费了空间
• 唯一的区别是别人实现的eq函数，这是一个严格判断两个变量是否相等的函数，在这个eq函数中 1=== '1'是false），当然代码value !== value && other !== other是为了判断eq(NaN, NaN)为true的。

union函数

我的实现

function union(...arrays) {
    let result = []
    let finalResult = []
    for (let val of arrays) {
        result = [...result, ...val]
    }


    //unique所有的数组
    let uniqueHashMap = {};
    for (let value of result) {
        debugger
        uniqueHashMap[value] = uniqueHashMap[value] ? (uniqueHashMap[value] + 1) : 1
    }

    console.log(uniqueHashMap)

    //循环uniqueHashMap 对象，选取 uniqueHashMap[value]为1的数据
    console.log(Object.keys(uniqueHashMap))
    Object.keys(uniqueHashMap).forEach((val) => {
        finalResult.push(val)
    })

    return finalResult
}

别人的实现

function baseUniq(array, iteratee, comparator) {
  let index = -1
  let includes = arrayIncludes
  let isCommon = true

  const { length } = array
  const result = []
  let seen = result

  if (comparator) {
    isCommon = false
    includes = arrayIncludesWith
  }
  else if (length >= LARGE_ARRAY_SIZE) {
    const set = iteratee ? null : createSet(array)
    if (set) {
      return setToArray(set)
    }
    isCommon = false
    includes = cacheHas
    seen = new SetCache
  }
  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
        }
      }
      if (iteratee) {
        seen.push(computed)
      }
      result.push(value)
    }
    else if (!includes(seen, computed, comparator)) {
      if (seen !== result) {
        seen.push(computed)
      }
      result.push(value)
    }
  }
  return result
}

function union(...arrays) {
  return baseUniq(baseFlatten(arrays, 1, isArrayLikeObject, true))
}

总结

• 算法都是一致的，先合并数组，然后数据去重。只不过去重的方法不一样。我采用的是hashmap的方式，当时有一个问题 Object.keys(array)会将number类型转化为string;lodash使用二层循环来去重，其他没有什么差别