算法导论 26.3 Exercises 答案

发表于 2023-10-01 分类于算法导论阅读次数： 61 本文字数： 2.7k 阅读时长 ≈ 2 分钟

26.3-1

基本思想是，只需要当前排序的数组长度小于等于某个很小的阈值 $K$ ，那么就选择使用原本串行的归并方式。否则使用当前优化过的归并方式，这个过程由 P-MERGE' 给出。其中 MEGRE' 和 MERGE 相比，表示将排序结果存储到 $B$ 中（而不是原本的 $A$ 中）。

P-MERGE'(A, p, q, r)
  let B[p : r] be a new array             // allocate scratch array
  if r - p > M
    P-MERGE-AUX(A, p, q, q + 1, r, B, p)  // merge from A into B
  else
    MERGE'(A, p, q, r, B)
  parallel for i = p to r                 // copy B back to A in parallel
    A[i] = B[i]

26.3-2

通过对题目 9.3-10 给出的 MEDIAN3 进行改造，我们给出了一个程序 MEDIAN4，它用于求解两个有序数组 $A [1 : n], B [1 : m]$ 中的中位数。

// 找出数组A[i : n], B[j : m]中的第k小数。
SELECT4(A, i, n, B, j, m, k)
  if i > n
    return B[j + k - 1]
  else if j > m
    return A[j + k - 1]
  else if k == 1
    return min{A[i], B[j]}
  if i + ⌊k/2⌋ - 1 <= n
    midl = A[i + ⌊k/2⌋ - 1]
  else
    midl = +∞
  if j + ⌊k/2⌋ - 1 <= m
    midr = B[i + ⌊k/2⌋ - 1]
  else
    midr = +∞
  if midl < midr
    return SELECT4(A, i + ⌊k/2⌋, n, B, j, m, k - ⌊k/2⌋, n)
  else
    return SELECT4(A, i, n, B, j + ⌊k/2⌋, m, k - ⌊k/2⌋, n)

MEDIAN4(A, B, n, m)
  return SELECT4(A, 1, n, B, 1, m, ⌊(n + m) / 2⌋)

由此可以将 P-MERGE-AUX 修改成 P-MERGE-AUX'，如下：

P-MERGE-AUX(A, p1, r1, p2, r2, B, p3)
  if p1 > r1 and p2 > r2
    return
  if r1 − p1 < r2 − p2
    exchange p1 with p2
    exchange r1 with r2
  x = MEDIAN4(A[p1 : r1], B[p2 : r2], r1 - p1 + 1, r2 - p2 + 2)
  q2 = FIND-SPLIT-POINT(A, p2, r2, x)
  q3 = p3 + (q1 − p1) + (q2 − p2) 
  B[q3] = x
  spawn P-MERGE-AUX(A, p1, q1 − 1, p2, q2 − 1, B, p3)
  spawn P-MERGE-AUX(A, q1 + 1, r1, q2, r2, B, q3 + 1)
  sync

先求解 P-MERGE-AUX' 的工作量 $T_{1} (n)$ 。可见，由于每次都淘汰了数组中一半的元素，并且每一轮除了递归部分，只需要 $Θ (\lg n)$ 的时间运行。因此有 $T_{1} (n) = 2 T_{1} (n / 2) + Θ (\lg n)$ 。根据主定理可以得到 $T_{1} (n) = Θ (n)$ 。

接下来求解 P-MERGE-AUX' 的持续时间 $T_{\infty} (n)$ 。同样的，我们得到 $T_{\infty} (n) = T_{\infty} (n / 2) + Θ (\lg n)$ 。从而得到 $T_{\infty} (n) = Θ (\lg^{2} n)$ 。

由于 P-MERGE-AUX' 的工作量和持续时间都不变，因此得到的 P-MERGE' 得到的工作量和持续时间和第 26.3 章分析的一样，分别为 $Θ (n)$ 和 $Θ (\lg^{2} n)$ 。因此其并行量仍然为 $Θ (n / \lg^{2} n)$ 。

26.3-3

PARTITION 的并行化版本 P-PARTITION 如下展示。

// 令T[p, r]表示一棵二叉树T存储了区间[p, r]内所有数的相关信息，包括：
// small：A[p, r]中小于等于x的数的个数。
// large：[p, r]中大于x的数的个数。
P-PARTITION-CAL(A, p, r, x)
  if p == r
    if A[p] <= x
      T[p, r].small = 1
      T[p, r].large = 0
      return (1, 0)
    else
      T[p, r].small = 0
      T[p, r].large = 1
      return (0, 1)
  else
    mid = ⌊(p + r) / 2⌋
    cl-small, cl-large = spawn P-PARTITION-CAL(A, p, mid, x)
    cr-small, cr-large = spawn P-PARTITION-CAL(A, mid + 1, q, x)
    sync
    T[p, r].small = cl-small + cr-small
    T[p, r].large = cl-large + cr-large
    return (T[p, r].small, T[p, r].large)

P-PARTITION-FILL(A, p, r, x, B, ls, rs, ll, rl)
  if p == r:
    if A[p] <= x
      B[ls] = A[p]
    else
      B[ll] = A[p]
  else
    mid = ⌊(p + r) / 2⌋
    spawn P-PARTITION-FILL(A, p, mid, x, B, ls, ls + T[p, mid].small - 1, ll, ll + T[p, mid].large + 1)
    spawn P-PARTITION-FILL(A, p, mid, x, B, rs - T[mid + 1, r].small + 1, rs, rl - T[mid + 1, r].large + 1, rl)
    sync

P-PARTITION(A, p, r)
  if p == r
    return p
  x = A[r]
  c-small, c-large = P-PARTITION-CAL(A, p, r - 1, x)
  let B[p : r] be a new array
  q = p + c-small
  B[q] = x
  P-PARTION-FILL(A, p, r, x, B, p, p + c-small - 1, r - c-large + 1, r)
  parallel for i = p to r
    A[i] = B[i]
  return q

我们可以首先并行化地构筑出一棵二叉树 $T$ ，其中 $T [l, r]$ 存储区间 $[l, r]$ 内的信息：小于等于 $x$ 的元素个数和大于 $x$ 的元素个数。我们可以知道这棵树的节点数为 $\sum_{i = 0}^{\infty} ⌈ \frac{n}{2^{i}} ⌉ = Θ (n)$ 。

因此，第一趟遍历首先是将这棵树的所有节点信息先处理出来（如 P-PARTITION-CAL 所示），由于这棵树一共有 $Θ (n)$ 个节点，其深度为 $Θ (\lg n)$ ，因此这一部分的工作量为 $Θ (n)$ ，持续时间为 $Θ (\lg n)$ 。

第二趟遍历则是按照树给定的信息，自底向上地将所有元素填入新数组 $B$ 中（如 P-PARTITION-FILL 所示）。这一部分的分析和第一趟类似，这一部分的工作量为 $Θ (n)$ ，持续时间为 $Θ (\lg n)$ 。

第三趟遍历则是将 $B$ 数组并行地填入 $A$ 中对应位置，因此这一部分的工作量为 $Θ (n)$ ，持续时间为 $Θ (\lg n)$ 。

也就是说，P-PARTITION 的工作量 $T_{1} (n)$ 满足 $T_{1} (n) = 2 T_{1} (n / 2) + Θ (1)$ ，即得到 $T_{1} (n) = Θ (n)$ 。其工作时间 $T_{\infty} (n)$ 满足 $T_{\infty} (n) = T_{\infty} (n / 2) + Θ (1) = Θ (\lg n)$ 。因此其并行度为 $Θ (n / \lg n)$ 。

26.3-4

给出的 FFT 的并行版本 P-FFT 如下：

FFT(a, n)
  if n == 1
    return a
  let a-even_{0 : n / 2 - 1}, a-odd_{0 : n / 2 - 1} be new arrays
  parallel for k = 0 to n / 2 - 1
    a-even_{k} = a_{k * 2}
    a_odd_{k} = a_{k * 2 + 1}
  y-even = spawn FFT(a-even, n / 2)
  y-odd = spawn FFT(a-odd, n / 2)
  sync
  parallel for k = 0 to n / 2 - 1
    ω = exp(2 * π * i * k / n)
    y_k = y-even_{k} + ω * y-odd_{k}
    y_{k + n / 2} = y-even_{k} - ω * y-odd_{k}
  return y

P-FFT 和其串行投影 FFT 的区别在于：将 $a$ 向量进行奇偶划分的过程可以并行完成。其次， $y^{e v e n}, y^{o d d}$ 的计算也是同时派生出两个子线程再进行合并。此外， $ω_{n}^{k}$ 的值不能够递推计算，它只能以 $(ω_{n})^{k}$ 的方式进行计算。

可见其串行投影为普通的 FFT，因此其工作量为 $T_{1} (n) = Θ (n \lg n)$ 。

每次递归，它都会将两个大小恰好为一半的两个子问题进行递归计算，其余部分只需要 $Θ (\lg n)$ 的时间就能够完成好（如两次次 parallel for 循环以及 $ω_{n}^{k}$ 的计算），因此其持续时间满足 $T_{\infty} (n) = T_{\infty} (n / 2) + Θ (\lg n)$ ，最终得到 $T_{\infty} (n) = Θ (\lg^{2} n)$ 。

因此，P-FFT 的并行度为 $T_{1} (n) / T_{\infty} (n) = Θ (n / \lg n)$ 。

$⋆$ 26.3-5

P-SELECT(A, p, r, i)
  g = ⌊(r – p + 1) / 5⌋
  f = (r - p + 1) % 5
  parallel for j = p to p + g – 1
    sort〈A[j], A[j + g], A[j + 2 * g], A[j + 3 * g], A[j + 4 * g]〉in place
  for j = 0 to t - 1
    exchange A[p + 3 * g + j] with A[p + 5 * g + j] 
  x = P-SELECT(A, p + 2 * g, p + 3 * g + f – 1, ⌈(g + f) /2⌉)
  q = P-PARTITION-AROUND(A, p, r, x)
  k = q – p + 1
  if i == k
    return A[q]
  else if i < k
    return P-SELECT(A, p, q – 1, i)
  else 
    return P-SELECT(A, q + 1, r, i – k)

修改后得到的 P-SELECT 算法如上。相比于 SELECT，P-SELECT 将未满一个组的五个元素进行了延后处理。此外，套用题目 26.3-3 的结论，P-PARTITION-AROUND 可以由 PARTITION-AROUND 转化而来。其余部分只需要 $Θ (\lg n)$ 的时间即可完成。

因此，P-SELECT 的工作量 $T_{1} (n)$ 和 SELECT 的运行时间一样，为 $Θ (n)$ 。

P-SELECT 的持续时间 $T_{\infty} (n)$ 可以由 $T_{\infty} (n) \leq T_{\infty} (n / 5) + T_{\infty} (7 n / 10) + Θ (\lg n)$ 给出。这里可以考虑使用第 4.7 章介绍的 Akra-Bazzi 方法进行求解。

令 $c_{1} = \frac{1}{5}, c_{2} = \frac{7}{10}$ ，构造关于未知数 $p$ 的方程 $c_{1}^{p} + c_{2}^{p} = 1$ ，可以得到 $p \approx 0.84$ 。因此，使用等式 4.23，可以得到

$\begin{aligned} T_{\infty} (n) & = Θ (n^{p} (1 + \int_{1}^{n} \frac{f (x)}{x^{p + 1}} d x)) \\ = Θ (n^{p} (1 + \int_{1}^{n} \frac{\lg x}{x^{p + 1}} d x)) \\ = Θ (n^{p} (1 + (\frac{1 - n^{- p} (1 + p \ln n)}{p^{2} \ln 2}))) \\ = Θ (n^{p}) \end{aligned}$

因此，P-SELECT 的并行度为 $T_{1} (n) / T_{\infty} (n) = Θ (n^{1 - p}) \approx Θ (n^{0.16})$ 。

26.3-1

26.3-2

26.3-3

26.3-4

⋆ 26.3-5

$⋆$ 26.3-5