爱囡囡，爱前端

0%

lodash源码解析：xor家族

发表于 分类于 ， ， ，

本篇继续分析下 xor 家族的方法，xor 方法的主要目的就是实现异或，也就是对称差（symmetric difference）。包括xor、xorBy、xorWith及核心方法 baseXor。

对应源码分析已推到 github 仓库: https://github.com/MageeLin/lodash-source-code-analysis

原理

数学原理

该方法的数学原理其实很简单，两个集合 a 和 b 求对称差的换算方式如下：

a ⊕ b = (a ∧ ¬b) ∨ (¬a ∧ b)

同理，三个集合 a、b、c求对称差的换算方式如下：

a ⊕ b ⊕ c = ((a ∧ ¬b) ∨ (a ∧ ¬c)) ∨ ((b ∧ ¬a) ∨ (b ∧ ¬c)) ∨ ((c ∧ ¬a) ∨ (c ∧ ¬b))

以此类推，n 个集合求对称差时，都可以分成两步，第一步将每一个集合都与所有其他的集合的非求交集，第二步将交集全都并起来。

在 lodash 实现时，第一步将所有 array 都与其他 array 一起 baseDifference 实现 交集，第二步 baseFlatten 展平一层且 baseUniq 去重实现 并。

依赖路径图

xor 家族方法的依赖路径图如下所示:

只需要注意左侧的主要依赖，右侧的依赖在之前的文章中已经分析过。

流程图

xor 家族方法实现时的主要流程图如下所示：

依赖的基础方法

baseXor

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
import baseDifference from './baseDifference.js';
import baseFlatten from './baseFlatten.js';
import baseUniq from './baseUniq.js';

/**
 * `xor`家族方法的基础实现，参数是要检查的每个数组。
 *
 * @private
 * @param {Array} arrays 要检查的每个数组
 * @param {Function} [iteratee] iteratee 调用每个元素
 * @param {Function} [comparator] comparator 调用每个元素
 * @returns {Array} 返回过滤值后的新数组
 */
function baseXor(arrays, iteratee, comparator) {
  // 如果arrays长度为1，则直接调用 baseUniq 去重返回
  const length = arrays.length;
  if (length < 2) {
    return length ? baseUniq(arrays[0]) : [];
  }
  let index = -1;
  const result = new Array(length);

  // 迭代arrays
  while (++index < length) {
    const array = arrays[index];
    let othIndex = -1;

    // 迭代arrays中的其他array
    while (++othIndex < length) {
      if (othIndex != index) {
        // 核心步骤1：把result的对应位置设为用baseDifference比较后的array
        result[index] = baseDifference(
          result[index] || array,
          arrays[othIndex],
          iteratee,
          comparator
        );
      }
    }
  }
  // 核心步骤2：把结果展平一层，也就是把每一个 array 展开
  // 再调用 baseUniq 去重返回
  return baseUniq(baseFlatten(result, 1), iteratee, comparator);
}

export default baseXor;

xor 家族

xor 家族都是调用了 baseXor 核心方法。

xor

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 baseXor from './.internal/baseXor.js';
import isArrayLikeObject from './isArrayLikeObject.js';

/**
 * 创建一个给定数组唯一值的数组，
 * 对给定的多个数组使用[symmetric difference](https://en.wikipedia.org/wiki/Symmetric_difference)，
 * 创建出一个唯一值数组。
 * 返回值的顺序取决于在数组的出现顺序
 *
 * @since 2.4.0
 * @category Array
 * @param {...Array} [arrays] 要检查的数组
 * @returns {Array} 返回过滤后的新数组
 * @see difference, union, unionBy, unionWith, without, xorBy, xorWith
 * @example
 *
 * xor([2, 1], [2, 3])
 * // => [1, 3]
 */
function xor(...arrays) {
  // 直接调用baseXor，并且进行了过滤，只有数组类型的参数才可以进行比较
  return baseXor(arrays.filter(isArrayLikeObject));
}

export default xor;

xorBy

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 baseXor from './.internal/baseXor.js';
import isArrayLikeObject from './isArrayLikeObject.js';
import last from './last.js';

/**
 * 此方法类似 `xor` ，但是接受 `iteratee`（迭代器）参数，
 * `iteratee` 调用每一个 array 的每一个值，用生成的新值进行比较。
 * `iteratee` 调用1个参数：(value).
 *
 * @since 4.0.0
 * @category Array
 * @param {...Array} [arrays] 要检查的数组
 * @param {Function} iteratee iteratee 调用每个元素
 * @returns {Array} 返回过滤值后的新数组
 * @see difference, union, unionBy, unionWith, without, xor, xorWith
 * @example
 *
 * xorBy([2.1, 1.2], [2.3, 3.4], Math.floor)
 * // => [1.2, 3.4]
 */
function xorBy(...arrays) {
  // 取最后一个参数为iteratee
  let iteratee = last(arrays);
  // 如果最后一个参数仍然是数组，那iteratee就为undefined
  if (isArrayLikeObject(iteratee)) {
    iteratee = undefined;
  }
  // 过滤参数并调用baseXor
  return baseXor(arrays.filter(isArrayLikeObject), iteratee);
}

export default xorBy;

xorWith

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
import baseXor from './.internal/baseXor.js';
import isArrayLikeObject from './isArrayLikeObject.js';
import last from './last.js';

/**
 * 此方法类似 `xor`，但是它接受一个 `comparator`（比较器）参数 ，
 * `comparator` 调用每个 `array` 的每个元素进行比较。
 * 返回值的顺序取决于在数组的出现顺序。
 * `comparator` 调用2个参数：(arrVal, othVal).
 *
 * @since 4.0.0
 * @category Array
 * @param {...Array} [arrays] 要检查的每个数组
 * @param {Function} [comparator] comparator 调用每个元素
 * @returns {Array} 返回过滤值后的新数组
 * @see difference, union, unionBy, unionWith, without, xor, xorBy
 * @example
 *
 * const objects = [{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }]
 * const others = [{ 'x': 1, 'y': 1 }, { 'x': 1, 'y': 2 }]
 *
 * xorWith(objects, others, isEqual)
 * // => [{ 'x': 2, 'y': 1 }, { 'x': 1, 'y': 1 }]
 */
function xorWith(...arrays) {
  // 取最后一个参数为 comparator
  let comparator = last(arrays);
  // 换了一种比较方式，如果comparator不是function类型，就设为undefined
  comparator = typeof comparator === 'function' ? comparator : undefined;
  // 过滤参数并调用baseXor
  return baseXor(arrays.filter(isArrayLikeObject), undefined, comparator);
}

export default xorWith;

原生实现

原生实现时可以更简单，利用对称差的结合律:

a ⊕ b ⊕ c ⊕ d = ((a ⊕ b) ⊕ c) ⊕ d

直接可以用 reduce，用之前的对称差结果和下一个数组求对称差即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function xor(...arrays) {
  let result = arrays.reduce((arrayAcc, arrayCur) => {
    let resultCur = []; // 本次迭代的结果数组

    // 从acc中找到cur中没有的元素
    arrayAcc.forEach((item) => {
      if (arrayCur.indexOf(item) < 0) {
        resultCur.push(item);
      }
    });

    // 从cur中找到acc中没有的元素
    arrayCur.forEach((item) => {
      if (arrayAcc.indexOf(item) < 0) {
        resultCur.push(item);
      }
    });

    return resultCur;
  });
  // 去重返回
  return [...new Set(result)];
}

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇