Algorithms III

约 8178 个字 117 行代码 5 张图片 预计阅读时间 29 分钟

九、Randomized Algorithm

简单来说，如果一个算法的行为不仅通过输入决定，还由随机数生成器产生的数值决定，就称这个算法是随机的。这也就是我们在课上讲的算法会产生随机的决策。随机算法可以有效避免最坏情况，其一般分为两种算法：

• 拉斯维加斯算法/Las Vegas Algorithm：这种算法总是返回正确的结果，但是运行时间是随机的，比如快速排序的随机化版本，通过随机选择 pivot 来加速排序；
• 蒙特卡罗算法/Monte Carlo Algorithm：这种算法总是在有限时间内返回结果，但是结果不一定是正确的，比如下面的雇佣问题的几个解法。

另外，由于很多时候输入的数据也是随机的，我们就可以使用随机分析来分析算法的性能，我们一般使用指示器随机变量和期望值分析算法的平均情况开销。

注意，如果我们使用平均情况分析分析某个算法的开销，分析出来预期的开销为 \(T_1\)，那么存在某些情况，执行该算法需要的时间可以大于或小于这个分析出来的开销，这和摊还分析很相似。（摊还分析分析出来的复杂度考虑的是全局的耗时，保证总体的复杂度不超过这一个边界，但是允许某几次运算超过这个边界）

1. 雇佣问题

题面：我们从猎头公司雇佣一位秘书，每次面试一个人，连续 \(N\) 次面试，面试的花费远远小于雇佣的花费 \(C_i \ll C_{h}\)，考虑一下面试和雇佣的成本。

如果我们在面试的过程中一共雇佣了 \(M\) 个候选者，那么总体的开销为 \(O(MC_h + NC_i)\)，我们的目标是找到一个最优的策略，使得总体的开销最小。

方案 1：从头面试到尾，如果每次面试的候选者的能力都比当前雇佣的人要好，就雇佣这个候选者：

typedef struct {int score;} Person;
int Hiring (Person C[], int N) {
    int best = 0;
    int best_score = 0;

    for (int i = 1; i <= N; i++){
        if (interview(C, i) > best_score) {
            best = i;
            best_score = interview(C, i);
        }
    }
    return best;
}

最坏的情况是候选者按照能力递增的顺序进行面试，这时总体的开销为 \(O(NC_h + NC_i)\)，这是我们进行最差情况分析的结果。如果使用平均情况分析，首先我们规定所有的候选者等可能地具有最佳能力，知道第 \(i\) 个候选者被雇佣的概率为 \(\dfrac{1}{i}\)，这是因为这个候选者一定会比前面的所有候选者都优秀，所以可以得到总的期望开销为 \(O(C_h\ln N + NC_i)\)。但是我们不可避免地遇见最差情况，这就需要随机化算法。

方案 2：在开始雇佣之前对数据进行随机排列，这样就可以得到随机排序的数据，从而避免了最坏情况，但是随机排列数据需要额外开销。

typedef struct {int score, priority;} Person;

int compare (const Person *a, const Person *b) {
    return b->priority - a->priority;
}

void shuffle (Person C[], int N) {
    for (int i = 1; i <= N; i++) 
        C[i].priority = 1 + rand() % (N * N * N);
    qsort(C, N, sizeof(Person), compare);
}

int Hiring (Person C[], int N) {
    int best = 0;
    int best_score = 0;

    shuffle(C, N);

    for (int i = 1; i <= N; i++){
        if (interview(C, i) > best_score) {
            best = i;
            best_score = interview(C, i);
        }
    }
    return best;
}

可以看到我们其实只需要额外设计一个 shuffle 操作来进行对数据的随机排列，大致思路就是对候选人数组的每一个元素预先赋予一个随机的优先级，然后按照优先级排序。我们这里使用的其实是伪随机数生成器/PRNG，PRNG 其实是一个确定性算法，但是生成的值在统计上看起来是随机的。假定数组的优先级都是唯一的，这样的算法就可以得到一个基于原数据的均匀随机排序。

但是仅仅使用这样的算法并不足够，首先我们没有证明这样打乱算法确实有效：也就是产生数据存在两个相同的优先级的概率很低，其次，我们也没有证明如果产生的数据优先级两两不同，那么我们产生的数据就确实是均匀随机排序。下面分别给出证明：

证明

首先证明：所有元素的优先级唯一的概率至少是 \(1 - \dfrac1n\)：这是很简单的概率问题，首先定义事件 \(S_i\) 代表索引为 \(i\) 的元素的优先级是唯一的，那么我们有

\[\begin{align} P[S_1 \cap S_2 \cap \cdots \cap S_n] &= P[S_1] \cdot P[S_2 \vert S_1] \cdots P[S_n\vert S_1 \cap S_2 \cap \cdots \cap S_{n-1}] \\ &= 1 \cdot \left(1 - \frac{1}{n^3}\right) \cdots \left(1 - \frac{n-1}{n^3}\right) \\ &\geq 1 \cdot \left(1 - \frac{n}{n^3}\right) \cdots \left(1 - \frac{n}{n^3}\right) \\ &= \left(1 - \frac{1}{n^2}\right)^n \geq 1 - \frac{1}{n} \end{align}\]

其次证明这个过程等可能地产生一个 \(1\) 到 \(n\) 的每一种排列，证明产生任何一种排列的概率为 \(\dfrac{1}{n!}\)。感兴趣的看算法导论去吧，没时间写了 QAQ

另外，本算法还可以简单修改以处理出现优先级不唯一的情况。只需要在优先级相同时，将优先级相同的元素内再进行一次的随机优先级分配再排序即可。

方案 3：上面介绍的算法都是离线算法，也就是在处理数据之前需要知道所有的输入数据，虽然能够保证答案的正确性，但是不能保证效率，这里可以设计一个只雇佣一次的算法。大概想法为：我先定一个超参数 k，然后在前 k 个人中找到最好的，然后在后面的人中找到比前 k 个人中最好的还好的第一个人，雇佣这个人并结束面试，不然就选择最后一个被面试的人。

int online_hiring (Person C[], int N, int k) {
    int best = N;
    int best_score = 0;

    for (int i = 1; i <= k; i++) {
        if (interview(C, i) > best_score) {
            best_score = interview(C, i);
        }
    }

    for (int i = k + 1; i <= N; i++) {
        if (interview(C, i) > best_score) {
            best = i;
            break;
        }
    }

    return i;
}

这个算法不能保证我们一定会雇佣到能力最好的人，有两个阻碍：一个是可能能力最好的人在前 k 个，作为训练集被学习去了；另一个就是可能这个能力最好的人前面有人提前被雇佣了，这个人错失良机。下面计算对于给定的 k，能够雇佣到最好的人的概率：

记 \(S\) 为我们雇佣到最好的候选者这个事件，并且记 \(S_i\) 为事件第 i 位候选者的能力最好并且我们雇佣了这位候选者，这个事件发生基于两个子事件：

• 事件 \(A_i\)：能力最佳的候选者恰好在位置 \(i\)；
• 事件 \(B_i\)：在位置 \(k+1\) 到 \(i-1\) 的候选者不会被雇佣。

每一个事件 \(A_i\) 和 \(B_i\) 是相互独立的，所以我们可以计算概率：

\[ \begin{align} P[S] &= \sum_{i=k+1}^N P[S_i] = \sum_{i=k+1}^N P[A_i \cap B_i] \\ &= \sum_{i=k+1}^N P[A_i] \cdot P[B_i] = \sum_{i=k+1}^N \frac{1}{N} \cdot \frac{k}{i-1} = \frac{k}{N} \sum_{i=k}^{N-1} \frac{1}{i} \end{align} \]

其中 \(P[B_i] = \dfrac{k}{i-1}\) 是因为我们必须让前 \(i - 1\) 个元素中最大的元素在前 \(k\) 个元素内出现，这样我们才可以保证 \(k + 1\) 到 \(i-1\) 的元素不会被雇佣。使用定积分进行放缩：

\[ \int_k^N \dfrac{1}{x} \mathrm{d}x \le \sum\limits_{i=k}^{N-1} \dfrac{1}{i} \le \int_{k-1}^{N-1} \dfrac{1}{x}\mathrm{d}x \]

因此

\[ \frac{k}{N} \ln(\frac{N}{k}) \le P[S] \le \frac{k}{N} \ln (\frac{N - 1}{k - 1}) \]

为了选择最好的 \(k\)，我们需要做一点点简单的最优化问题。注意到

\[ k_{\text{opt}} = \operatorname*{argmin}\limits_{1\leq k\leq N} f(k) = \operatorname*{argmin}\limits_{1\leq k\leq N}\dfrac{k}{N}\ln\dfrac{N}{k} = \frac{N}{e}, \]

所以上述算法得到最优候选人的概率为 \(\dfrac{1}{e}\)。因此这个算法是一个蒙特卡罗算法/Monte Carlo Algorithm，这样的算法是非常高效的，但是不能保证一定会有一个正确的输出。因为我们只能保证我们雇佣到最好的候选者的概率至少为 \(\dfrac{1}{e}\)。

2. 随机化快速排序

回忆一下传统的快速排序：

void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

int partition(int nums[], int left, int right) {
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) j--;
        while (i < j && nums[i] <= nums[left]) i++;
        swap(nums, i, j);
    }
    swap(nums, i, left);
    return i;
}

void quickSort(int nums[], int left, int right) {
    if (left >= right) return;
    int pivot = partition(nums, left, right);
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

传统的快速排序是一种确定性排序，平均时间复杂度为 \(\Theta(n\log n)\)，最坏情况下时间复杂度为 \(\Theta(n^2)\)，这时候就退化成冒泡了。

回忆一下学过的优化快速排序的方法，关键优化是优化选择哨兵/枢轴/Pivot 的方法，一种方法是选择最左侧、最右侧和中间的三个元素的中位数作为枢轴，这显著提升了算法的鲁棒性。这启示我们选择一个比较靠中间的数来优化快速排序的分治过程。

首先定义快速排序的中央分离器/Central Spilter：一个将左右集合分开并且使得左右的集合至少有 ¼ 的元素的分割器。这样我们可以修改快速排序算法，使得其在每次递归之前都能选择一个中央分离器，但是枢轴的选择是随机的，我们需要考虑选择出一个中央分离器的期望选择次数。

首先，我们意识到，每次随机选择一个枢轴，我们都有 ½ 的概率选择出一个中央分离器，所以如果我们一直选择枢轴，直到选择到一个中央分离器，我们的期望选择次数是 2。

由于快速排序是一个分治策略，我们通过考虑分治的子问题数目与规模来估计：我们的分治策略利用枢轴将所有的数字分成了很多份子问题，通过考察子问题的规模进行分类，如果一个子问题 \(S\) 的规模满足 \(N\cdot \left(3/4\right)^{j+1} \leq |S| < N\cdot \left(3/4\right)^{j}\)，那么就称这个子问题是类型为 \(j\) 的。首先，如果某个问题 \(T\) 类型为 \(j\)，那么使用调整后的快速排序算法，其子问题的规模在 \(\dfrac{3}{4}\lvert T \rvert\) 和 \(\dfrac{1}{4}\lvert T \rvert\) 之间，因此每一个问题和其子问题不相交，而且同一类型的问题的子问题间不相交，这就有一个重要的性质：所有同一类型的子问题之并包含于原问题，这就是我们分析的基础。

上面的性质蕴含一个结论：所有类型为 \(j\) 的问题的数目不超过 \((4/3)^{j+1}\)，这样所有类型为 \(j\) 的子问题规模之和不超过 \(N\cdot (4/3)\)，期望下处理这些问题的复杂度为 \(O(N)\)。并且我们一共有 \(O(\log_{4/3}N)\) 种类型的问题，所以总的期望复杂度为 \(O(N\log N)\)。

对于 MAX 3-SAT 问题，我们使用一种最简单的随机算法来尝试求解：对于每一个字面量，我们在 0 和 1 之间随机选择一个值，然后计算这样的字面量使得有多少个字句可以成立。根据概率论，每一个字句都有 ⅞ 的概率成立，⅛ 的概率成立。这样我们的期望是有总数的 ⅞ 的字句成立，而最优解的字句成立数目一定小于字句的总数，因此我们得到一个 8/7 的近似比。

十、Parallel Algorithm

1. 并行算法基本模型

加速比/Speedup：使用 \(p\) 个处理器的并行算法相对于使用一个处理器时的性能提升比例，也就是 \(S_p = \dfrac{T_1}{T_p}\)。其中 \(T_1\) 是使用一个处理器时的执行时间，\(T_p\) 是使用 \(p\) 个处理器时的执行时间。

工作量/Work：需要完成该并行算法的单位时间总操作数目，也就是如果只有一个处理器需要的执行时间，\(W = T_1\)。

深度/关键路径长度/Depth：并行算法中最长的一个依赖关系链的长度，也就是理想情况下有无穷个处理器需要的执行时间 \(D = T_{\infty}\)。

布伦特定理/Brent's Theorem：对于一个并行算法，如果我们有 \(p\) 个处理器，总的工作量为 \(W\)，深度/关键路径长度为 \(D\)，那么这个并行算法的并行时间有上下界：

\[ \frac{W}{p} \leq T_p \leq \frac{W}{p} + D \text{ or } \frac{W}{p} \leq T_p \leq \frac{W - D}{p} + D \]

WD-presentation Sufficiency Theorem：所有 WD 模型的算法都可以被任何 \(P\) 个处理器以时间 \(O(W/P + D)\) 执行，并要求使用和 WD 模型同样的并发写入惯例。

2. 前缀和问题

前缀和问题：给定一个长度为 \(n\) 的数组 \(A\)，我们需要设计并行算法求出 \(A\) 的前 \(k\) 个元素的和，其中 \(k\) 取遍 \(1\) 到 \(n\)。

前缀和问题完全基于之前计算的并行求和问题，我们使用平衡二叉树已经算出来了这个数组的所有元素的和，下面根据已经计算出来的结果计算前缀和。

注意到每一个非叶子节点都存着很多已经计算好的数据，每一个节点都是其子树求和问题的解，我们的并行计算需要好好利用这些求好的数据，下面引入必要的记号：\(B(h, i)\) 表示深度为 \(h\) 的第 \(i\) 个节点的值，这里的深度从底向上计算，深度为 \(0\) 的节点为输入节点；\(C(h, i)\) 表示深度为 \(h\) 的第 \(i\) 个节点的前缀和，这里的深度计算规则和 \(B(h, i)\) 一模一样，深度为 \(0\) 的节点为输出节点。按照下面约定好的规则，我们可以计算出所有的前缀和：

• 首先，\(C(h, i) = \sum\limits_{k=1}^{\alpha} A(k)\)，其中 \(\alpha\) 是节点 \(B(h, i)\) 的最右下角的叶子的索引 \(i\)；
• 如果 \(i = 1\)，那么 \(C(h, i) = B(h, i)\)，这个节点代表其子树叶子值 \(B(0, j)\) 的和，我们也将最左边的路径的所有值 \(C(h, 1)\) 计算完毕；
• 如果 \(i\) 是偶数，那么 \(C(h, i) = C(h+1, i/2)\)，直接继承其父亲节点的 \(C\) 值即可，因为这个节点在父节点的右侧，所以其对应的 \(\alpha\) 值是一样的，就应该继承父亲的值；
• 如果 \(i\) 是奇数且不是 \(1\)，那么 \(C(h, i) = C(h+1, (i-1)/2) + B(h, i)\)，这个节点的值是其叔叔节点的值加上其自己的值，因为这个节点的值与其父亲节点的值相差了父亲节点的右儿子的值对应的 \(B\) 值，一方面是不能继承，另一方面我们要从叔叔节点拿到左侧已经计算的求和值，所以才有这样的计算规则。

看起来很抽象，看一遍 PPT 的动画就啥都明白了。

// 输入
for P_i, 1 <= i <= n pardo
    B(0, i) := A(i)

// 从下往上构建二叉树
for h = 1 to log(n)
    for i, 1 <= i <= n / 2^h pardo
        B(h, i) := B(h - 1, 2 * i - 1) + B(h - 1, 2 * i)

// 根据已经计算出来的值从上往下计算前缀和
for h = log(n) to 0
    for i even, 1 <= i <= n / 2^h pardo
        C(h, i) := C(h + 1, i / 2)
    for i = 1 pardo
        C(h, 1) := B(h, 1)
    for i odd, 3 <= i <= n / 2^h pardo
        C(h, i) := C(h + 1, (i - 1) / 2) + B(h, i)

// 输出前缀和
for P_i, 1 <= i <= n pardo
    Output C(0, i)

这个并行算法的深度是 \(O(\log n)\)，总的工作量是 \(O(n)\)。

3. 归并问题

省流！

• 串行查找：深度为 \(O(n)\)，总工作量为 \(O(n)\)；
• 并行二分查找：深度为 \(O(\log n)\)，总工作量为 \(O(n\log n)\)；
• 划分范式：分成大小为 \(\log n\) 的 \(n/\log n\) 个块，深度为 \(O(\log n)\)，总工作量为 \(O(n)\)。

问题：

简单的想法：想法来自于排名/Rank，假设我在本班排名第 \(i\)，在隔壁班排名第 \(j\)，那么我在两个班合起来排名就是 \(i + j - 1\)，对于合并两个数列的元素，我只需要知道 \(A\) 数列中的元素在 \(B\) 数列中的位置，同时数列这个数据结构就隐式的给出了这个元素在本数列中的位置，所以我们就可以知道这个元素在合并数列中的位置。

在 PPT 的中，\(A\) 的一个元素 \(A[i]\) 在 \(B\) 中的位置是 \(j\) 当且仅当在 \(B\) 中有 \(j\) 个元素在 \(A[i]\) 的前面，这样 \(A[i]\) 在合并数列中的位置就是 \(i + j\)，同时注意到我们这里的索引是从 \(1\) 开始一直到 \(n\) 的。这样并行的归并算法就很容易设计出来，并行的深度为 \(O(1)\)，总的工作量为 \(O(n)\)。

for P_i, 1 <= i <= n pardo
    C(i + Rank(A[i], B)) := A[i]
for P_i, 1 <= i <= n pardo
    C(i + Rank(B[i], A)) := B[i]

但是我们需要有合适的算法来确定 \(\mathrm{Rank}\) 函数。一个想法是简单的二分查找，二分查找本身不被并行化，但是我们可以并行的方式使用二分查找确定每一个元素的位置，这样的算法的深度为 \(O(\log n)\)，总的工作量为 \(O(n\log n)\)。

另外也可以整体线性查找，方法有点像归并排序，就是两个数组的元素从头向后比较，这样甚至都可以跳过从 \(\mathrm{Rank}\) 到最后求出 \(C\) 的步骤，一下就出来了，求 \(\mathrm{Rank}\) 简直就是脱裤子放屁。但是整个算法完全没有并行，深度和总的工作量都是 \(O(n)\)。

function BinarySearch:
    for P_i, 1 <= i <= n pardo
        Rank(A[i], B) = BS(A[i], B)
        Rank(B[i], A) = BS(B[i], A)

function SerialSearch:
    while (i <= n && j <= m)
        if (A[i+1] < B[+1j]) 
            Rank(A[++i], B) = j
        else 
            Rank(B[++j], A) = i

但是这样两种方法显然都不是最好的，第一种总工作量太大，第二种深度太大，我们需要效率更高的算法，因此引入划分范式作为我们的并行算法设计思路。

划分范式：分为两个步骤，第一个步骤为划分/Partitioning，将原问题划分为相当多个（也就是 \(p\) 个）子问题，每个子问题的大小大致为 \(n/p\)；第二个步骤为真实工作/Actual Work，同时对所有子问题进行处理，得到最终结果。上面的二分查找将问题划分为了 \(n\) 个子问题，线性查找将问题划分为了 \(1\) 个子问题。

使用划分范式处理归并问题，我们将数组分成 \(p\) 份，这时候 \(p\) 是未知的，我们只知道这个 \(p\) 应该是一个很大的值，，但在分析后选取最优的 \(p\)，首先对每一个子问题的第一个元素求出其在另一个数组的位置，这一步其实就讲两个数组分成了很多个对应的区域，我们在对应的区域再进行归并就可以了。这一步额外需要使用二分查找，否则因为子问题很多，使用线性查找会导致总工作量达到 \(O(p\cdot n)\)，这几乎是平方级别的工作量，显然是不可接受的。所以第一步划分的总工作量是 \(O(p\log n)\)，深度为 \(O(\log n)\)。

之后处理真实工作：剩下的工作其实就是相邻两个箭头之间的部分需要确认相应位置，确认了之后就可以根据划分的信息确定最终的位置。注意到这些箭头不会交叉，并且相邻两个箭头之间的距离不超过 \(n/p\)，加上一共有 \(2p\) 个箭头，这些都是通过分割的条件知道的。箭头将整个问题分成了 \(2p\) 个大小为 \(O(n/p)\) 的子问题，这些子问题直接使用线性查找就好，因为每个子问题都很小，此时的深度为 \(O(n/p)\)，总工作量为 \(2p\cdot O(n/p) = O(n)\)，这符合我们的要求。

注意这一步不能使用二分查找，一旦二分之后，总工作量就变成了 \(2p \cdot \dfrac{n}{p} \cdot O(\log n/p) = O(n\log n/p)\)，这显然是不可接受的，无法保证线性约束。

这样我们得到了划分深度为 \(O(\log n)\)，总工作量为 \(O(p\log n)\)、真实工作深度为 \(O(n/p)\)，总工作量为 \(O(n)\) 的并行算法。所有的这些 \(p\) 都还没有确定，我们首先希望划分的总工作量也应该是对于 \(n\) 线性的，所以取 \(p = n/\log n\)，这样划分的总工作量就是 \(O(n)\)，真实工作的深度就是 \(O(\log n)\)，总工作量也是 \(O(n)\)，这样我们就得到了一个深度为 \(O(\log n)\)，总工作量为 \(O(n)\) 的并行算法。

4. 寻找最大元素

问题：给定一个长度为 \(n\) 的数组，我们需要设计一个并行算法找到其中的最大元素。

我们将使用两种范式来解决这个问题，分别是：双对数范式/Doubly-Logarithmic Paradigm、加速级联范式/Accelerating Cascades Paradigm，并且讨论随机算法的应用。

省流！

• 双对数范式：分割成 \(\sqrt{n}\) 个子问题，每个子问题的大小为 \(\sqrt{n}\)，深度为 \(O(\log\log n)\)，总工作量为 \(O(n\log\log n)\)；
• 加速级联范式：分割成 \(n/\log\log n\) 个子问题，每个子问题的大小为 \(\log\log n\)，深度为 \(O(\log\log n)\)，总工作量为 \(O(n)\)。
• 随机算法：深度为 \(O(\log n)\)，工作量为 \(O(n)\)，存在常数 \(c\)，使得算法只有 \(1/n^c\) 的概率找不到最优解。
• 拓展：并行找第 \(k\) 大的：深度为 \(O(1)\)，工作量为 \(O(n^2)\)。两两比较，大的加 1 分，小的不加分，深度为 \(O(1)\)，工作量为 \(O(n^2)\)；然后再并行找到一个固定分数的元素（可以从 \(k\) 确定），深度为 \(O(1)\)，工作量为 \(O(n)\)。

双对数范式依赖二叉树的扩展——双对数树，在完全二叉树中，设叶子数量为 \(n\)，那么树高为 \(\log n\)。这里的双对数范式是希望构造一棵树，使得树高是 \(\log \log n\) 级别的。下面我们来构造这样一棵树，定义某个节点的 level 为从跟到该节点的距离/需要经过的边数，并且记根的 level 为 \(0\)，下面是一个有十六个叶子节点的树。

• 当某个节点的 level 为 \(s\)，且 \(s \leq \log \log n - 1\) 时，该节点有 \(2^{2^{H-s-1}}\) 个子节点，这里的 \(H\) 使得树的叶子节点的数量为 \(2^{2^H}\)；
• 当某个节点的 level 为 \(s\)，且 \(s = \log \log n\) 时，该节点有 \(2\) 个子节点作为树的叶子。

按照上面的规则，我们就可以建立起一棵双对数树，不难验证这样一棵树的叶子数量为 \(n\)，树高为 \(\log \log n\) 级别的。还有一个观察，当一个中间节点的 level 为 \(s\) 时，其一共有 \(2^{2^{H-s-1}}\) 个子节点，然后以它为根的子树的叶子数量可以算出来为 \(2^{2^{H-s}}\)，注意到 \(2^{2^{H-s - 1}}\) 是 \(2^{2^{H-s}/2} = \sqrt{2^{2^{H-s}}}\)，也就是我们知道每个节点将问题分割成了 \(\sqrt{m}\) 个子问题，其中 \(m\) 是这个节点对应的子树的叶子数量。

对于任意输入规模的数据，我们可以通过加入一些哑节点来构造出以这些输入为叶子的双对数树，这样我们就可以使用双对数范式来解决问题。即在每一层都将问题分割成 \(\sqrt{m}\) 个子问题，恰好每个子问题都对应着一棵子树，子树的叶子数也是 \(\sqrt{m}\)，这样我们就可以使用双对数范式来解决问题：算法是将数组划分成 \(\sqrt{n}\) 份，每一份的大小为 \(\sqrt{n}\)，然后我们并行递归找到每一份中的最大值，最后归并阶段再并行找到这 \(\sqrt{n}\) 个最大值中的最大值即可，这一步两两比较就可以得到线性大小的总工作量界，而且其深度是常数的，基本不会影响整体复杂度界，另整个算法的深度为 \(D(n)\)，总工作量为 \(W(n)\)，根据分治算法写出递推式：

\[ D(n) = D(\sqrt{n}) + O(1), \quad W(n) = \sqrt{n}W(\sqrt{n}) + O(n) \]

使用 \(n = 2^m\) 换元就可以破解：\(D(2^m) = D(2^{m/2}) + O(1)\)，解得 \(D(2^m) = O(\log m)\)，也就是 \(D(n) = O(\log\log n)\)，对待 \(W(n)\) 也是同理，但是直接寻找规律则可：记 \(S(m) = W(2^m)\)，则有

\[ S(m) = 2^{m/2}S(m/2) + O(2^m) \]

进一步展开 \(S(m/2)\)：

\[\begin{aligned} S(m) &= 2^{m/2}S(m/2) + O(2^m) = 2^{m/2} \cdot(2^{m/4}S(m/4) + O(2^{m/2})) + O(2^m) \\ &= 2^{3m/4}S(m/4) + O(2\cdot 2^m) \end{aligned}\]

继续展开总结规律可以得到 \(S(m) = 2^{m-1}\cdot S(1) + O(\log m\cdot 2^m) = O(\log m\cdot 2^m)\)，也就是 \(W(n) = O(n\log\log n)\)，这样我们就得到了一个深度为 \(O(\log\log n)\)，总工作量为 \(O(n\log\log n)\) 的并行算法。虽然总工作量没有达到线性复杂度，但是深度已经大大减小了，这仍然是可以接受的。

加速级联范式尝试将现有的并行算法和别的策略进行结合，得到更好的算法，PPT 上的第二个双对数范式其实就是加速级联范式。我们尝试将数组分为大小为 \(h = \log\log n\) 的 \(n/\log\log n\) 份，每一份的大小都很小，所以使用线性查找得到每一份的最大值，深度和工作量都是 \(O(\log\log n)\) 的；然后我们在上面求出来的 \(n/\log\log n\) 个最大值中找到最大值，这一步使用双对数范式的结果：深度为 \(O(\log\log(n/\log\log n))\)，总工作量为 \(O(n/\log\log n\cdot \log\log(n/\log\log n))\)

于是总体的深度为

\[ D(n) = O(\log\log n) + O(\log\log(n/\log\log n)) = O(\log\log n) \]

总体的总工作量为

\[ W(n) = O(n/\log\log n\cdot \log\log n) + O(n/\log\log n \cdot \log\log(n/\log\log n)) = O(n) \]

这样我们就有了一个双对数级别的深度和线性的总工作量的并行算法。

随机算法：甚至我们还有改进的空间，因为当初的两两比较算法可以实现 \(O(1)\) 的深度和 \(O(n^2)\) 的总工作量，我们希望使用随机进行改进，保证以很高的概率在 \(O(n)\) 的总工作量内找到最大值，同时常数深度不变。算法设计如下：

1. 在长度为 \(n\) 的数组 \(A\) 中，依照均匀分布取出 \(n^{7/8}\) 个元素，得到新的数组记为 \(B\)，这一步可以完全并行，深度为 \(O(1)\)，总工作量为 \(O(n^{7/8})\)；
2. 求出 \(B\) 中的最大值，使用确定性的算法实现，分为下面几个步骤：
   • 把 \(B\) 分成 \(n^{3/4}\) 个长度为 \(n^{1/8}\) 的子数组，然后使用两两比较的暴力算法并行找到每个子数组的最大值，这一步深度为 \(O(1)\)，总工作量为 \(O(n^{3/4}\cdot (n^{1/8})^2) = O(n)\)，将这 \(n^{3/4}\) 个最大值放在新数组 \(C\) 中；
   • 将 \(C\) 分成 \(n^{1/2}\) 个长度为 \(n^{1/4}\) 的子数组，然后使用两两比较的暴力算法并行找到每个子数组的最大值，这一步深度为 \(O(1)\)，总工作量为 \(O(n^{1/2}\cdot (n^{1/4})^2) = O(n)\)，将这 \(n^{1/2}\) 个最大值放在新数组 \(D\) 中；
   • 数组 \(D\) 直接使用两两比较的方法找到最大值，这一步深度为 \(O(1)\)，总工作量为 \(O((n^{1/2})^2) = O(n)\)；
   • 这样的方法深度为 \(O(1)\)，总工作量为 \(O(n)\)，我们能求出 \(B\) 中的最大值，结果是抽取这 \(n^{7/8}\) 个元素中的最大值；
3. 再来一轮，首先均匀分布取出 \(n^{7/8}\) 个元素，得到数组 \(B\)，然后用 \(n\) 个处理器，完全并行地对比 \(A\) 的一个元素和前一步获得的最大值 \(M\)，如果小于 \(M\) 则什么也不用做，大于 \(M\) 则往数组 \(B\) 的一个随机位置写入这一更大的值，写入完了后再求出更新后的 \(B\) 中的最大值，这一步的深度和工作量和第二步一样，因此是 \(O(1)\) 的深度和 \(O(n)\) 的工作量。

所以总的工作量就在 \(O(n)\) 的级别，总的深度在 \(O(1)\) 的级别。对于算法的正确性有下面的定理：

定理：以上算法以非常高的概率在 \(O(1)\) 的深度和 \(O(n)\) 的工作量内找到数组 \(A\) 中的最大值，也就是存在常数 \(c\)，使得算法只有 \(1/n^c\) 的概率无法在这一时间复杂度内找到最大值。

证明

寒假再写。

十一、External Sorting

由于我们很难在硬盘上直接进行排序，因为大部分内部排序算法均依赖于内存直接寻址的计算机体系结构特性，但是如果在硬盘上，由于硬盘上的元素只能被顺序访问，转动磁盘和移动磁头的延迟导致了实际上的效率损失。为了解决这个问题，我们只能使用归并排序，因为归并排序只需要顺序扫描两个有序数组，顺序写入硬盘就可以。

1. 简单算法

术语简记如下：

• run: 每组排好序的数据称为一个 run；
• pass: 将所有数据读过一遍的称为一个 pass。

我们进行二路排序，一般描述如下：我们有四个磁盘 \(T_{a_1}\)、\(T_{a_2}\)、\(T_{b_1}\)、\(T_{b_2}\)，初始数组一共有 \(N\) 个元素，内存可以一次性容纳和排序 \(M\) 个元素。一种自然的方法就是第一步输入磁带一次读入 \(M\) 个元素，在内部进行排序，然后交替地将排完序的元素写在 \(T_{a_1}\) 和 \(T_{a_2}\) 上，这样每组排序好的记录叫做一个顺串/Run。然后将 \(T_{a_1}\) 和 \(T_{a_2}\) 上的第一个顺串取出，合并并且将结果写在 \(T_{b_1}\) 上，然后取出下一个顺串，合并并且将结果写在另一个磁盘上，直到两个磁盘都是空的，或者只剩下一个顺串，将这个顺串拷贝到磁盘的末尾就好。接着递归地做这个操作，直到全部排序完成。

如果要对 \(N\) 条记录进行外部排序，且主存最多对 \(M\) 条记录进行外部排序，那么我们需要 \(\lceil \log_2(N/M) \rceil + 1\) 个 Pass。

在设计外部排序的时候，我们会关心以下问题：

• 寻道时间 \(O(\mathrm{number\ of\ passes})\)
• 读/写一个记录块（一组记录集）的时间
• 对 \(M\) 条记录进行内部排序的时间
• 从输入缓存（就是磁带）合并 \(M\) 条记录到输出缓存所需的时间

2. 多路合并

第一个目标就是减少工作的趟数，显然如果使用多路归并的话，每次合并后的顺串的长度增加 \(k\) 倍，那么我们只需要 \(\lceil \log_k(N/M) \rceil + 1\) 个 Pass，今儿减少了寻道时间，减少总时间，这样的算法被称为 \(k\)-路合并。

注意到，如果我们有 \(2k\) 个磁盘，那么在多路合并的视角下，我们只能实现 \(k\)-路合并。

3. 多相合并

多相合并通过调整每个磁盘上的顺串的个数，使得我们在实现 \(k\)-路合并的时候，可以尽可能使用最少的磁盘，也就是我们可以使用 \(k+1\) 个磁盘实现 \(k\)-路合并。作为例子，我们使用 \(3\) 个磁盘实现 \(2\)-路合并。

设我们有的磁盘是 \(T_1\)、\(T_2\)、\(T_3\)，在 \(T_1\) 上有 \(34\) 个顺串，我们的想法是合理分配这 \(34\) 个顺串到 \(T_2\) 和 \(T_3\) 上，使得每次归并的时候，我们将所有合并后的顺串都放在一个磁盘上，要求每次归并之后恰好有一个输入磁盘在归并结束之后是空的，这样就可以一直空一个盘：我们将 \(34\) 个顺串分成一组 \(13\) 个顺串，一组 \(21\) 个顺串，这样就可以用最少的归并次数实现 \(2\)-路合并——因为这样没有只有一个磁盘非空的情况，也就不需要将这个磁盘的内容分到两个磁盘上。

在二路合并中，如果顺串的个数是一个斐波那契数，将顺串分配成两个斐波那契树就好；如果不是，加一点哑顺串就可以实现。推广到 \(k\)-路合并，其中 \(k\)-阶斐波那契数定义如下：

\[ F^{(k)}(n) = F^{(k)}(n-1) + F^{(k)}(n-2) + \cdots + F^{(k)}(n-k) \]

4. 缓存并行

实现外部排序的时候，肯定是一块一块读入数据的，而不是每比较一次就往磁盘写一个元素，因此我们应该将内存划为输入缓冲区和输出缓冲区。输入缓冲区用来存放输入磁盘读入的数据，然后几个输入缓冲区之间的数据比较之后的排序结果先放到输出缓冲区，当输出缓冲区满了之后再一次行写进磁盘。

只有一个输出缓冲区显然是不可以的，因为当这个缓冲区的内容写进磁盘的时候，我们就不能再进行排序，所以我们需要两个输出缓冲区，这样就可以并行了：一个在内存里操作，一个进行 IO 操作。输入缓存同理，每个磁盘要配两个缓冲区，这样当输入缓存的数据正在比较的时候，我们就可以在另一块缓存中并行的读入新的数据。

总的来说，在 \(k\)-路合并的时候需要 \(2k\) 个输入缓冲区和 \(2\) 个输出缓冲区。当 \(k\) 太高时，\(k\)-路合并减少了趟数，但是并不一定更优：因为当 \(k\) 很大的时候，我们的输入缓存就会被划分得很细，一次能读入输入缓存的数据量就会减小（也就是 block 大小降低），那么我们的 I/O 操作就会变多，因此 k 太大的时候尽管趟数降低导致 I/O 成本降低，但并不一定更优。因此这其中一定有一个最优的 \(k\)，当然这是与具体的机器硬件有关的。

5. 替换选择

这是为了优化顺串的构造：先前我们的策略是每个顺串的长度都是内存的大小，但是这个长度可以进一步扩展。如果某个内存中的元素一旦写入磁盘了，这个内存位置就可以空出来比后续的元素使用，只要后续的元素比现在写入的更大，就可以继续往顺串后面添加该元素，下面是一个动态的例子，我们在内存中维护一个优先队列，每次从队列中取出一个比当前顺串中最后一个元素更大的最小的元素写入磁盘，再从磁盘中读入一个元素放进队列中，知道队列中的元素都比顺串中的最后一个要小，就开启一个新的顺串。

生成顺串的长度的均值一般有 \(L_{\mathrm{avg}} = 2M\) 的长度。

当生成了不同长度的顺串的时候，我们需要考虑如何合并这些顺串是最优的。最优解就是哈夫曼树，因为我们的目标是想让长的顺串尽可能少地参与合并，那么显然贪心地不断选择最小的两个顺串合并是最优的。

所谓外部路径长度，就是根到各个叶节点的路径长度之和，内部路径长度就是根到各个分支节点的路径长度之和。我们希望外部路径长度尽可能小，这样我们的 I/O 操作就会尽可能少，因此我们的目标就是构造一颗外部路径长度最小的哈夫曼树。

Info

完结撒花。