算法导论26.3 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

26.3-1

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

1
2
3
4
5
6
7
8
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]\)中的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 找出数组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'，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
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)\)。可见，由于每次都淘汰了数组中一半的元素，并且每一轮除了递归部分，只需要\(\Theta(\lg n)\)的时间运行。因此有\(T_1(n)=2T_1(n/2)+\Theta(\lg n)\)。根据主定理可以得到\(T_1(n)=\Theta(n)\)。

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

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

26.3-3

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

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
// 令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\)的元素个数。我们可以知道这棵树的节点数为\(\displaystyle{\sum_{i=0}^{\infty}\left\lceil\dfrac{n}{2^i}\right\rceil}=\Theta(n)\)。

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

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

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

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

26.3-4

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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^{even},y^{odd}\)的计算也是同时派生出两个子线程再进行合并。此外，\(\omega_n^k\)的值不能够递推计算，它只能以\((\omega_n)^k\)的方式进行计算。

可见其串行投影为普通的FFT，因此其工作量为\(T_1(n)=\Theta(n\lg n)\)。

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

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

\(\star\) 26.3-5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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转化而来。其余部分只需要\(\Theta(\lg n)\)的时间即可完成。

因此，P-SELECT的工作量\(T_1(n)\)和SELECT的运行时间一样，为\(\Theta(n)\)。

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

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

\(\begin{aligned} T_{\infty}(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{\lg x}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n^p\left(1+\left(\dfrac{1-n^{-p}(1+p\ln n)}{p^2\ln 2}\right)\right)\right) \\ &=\Theta(n^p) \end{aligned}\)

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