今天读了 The Art of Computer Programming (TAOCP) 第一卷第二章的前半部分, 主要讲的是线性表 (Linear List) 相关的内容. 大部分内容之前都有学习过, 但是还是学了挺多新东西的, 这篇博客分享一个我个人觉得挺有意思的算法.

当我们谈论线性表时, 我们在谈论什么

你们在相遇之前也曾爱过别人……如果我们俩有谁出了事，我想另一个，另一个人会伤心一会儿，你们知道，但很快，或者的一方就会跑出去，继续再次恋爱……所有这些，所有这些我们谈论的爱情，只不过是一种记忆罢了。甚至可能连记忆都不是。

— What We Talk About When We Talk About Love

1
// 上面是一段(除了我致敬了标题之外)毫无关系的引用. TAOCP 也经常出现这样的引用, 只不过它的引用都和正文有关系. ¯\_(ツ)_/¯

我们这里讨论的线性表, 主要是指数组, 链表, 栈, 队列等等这种一维的”表”. 今天要分享的内容主要和栈有关, 并且我们今天只讨论用 “数组” (连续的内存空间, 或者说序列分配 (Sequential Allocation)) 来实现的栈.

栈的放置

一, 两个栈

想像一下, 当我们全局只有一个栈的时候, 我们可以将栈基地址设置为内存空间的最大值, 每次 push 就减少栈顶地址. 这样, 我们就能在内存允许的情况下, 在栈中放置尽可能多的内容.

当全局有两个栈的时候, 我们可以机智地使用内存空间的另一头 (最小值) 来做第二个栈的栈基地址. 这样两个栈就各自安好, 互不打扰, 并且有多少内存, 就可以用多少内存. (这像不像堆和栈的关系).

多个栈

一旦我们需要使用超过两个栈, 很显然, 我们就没有办法同时保证以下两点:

  1. 只在所有栈中的内容总和超过所有可以内存的情况下, 才会栈溢出
  2. 每个栈的栈基地址固定不动.

为了提高内存的使用效率, 我们就只能放弃第二点. 这就意味着, 在某些情况下, 我们需要为一个”生存空间受到压迫”的栈腾挪出一些位置, 而这个往往是通过将某些内容拷贝到新的位置实现的.

一旦接受了这个设定, 人们就想出了很多算法. 在介绍算法之前, 我们先统一一下符号.

  • 地址空间为 $L_0$ 到 $L_{max}$ (假设指针大小可以被一个 int 存放).
  • 我们需要使用 $n > 2$ 个栈.
  • 每个元素占用一个字节.
  • 每个栈的栈基地址为 $BASE[i]$, 栈顶地址为 $TOP[i]$. 另外规定一下, $BASE[i]$ 为栈中第一个元素的前一字节的地址, $TOP[i]$ 为栈中最后一个元素的地址.

算法框架

根据上面的核心思想, 算法的框架如下:

初始化

1
2
3
4
5
6
for (int i = 0; i < n; i ++ ) {
  BASE[i] = L_0;
  TOP[i] = L_0;
}
// 虚拟的栈, 用来表示最后一个栈最多能扩展到哪.
BASE[n] = L_MAX;

压栈

1
2
3
4
5
6
7
void push(int i, byte v) {
  TOP[i] += 1;
  if (TOP[i] > BASE[i]) {
    rearrange();
  }
  *(TOP[i]) = v;
}

弹栈

1
2
3
4
5
6
7
byte pop(int i) {
  if (TOP[i] == BASE[i]) {
    throw Underflow();
  }
  TOP[i] -= 1;
  return *(TOP[i] + 1);
}

当我们发现一个栈目前的空间不够用的时候, 我们需要调用 rearrange 方法来为它拉扯空间.

简单算法

一个最简单的思路就是, 每当我们发现某一个栈的空间不够用了, 我们就将这个栈后面的栈都往后挪一个格, 直到某一个栈还有空闲空间.

这个方法简单易懂, 但是性能堪忧. 我们就不能多分配一些空间给这个用完空间的栈吗? 比如像 STL 中的 vector 每次扩展就是重新分配翻倍的空间, 大气!

今天的重头戏: “动态扩展”算法

这个算法的框架和简单算法相似, 只不过在 rearrange 的时候会搞个大新闻. 下面是 rearrange 的伪代码. 为了实现”因地制宜”的空间扩展, 我们还需要记住上一次 rearrange 之后每一个栈的 $TOP$ 值, 这些值保存在 $OLD_TOP$ 数组中.

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
47
48
49
50
51
52
53
54
55
56
void rearrange() {
  int* new_base[i] = compute_new_base();
  move(new_base);
}

// 为每个栈分配空间, 并计算分配完之后每个栈的新的栈基地址是什么.
int* compute_new_base() {
  int total_free = L_MAX - L_0;
  int* delta = new int[n];
  int total_detal = 0;
  for (int i = 0; i < n; i ++) {
    // 计算所有的空闲空间
    total_free -= TOP[i] - BASE[i];

    // 计算每个栈新使用的空间大小
    delta[i] = TOP[i] > OLD_TOP[i] ? TOP[i] - OLD_TOP[i] : 0;
    total_delta += delta[i];
  }

  int* new_base[i] = new int[n + 1];
  new_base[0] = L_0;
  new_base[n] = L_MAX;
  for (int i = 1; i < n; i ++) {
    new_base[i] = new_base[i - 1] + TOP[i - 1] - BASE[i - 1]
                + more_space(total_free, delta[i - 1], total_delta);
  } 
  return new_base;
}

// 根据新的栈基地址来腾挪之前的数据
// 注意这个 memmove 的调用很关键, 它和 memcpy 不一样, 可以处理 src 和 dst 重合的情况, 保证不会丢失数据.
void move(int* new_base) {
  int i = 0;

  while (i < n) {
    if (new_base[i] < BASE[i]) {
      memmove(new_base[i], BASE[i], TOP[i] - BASE[i]);
    }
    i ++;
  }

  while (i >= 0) {
    if (new_base[i] > BASE[i]) {
      memmove(new_base[i], BASE[i], TOP[i] - BASE[i]);
    }
    i --;
  }
}

// 这个 more_space 由于有浮点数运算, 可能总和小于 total_free, 要处理一下.
int more_space(int total_free, int delta, int total_delta) {
  // 10% free space are shared by n stacks evenly.
  // 90% free space are assigned propotional to the delta since last rearrangement.
  return (0.1 * total_free) / n 
       + (0.9 * total_free) * delta / total_delta; 
}

上面的算法非常好理解, 它主要包含两部分:

  1. 根据每个栈增长的幅度来分配剩余的可用空间, 根据可用空间来计算新的栈基地址.
  2. 将内容移到新的地址上.

其中第二个步骤需要注意的地方是两个 pass 的顺序. 第一个 pass 先将 base 前移的数据前移, 第二个 pass 先将 base 后移的数据后移. 我第一遍看的时候困惑了一下为什么这样移不会导致数据重合, 尤其是书上说

This algorithm is based on the easily verified fact that the data to be moved downward cannot overlap with any data that is to be moved upward, nor with any data that is supposed to stay put.

这个原因干想可能比较困难, 实际上计算一下就很容易. 对于任意两个相邻的栈 $i$ 和 $i + 1$, 只有 $i$ 向右移动, $i + 1$ 向左移动, 才可能出现重合. 回忆上面的代码, 我们知道

$$NEW\_BASE[i + 1] = NEW\_BASE[i] + TOP[i] - BASE[i] + DELTA$$

这样, 我们可以知道

$$NEW\_BASE[i + 1] \geq NEW\_BASE[i] + TOP[i] - BASE[i]$$

因为我们之前已经假设栈 $i$ 是向右移动, 所有 $NEW_BASE[i] > BASE[i]$. 也就是说,

$$NEW\_BASE[i + 1] \geq BASE[i] + TOP[i] - BASE[i] = TOP[i]$$

所以任意向左移的栈基地址是不会和前一个栈重合的, 我们上面的算法先将所有需要左移的栈左移是安全的.