开发经验

一个普通的遍历实现

Posted by w@hidva.com on April 4, 2020

最近在看 Greenplum 代码时发现一个比较有意思的代码片段, 这个代码片段解决了一个比较有意思的问题. 抽象着来说, 便是对于一个长度为 N 的数组 A, 数组 A 中每一个元素自身也是一个数组, 记集合 \(\{ M_1, M_2,..., M_N \}\) 为一个组合, 其中 \(M_i\) 为 A[i] 指向数组中成员之一. 现在需要设计一个过程可以完成对所有组合的遍历工作.

很显然, 对于 N 为编译期常数时这一过程非常简单. 比如 N = 3 时对应的遍历实现:

for (auto m1 : A[0]) {
    for (auto m2 : A[1]) {
        for (auto m3 : A[2]) {
            /* 此时 {m1, m2, m3} 便是一个组合 */
        }
    }    
}

但当 N 为变量时, 这一遍历过程的实现(最起码对我来说)还是挺让人头秃的. 老规矩, 先看下 N = 2 时能不能找到一个通用的遍历实现, 然后再以此类推. 为此我们先看一下一个比较直观的定理1:

对于长度为 2 的数组 A, A[0], A[1] 自身也指向着长度不同的数组. 记集合 \(Q1 = \{(a, b) | a \in [0, L0), b in [0, L1)\}\), \(Q2 = \{j | j \in [0, L0 * L1)\}\). 那么对于 Q1 中任意元素, 在 Q2 中都有且只有一个元素与之对应, 反之亦然.

这里 L0 即 A[0] 指向数组的长度, L1 即 A[1] 指向数组的长度. 该定理的证明也是比较直白的. 我们可以找到一个对应关系:

对于 Q2 中任意一个 j, 另 a = j % L0, b = j / L0, 即 j = a + b * L0

显然此时 (a, b) 形成的集合与 Q1 相等, 定理得证. (emmm, 感觉少了很多东西…

也即对于 N = 2 时, 另一种遍历实现可以是:

for (int j = 0; j < L0 * L1; ++j) {
    auto a = j % L0;
    auto b = j / L0;
    /* 此时 A[0][a], A[1][b] 便是一个组合 */
}

稍作一下结构上的调整, 得到遍历过程 F:

for (int j = 0; j < L0 * L1; ++j) {
    std::vector<int> idxes;
    for (int i = 0; i < length(A); ++i) {
        idxes.push_back(j % length(A[i]));
        j /= length(A[i]);
    }
    /* 此时 A[0][idxes[0]], A[1][idxes[1]] 便是一个组合 */
}

记得当 i = 1, 这里 \(j_1 \% L1\) 实际上便是 \((j_0 / L0) \% L1\), 考虑到 \(j_0\) 总是小于 L0 * L1, 这里 \((j_0 / L0) \% L1\) 便是 \(j_0 / L0\) 了. 另外这里调整后得到的结构看上去是一个通用的结构, 如果我们能证明对于 N > 2 的情况, 如上结构也成立, 那么我们便解出了文章最开始提出的问题了.

所以我们这里考虑下 N = 3 的情况. 对于 A0, A1, A2, 我们暂且把 A0, A1 作为一个整体看待, 即认为他是一个长度为 L0 * L1 的数组 A01. 那么根据定理1可知, 对于 A01, A2 任意一个组合 (a01, a2), 这里 a01, a2 是组合中元素在各自数组中对应的下标, 都有 j = a01 + a2 * (L0 * L1) 与之对应, 并且此时 a01 = j % (L0 * L1). 再次应用定理1, 可得对于任一 a01 取值, 都对应着 A0, A1 的一个组合 (a0, a1), 此时 a01 = a0 + a1 * L0, a0 = a01 % L0, a1 = a01 / L0. 即对于 A0, A1, A2 任一组合 (a0, a1, a2), 有且仅有一个 j = (a0 + a1 * L0 + a2 * (L1 * L2)) 与之对应. 所以 N = 3 时对应的遍历过程可以写为:

for (int j = 0; j < L0 * L1 * L2; ++j) {
    auto a0 = (j % (L0 * L1)) % L0;
    auto a1 = (j % (L0 * L1)) / L0;
    auto a2 = j / (L0 * L1);
    /* 此时 A[0][a0], A[1][a1], A[2][a2] 便是一个组合 */
}

稍作推算便可得 (j % (L0 * L1)) % L0 等于 j % L0. (j % (L0 * L1)) / L0 等于 (j / L0) % L1, 这里我们简单写一下第二个推算过程(怕我再看时忘了==):

  1. 另 x = (j % (L0 * L1)) / L0. 那么:
  2. j % (L0 * L1) = x * L0 + j % (L0 * L1) % L0; 应用推算1可得:
  3. j % (L0 * L1) = x * L0 + j % L0. 以及 x < L1(反证一下 x >= L1 时等式肯定不会成立的便可得). 令 k = j / (L0 * L1), 可得:
  4. j = k * (L0 * L1) + j % (L0 * L1), 即 j = k * (L0 * L1) + x * L0 + j % L0, 即:
  5. j = (k * L1 + x) * L0 + j % L0, 也即:
  6. (k * L1 + x) = j / L0. 再结合之前得到的 x < L1. 可得:
  7. x = (j / L0) % L1.

所以, 上面的遍历过程便可变换为:

for (int j = 0; j < L0 * L1 * L2; ++j) {
    auto a0 = j % L0;
    auto a1 = (j / L0) % L1;
    auto a2 = (j / (L0 * L1)) % L2;
    /* 此时 A[0][a0], A[1][a1], A[2][a2] 便是一个组合 */
}

可以看到这里遍历过程是符合如上遍历过程 F 结构的, 即 F 可以用于 N = 3 的情况. 以此类推可知 F 适用于任何 N 的情况, 也即 F 便是文章开头提出问题的答案.

CATALOG