爱囡囡，爱前端

0%

lodash源码解析：sorted家族

发表于 分类于 ， ， ，

本篇分析下sorted家族的方法，该系列的方法主要是用来确定向已排序数组中插入 value 的索引。包括sortedIndex、sortedLastIndex、sortedIndexOf、sortedLastIndexOf、sortedIndexBy、sortedLastIndexBy、sortedUniq、sortedUniqBy以及核心方法baseSortedIndex、baseSortedIndexBy、baseSortedUniq。

首先学习一个二分查找的实例，这也是sortedIndex系列方法用到的核心算法。顺便分析依赖到的 lodash 方法eq。

具体的依赖路径图如下所示：

二分查找

二分查找（Binary Search）是一种查找算法，用来在一个数组中查找指定的元素。注意这个数组需要是一个有序数组才有效，时间复杂度为O(log2n)。下面是一个二分查找与线性查找的对照图。

最普通的二分查找

下面给出最普通的二分查找的 JS 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binarySearch(array, value) {
  let low = 0; // 数组最小索引值
  let high = array.length - 1; // 数组最大索引值
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (value == array[mid]) {
      // value等于中间值，查找到了结果
      return mid;
    } else if (array[mid] < value) {
      // value大于中间值，挪动low
      low = mid + 1;
    } else if (value < array[mid]) {
      // value小于中间值，挪动high
      high = mid - 1;
    }
  }
}

按照示例图给的数据进行计算：

1
2
const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59];
binarySearch(array, 37);
迭代 low high mid array[mid]
1 0 16 8 23
2 9 16 12 41
3 9 11 10 31
4 11 11 11 37

但是这个算法对于某些情况是有一些问题的，当数组中要寻找的 value 存在有多个重复时，他只能随缘找到其中一个，无法找到最左边或者最右边那个。但是 sorted 算法中是需要这种能力的，所以需要进化！

二分算法寻找左侧边界

先放出寻找左侧边界代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearchLeft(array, value) {
  let low = 0;
  let high = array.length; // 区别1
  while (low < high) {
    // 区别2
    let mid = Math.floor((low + high) / 2);
    if (value == array[mid]) {
      high = mid; // 区别3
    } else if (array[mid] < value) {
      low = mid + 1;
    } else if (value < array[mid]) {
      high = mid; // 区别4
    }
  }
  return low;
}

与普通二分算法的区别是以下几点：

  1. 初始 high 给的是 array.length，没有减 1。
  2. 判断条件是 < ，而不是 <=。
  3. 当 value == array[mid]时，并不立即返回 mid，而是继续向左查找。
  4. 当 value < array[mid]时，high = mid，而不是 high = mid - 1。

1 和 4 是一样的原因，不需要减 1 就是因为 2 中判断条件变成了<而不是<=。第 3 条是寻找左侧边界的关键，如果发现了与value相等的mid值，不要立即返回，而是把这里设为high，继续向左寻找有没有更小的，直到找到最左侧的位置。

有同学可能会问为啥不只改第3条，从而继续用<=的版本。这是因为如果value比array中的所有值都大时，low会比最大索引还大，导致越界。

二分算法寻找右侧边界

继续放出寻找右侧边界代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearchRight(array, value) {
  let low = 0;
  let high = array.length; // 区别1
  while (low < high) {
    // 区别2
    let mid = Math.floor((low + high) / 2);
    if (value == array[mid]) {
      low = mid + 1; // 区别3
    } else if (array[mid] < value) {
      low = mid + 1;
    } else if (value < array[mid]) {
      high = mid; // 区别4
    }
  }
  return low;
}

寻找右侧边界和左侧同理，只不过区别 3 变成了 low = mid + 1。

依赖的内置方法

两个依赖的核心内置方法都是用到了二分查找算法的变形。

baseSortedIndex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import baseSortedIndexBy from './baseSortedIndexBy.js';
import isSymbol from '../isSymbol.js';

/** 用作最大长度和数组索引的引用 */
// 4294967295 == 0xffffffff，8字节，64位
const MAX_ARRAY_LENGTH = 4294967295;
// 4294967295 >>> 1 = 2147483647 === 0x7fffffff，
// 也就是逻辑右移1位
const HALF_MAX_ARRAY_LENGTH = MAX_ARRAY_LENGTH >>> 1;

/**
 * `sortedIndex` 和 `sortedLastIndex`的基础实现，对`array`执行二进制搜索，
 * 决定`value`应该在`array`中的插入的`index`，确保不打乱原数组顺序
 *
 * @private
 * @param {Array} array 要检查的排序后数组
 * @param {*} value 要计算的值
 * @param {boolean} [retHighest] 标志是否返回最大的匹配索引
 * @returns {number} 返回 `value`应该在`array`中插入的位置 `index`
 */
function baseSortedIndex(array, value, retHighest) {
  // 初始化变量
  let low = 0;
  // array为空时，high为0，否则为length
  let high = array == null ? low : array.length;

  // 当value是number类型
  if (
    typeof value === 'number' &&
    value === value &&
    high <= HALF_MAX_ARRAY_LENGTH
  ) {
    // 当low < high时循环
    while (low < high) {
      // 逻辑右移一位相当于变小一半
      const mid = (low + high) >>> 1;
      // computed是最中间的变量
      const computed = array[mid];
      // 当中间变量小于value时，就去后半个区间寻找
      if (
        computed !== null &&
        !isSymbol(computed) &&
        (retHighest ? computed <= value : computed < value)
      ) {
        low = mid + 1;
      } else {
        // 当中间变量大于等于value，就去前半个区间寻找
        high = mid;
      }
    }
    // 最后low>=high了，就返回high
    return high;
  }
  // 如果不是数字类型，不是null，或者数字值超过了HALF_MAX_ARRAY_LENGTH，就调用baseSortedIndexBy并返回
  return baseSortedIndexBy(array, value, (value) => value, retHighest);
}

export default baseSortedIndex;

baseSortedIndexBy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import isSymbol from '../isSymbol.js';

/** 用作最大长度和数组索引的引用*/
// 4294967295 == 0xffffffff，8字节，64位
const MAX_ARRAY_LENGTH = 4294967295;
// 4294967295 == 0xfffffffe
const MAX_ARRAY_INDEX = MAX_ARRAY_LENGTH - 1;

/**
 * `sortedIndexBy` 和 `sortedLastIndexBy`方法的基础实现，
 * 对`array`的每个元素调用了`iteratee`后和`value`比较来计算`value`在已排序数组中的索引。
 * `iteratee`调用一个参数(`value`)
 *
 * @private
 * @param {Array} array 要检查的已排序数组
 * @param {*} value 要计算的值
 * @param {Function} iteratee 每个元素调用的iteratee
 * @param {boolean} [retHighest] 标志是否返回最大的匹配索引
 * @returns {number} 返回 `value`应该在`array`中插入的位置 `index`
 */
function baseSortedIndexBy(array, value, iteratee, retHighest) {
  // 初始化变量low，high
  let low = 0;
  let high = array == null ? 0 : array.length;
  if (high == 0) {
    return 0;
  }

  // 对value进行iteratee迭代
  value = iteratee(value);

  // 只有NaN !== NaN 这一种情况满足value !== value 为真
  const valIsNaN = value !== value;
  // 是否未null
  const valIsNull = value === null;
  // 是否为symbol
  const valIsSymbol = isSymbol(value);
  // 是否为undefined
  const valIsUndefined = value === undefined;

  // 二分查找
  while (low < high) {
    let setLow;
    const mid = Math.floor((low + high) / 2);
    // 把中间值用iteratee处理成computed
    const computed = iteratee(array[mid]);
    // 是否已定义
    const othIsDefined = computed !== undefined;
    // 是否为null
    const othIsNull = computed === null;
    // 是否与自身相等
    const othIsReflexive = computed === computed;
    // 是否是symbol
    const othIsSymbol = isSymbol(computed);

    // 这里都是在处理 简单的大小比较 解决不了的比较过程
    if (valIsNaN) {
      setLow = retHighest || othIsReflexive;
    } else if (valIsUndefined) {
      setLow = othIsReflexive && (retHighest || othIsDefined);
    } else if (valIsNull) {
      setLow = othIsReflexive && othIsDefined && (retHighest || !othIsNull);
    } else if (valIsSymbol) {
      setLow =
        othIsReflexive &&
        othIsDefined &&
        !othIsNull &&
        (retHighest || !othIsSymbol);
    } else if (othIsNull || othIsSymbol) {
      setLow = false;
    } else {
      // 这里才是最普适性的处理，上面都在处理特殊情况
      // 如果从左向右查，就是<=，如果从右向左查，就是<
      setLow = retHighest ? computed <= value : computed < value;
    }
    // 二分查找核心
    if (setLow) {
      // 比中间值大，就修改low
      low = mid + 1;
    } else {
      // 比中间值小，就修改high
      high = mid;
    }
  }
  return Math.min(high, MAX_ARRAY_INDEX);
}

export default baseSortedIndexBy;

baseSortedUniq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import eq from '../eq.js';

/**
 * `sortedUniq` and `sortedUniqBy`的基础实现
 *
 * @private
 * @param {Array} array 要检查的数组
 * @param {Function} [iteratee] `iteratee`调用每个元素
 * @returns {Array} 返回新的数组副本
 */
function baseSortedUniq(array, iteratee) {
  // 初始化
  let seen;
  let index = -1;
  let resIndex = 0;

  // 取到array的长度
  const { length } = array;
  const result = [];

  // 迭代
  while (++index < length) {
    // value是每个元素，computed为转换后的该元素
    const value = array[index],
      computed = iteratee ? iteratee(value) : value;
    // 当index为0 或者 computed!== seen
    // seen其实是上次的computed
    if (!index || !eq(computed, seen)) {
      // 把本次的computed放到seen中
      seen = computed;
      // 只有跟前一个元素不重复的才放到result中
      result[resIndex++] = value === 0 ? 0 : value;
    }
  }
  return result;
}

export default baseSortedUniq;

依赖的 lodash 方法

eq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 在两个值之间执行
 * [`SameValueZero`](http://ecma-international.org/ecma-262/7.0/#sec-samevaluezero)比较
 * 决定两个值是否相等
 *
 * @since 4.0.0
 * @category Lang
 * @param {*} value 要比较的值
 * @param {*} other 要比较的另一个值
 * @returns {boolean} 当两个值相等时返回`true`，否则返回`false`
 * @example
 *
 * const object = { 'a': 1 }
 * const other = { 'a': 1 }
 *
 * eq(object, object)
 * // => true
 *
 * eq(object, other)
 * // => false
 *
 * eq('a', 'a')
 * // => true
 *
 * eq('a', Object('a'))
 * // => false
 *
 * eq(NaN, NaN)
 * // => true
 */
function eq(value, other) {
  // 只有当values严格相等 或者 两个值都为null时，才会返回ture
  // 其余都返回false
  return value === other || (value !== value && other !== other);
}

export default eq;

sorted 家族

下面是六个sorted系列方法的解析。

sortedIndex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import baseSortedIndex from './.internal/baseSortedIndex.js';

/**
 * 使用二进制检索来决定应该插入到数组中的`value`的最小的索引位置，以保证array的排序。
 *
 * @since 0.1.0
 * @category Array
 * @param {Array} array 要检查的已排序数组。
 * @param {*} value 要计算的值
 * @returns {number} 返回 `value`应该在`array`中插入的位置 `index`。
 * @example
 *
 * sortedIndex([30, 50], 40)
 * // => 1
 */
function sortedIndex(array, value) {
  // 其实是调用 baseSortedIndex(array, value, false)
  return baseSortedIndex(array, value);
}

export default sortedIndex;

sortedLastIndex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import baseSortedIndex from './.internal/baseSortedIndex.js';

/**
 *
 * 此方法类似于`sortedIndex`，但是返回 `value` 是在 `array` 中尽可能大的索引位置`index`。
 *
 * @since 3.0.0
 * @category Array
 * @param {Array} array 要检查的已排序数组。
 * @param {*} value 要计算的值
 * @returns {number} 返回 `value`应该在`array`中插入的位置 `index`。
 *  into `array`.
 * @example
 *
 * sortedLastIndex([4, 5, 5, 5, 6], 5)
 * // => 4
 */
function sortedLastIndex(array, value) {
  // 调用 baseSortedIndex(array, value, true)
  return baseSortedIndex(array, value, true);
}

export default sortedLastIndex;

sortedIndexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import baseSortedIndex from './.internal/baseSortedIndex.js';
import eq from './eq.js';

/**
 * 这个方法类似 `indexOf`，但是它是在已经排序的数组`array`上执行二进制检索。
 *
 * @since 4.0.0
 * @category Array
 * @param {Array} array 要检查的数组
 * @param {*} value 要搜索的值
 * @returns {number} 返回匹配值的`index`，否则返回`-1
 * @example
 *
 * sortedIndexOf([4, 5, 5, 5, 6], 5)
 * // => 1
 */
function sortedIndexOf(array, value) {
  // 先取到数组的length
  const length = array == null ? 0 : array.length;
  // 数组有内容就处理
  if (length) {
    // 跟sortedIndex调用方式一样
    const index = baseSortedIndex(array, value);
    // 但是多了一步处理，就是数组的该项与value是否相等
    // 如果不相等说明数组中不存在这个值，就返回-1
    if (index < length && eq(array[index], value)) {
      // 确定查到数组中有该值，返回index
      return index;
    }
  }
  // 数组没内容时返回-1
  return -1;
}

export default sortedIndexOf;

sortedLastIndexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import baseSortedIndex from './.internal/baseSortedIndex.js';
import eq from './eq.js';

/**
 * 这个方法类似`lastIndexOf`，但是它是在已经排序的`array`上执行二进制检索。
 *
 * @since 4.0.0
 * @category Array
 * @param {Array} array 要检查的数组
 * @param {*} value 要搜索的值
 * @returns {number} 返回匹配值的`index`，否则返回`-1
 * @example
 *
 * sortedLastIndexOf([4, 5, 5, 5, 6], 5)
 * // => 3
 */
function sortedLastIndexOf(array, value) {
  // 先取到数组的length
  const length = array == null ? 0 : array.length;
  if (length) {
    // 跟sortedLastIndex调用方式一样，但是减1
    const index = baseSortedIndex(array, value, true) - 1;
    // 如果不相等说明数组中不存在这个值，就返回-1
    if (eq(array[index], value)) {
      // 确定查到数组中有该值，返回index
      return index;
    }
  }
  return -1;
}

export default sortedLastIndexOf;

sortedIndexBy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import baseSortedIndexBy from './.internal/baseSortedIndexBy.js';

/**
 * 这个方法类似`sortedIndex`，但是它接受一个 `iteratee` （迭代函数），
 * 调用`array`的每一个元素，返回结果和`value` 比较来计算排序。
 * iteratee 会传入一个参数：(value)。
 *
 * @since 4.0.0
 * @category Array
 * @param {Array} array 要检查的已排序数组。
 * @param {*} value 要计算的值
 * @param {Function} iteratee 每个元素调用的iteratee迭代函数
 * @returns {number} 返回`value`应该在`array`中插入的索引位置 `index`。
 * @example
 *
 * const objects = [{ 'n': 4 }, { 'n': 5 }]
 *
 * sortedIndexBy(objects, { 'n': 4 }, ({ n }) => n)
 * // => 0
 */
function sortedIndexBy(array, value, iteratee) {
  // 调用核心方法baseSortedIndexBy(array, value, iteratee)
  return baseSortedIndexBy(array, value, iteratee);
}

export default sortedIndexBy;

sortedLastIndexBy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import baseSortedIndexBy from './.internal/baseSortedIndexBy.js';

/**
 * 这个方法类似`sortedLastIndex`，但是它接受一个 `iteratee` （迭代函数），
 * 调用`array`的每一个元素，返回结果和`value`比较来计算排序。
 * iteratee 会传入一个参数：(value)。
 *
 * @since 4.0.0
 * @category Array
 * @param {Array} array 要检查的已排序数组。
 * @param {*} value 要计算的值
 * @param {Function} iteratee 每个元素调用的iteratee迭代函数
 * @returns {number} 返回`value`应该在`array`中插入的索引位置 `index`。
 * @example
 *
 * const objects = [{ 'n': 4 }, { 'n': 5 }]
 *
 * sortedLastIndexBy(objects, { 'n': 4 }, ({ n }) => n)
 * // => 1
 */
function sortedLastIndexBy(array, value, iteratee) {
  return baseSortedIndexBy(array, value, iteratee, true);
}

export default sortedLastIndexBy;

sortedUniq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import baseSortedUniq from './.internal/baseSortedUniq.js';

/**
 * 这个方法类似`uniq`，但是它只对已排序数组有效。
 * 如果输入的数组确定是已排序的，那么`sortedUniq` 要比 `uniq`更快。
 *
 * @since 4.0.0
 * @category Array
 * @param {Array} array 要检查的数组
 * @returns {Array} 返回新的数组副本
 * @example
 *
 * sortedUniq([1, 1, 2])
 * // => [1, 2]
 */
function sortedUniq(array) {
  // 当数组==null或者长度为0，就返回[]
  return array != null && array.length
    ? // 否则调用baseSortedUniq
      baseSortedUniq(array)
    : [];
}

export default sortedUniq;

sortedUniqBy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import baseSortedUniq from './.internal/baseSortedUniq.js';

/**
 * 这个方法类似`uniqBy`，但是它会对已排序数组进行速度优化。
 *
 * @since 4.0.0
 * @category Array
 * @param {Array} array 要检查的数组
 * @param {Function} iteratee 每个元素调用的iteratee迭代函数
 * @returns {Array} 返回新的数组副本
 * @example
 *
 * sortedUniqBy([1.1, 1.2, 2.3, 2.4], Math.floor)
 * // => [1.1, 2.3]
 */
function sortedUniqBy(array, iteratee) {
  // 当数组==null或者长度为0，就返回[]
  return array != null && array.length
    ? // 否则调用baseSortedUniq(array, iteratee)
      baseSortedUniq(array, iteratee)
    : [];
}

export default sortedUniqBy;
👆 全文结束，棒槌时间到 👇