本章内容以作者的一次经历为线索，介绍了他解决问题时的一些思路，并总结了遇到问题时的一些思考原理。同时，作者也简要介绍了归并排序相关的一些内容。

# 一次友好的对话

下文的斜体内容为作者朋友的回答，其余内容为作者所说的内容。J 表示作者，F 表示作者的朋友。

J：为什么需要自己编写排序代码，而不使用库提供的排序函数？

F：我需要在一个大系统中进行排序，由于不明的原因，无法调用库函数进行排序。

J：需要排序的内容是什么？文件中有多少条记录？每条记录的格式是怎么样的？

F：文件最多包含 1000 万条记录，每条记录都是 7 位的整数。

J：既然文件这么小，为什么不在内存中而在磁盘上进行排序呢？

F：排序功能是大系统中的一部分，到时只有 1 MB 的内存可用。

J：还有什么其他信息吗？

F：每条记录都是 7 位数的整数，无其他数据。每个整数最多只出现一次。

作者通过上述对话了解程序运行的系统信息，以及处理的数据类型和数值范围，这对于后续程序的编写可以提供很大的帮助。

在当时，美国的电话号码由 3 位区号和后续的 7 位号码组成，拨打 800 免费区号开头的号码则是免费的。这位朋友应该正在开发这类数据库处理系统的号码排序功能。这个应用背景也定义了相应的性能需求，当与系统的会话时间较长时，用户大约每小时请求一次有序文件，并且需要在排序完成之前一直等待。因此，排序最多只允许耗时几分钟来执行排序，10 秒是比较理想的运行时间。

# 准确的问题描述

• 输入：一个最多包含 $n$ 个正整数的文件，每个数都小于 $n$，其中 $n=10^7$。如果在输入中包含重复的整数，算作 Fatal Error ；
• 输出：按升序排列的输入整数的列表；
• 约束：最多有大约 1 MB 的内存空间可用，有充足的磁盘空间可用。运行时间最多几分钟，运行时间为 10 秒左右时不需要进一步的优化。

# 程序设计

显而易见的方法是以一般的基于磁盘的归并排序程序为起点，对其进行一定调整后能够在几十行的代码之内完成需求，但是程序可能需要几天的时间运行（以作者当时的设备而言）。

另一种方案则是利用改排序问题的特殊性，任务中需要排序的号码是 7 位数。

• 如果使用字符串存储，那么每个数据需要 7 字节来存储，那么 1 MB 的空间可以存储大约 143 000 个号码。归并排序需要额外的空间储存中间的数组结果，而内存空间不足以存放额外的数据，因此还需要将中间结果存储到其他的文件中（称为工作文件）。即排序过程中需要多次读写工作文件。而输入文件和输出文件则只读取和写入一次；
• 如果使用 32 位整数来表示的话， 1 MB 的空间可以存储 250 000 个号码；需要读取输入文件 40 次来完成排序。第 $i$ 次读取从 $i \times 250 000$ 到 $(i + 1) \times 250 000$ 之间的数字，进行排序后输出。所有的数字只需要输出一次。

如果有一种排序能够只读取输入文件一次，写入输出文件一次，并且能够在 1 MB 的空间限制条件下完成排序，那么它应当就是我们能够找到的最佳方案了。那么问题的关键就在于能否用大约 800 万个可用位来表示最多 1000 多万个互不相同的整数。

# 实现概要

若想要达成这个目标，需要利用位图或者位向量来表示输入数据的集合。例如，用一个 20 位的位图 $G$ 来表示所有元素都小于 20 的简单的非负整数集合 $S = \{1, 2, 3, 5, 8, 13\}$，则可以用 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 来表示。即 $G[S[i]]$ 设置为 1。

在这个问题中，我们使用 1000 万个位的空间来表示这个文件中的数据。其中，当且仅当整数 $i$ 在文件中存在时，第 $i$ 位为 1。这种表示利用了输入数据的性质：

• 输入数据在某一个范围之内；
• 输入数据没有重复；
• 输入数据没有其他任何关联数据。

假定 bit 表示该位图，则可以分为三个阶段来编写程序：

/* Phase 1: Initialize set to empty */

for i = [0, n)

    bit[i] = 0

/* Phase 2: Insert present elements into the set */

for each i in the input file

    bit[i] = 1

/* Phase 3: Write sorted output */

for i = [0, n)

    if bit[i] == 1

        write i on the output file

# 原理

从作者的朋友将他的问题进行说明，并花费了一刻钟明确了问题的关键所在之后，他花了几个小时完成了这个排序程序。最后的结果远远比预期的效果更好。

从这些事实中可以总结出该实例研究所得到的第一个结论：对小问题的仔细分析有时可以得到明显的实际益处。该实例阐明了如下的一般原理：

• 正确的问题
• 位图数据结构
• 多趟算法
• 时间 - 空间折衷与双赢
• 简单的设计

设计者确定其设计已经达到了完美的标准不是不能再增加任何东西，而是不能减少任何东西。—— Antoine de Saint-Exupery (法国作家兼飞机设计师)

# 习题

# 一

使用 C++ 实现算法，可以直接使用 set 数据结构。 set 在数据插入时会自动按照一定的顺序插入，直接遍历输出便能够得到有序的集合。

#include <iostream>

#include <set>

using namespace std;

int main()

{

    set<int> S{5, 7, 10, 2, 3, 1, 4, 9, 6, 8};

    for (int num : S) {

        cout << num << " ";

    }

    return 0;

}

或者使用 unordered_set ，通过 sort 函数对集合进行排序。

#include <iostream>

#include <unordered_set>

#include <algorithm>

using namespace std;

int main() {

    unordered_set<int> S{5, 7, 10, 2, 3, 1, 4, 9, 6, 8};

    sort(S.begin(), S.end());

    for (int num : S) {

        cout << num << " ";

    }

    return 0;

}

当然如果要自己实现排序算法的话，可以实现一个简单的快速排序算法。

#include <iostream>

#include <algorithm>

#include <vector>

#include <random>

using namespace std;

int partition(vector<int>& arr, int start, int end) {

    int index = start + (rand() % (end - start));

    swap(arr[start], arr[index]);

    int pivot = arr[start];

    int left = start, right = end - 1;

    while (left < right) {

        while (left < right && arr[right] >= pivot) {

            --right;

        }

        arr[left] = arr[right];

        while (left < right && arr[left] <= pivot) {

            ++left;

        }

        arr[right] = arr[left];

    }

    arr[left] = pivot;

    return left;

}

void fast_sort_wrapper(vector<int>& arr, int start, int end) {

    if (start >= end) {

        return;

    }

    int mid = partition(arr, start, end);

    fast_sort_wrapper(arr, start, mid);

    fast_sort_wrapper(arr, mid + 1, end);

}

void fast_sort(vector<int>& arr) {

    fast_sort_wrapper(arr, 0, arr.size());

}

# 二

# 库实现

C++ 提供了 bitset 数据结构，可以很方便地利用其实现位向量。使用时需要包含 <bitset> 头文件。以下内容参考自 Cppreference 中 bitset 的相关内容。^[1]

bitset 数据结构是一个包含 $N$ 比特的固定长度的序列。 bitset 可以进行标准的逻辑运算，可以和 string 和 integer 类型进行相互转换。

其定义为：

#include <bitset>

template <std::size_t N>

class bitset;

其中 $N$ 表示分配的比特的数量。需要注意的是，如果 $N$ 的值在编译期间无法确定，那么推荐使用 std::vector<bool> 。

一段示例程序如下：

#include <bitset>

#include <cassert>

#include <iostream>

int main()

{

    // constructors:

    constexpr std::bitset<4> b1;

    constexpr std::bitset<4> b2{0xA}; // == 0B1010

    std::bitset<4> b3{"0011"}; // can't be constexpr yet

    std::bitset<8> b4{"ABBA", /*length*/4, /*0:*/'A', /*1:*/'B'}; // == 0B0000'0110

    // bitsets can be printed out to a stream:

    std::cout << "b1:" << b1 << "; b2:" << b2 << "; b3:" << b3 << "; b4:" << b4 << '\n';

    // bitset supports bitwise operations:

    b3 |= 0b0100; assert(b3 == 0b0111);

    b3 &= 0b0011; assert(b3 == 0b0011);

    b3 ^= std::bitset<4>{0b1100}; assert(b3 == 0b1111);

    // operations on the whole set:

    b3.reset(); assert(b3 == 0);

    b3.set(); assert(b3 == 0b1111);

    assert(b3.all() && b3.any() && !b3.none());

    b3.flip(); assert(b3 == 0);

    // operations on individual bits:

    b3.set(/* position = */ 1, true); assert(b3 == 0b0010);

    b3.set(/* position = */ 1, false); assert(b3 == 0);

    b3.flip(/* position = */ 2); assert(b3 == 0b0100);

    b3.reset(/* position = */ 2); assert(b3 == 0);

    // subscript operator[] is supported:

    b3[2] = true; assert(true == b3[2]);

    // other operations:

    assert(b3.count() == 1);

    assert(b3.size() == 4);

    assert(b3.to_ullong() == 0b0100ULL);

    assert(b3.to_string() == "0100");

}

最终的运行结果如下：

b1:0000; b2:1010; b3:0011; b4:00000110

从上面的示例可以看出， bitset 支持多种初始化方式，并且支持 &, |, ^, ~, <<, >> 等位运算操作，也可以通过下标对某一特定位置的比特进行访问。常用的一些函数如下：

# 简易版

当然，我们也可以自己实现一个简易版本的 bitset ，一方面可以加深对位运算的了解；另一方面，后续的习题中也存在需要对 bitset 进行改造的内容，因此自己实现的版本能够方便后续修改。这里只重点关注代码的逻辑实现，对于鲁棒性没有做太高的要求。

#include <iostream>

#include <cmath>

#include <cstring>

using namespace std;

class bitmap {

public:

    bitmap(size_t n) {

        size = n;

        capacity = ceil(n * 1.0 / byte_size);

        bits = new unsigned char[capacity];

        memset(bits, 0, capacity);

    }

    void set(size_t pos, bool val) {

        size_t major_offset = pos / byte_size;

        size_t minor_offset = pos % byte_size;

        unsigned char mask = 0x1 << (byte_size - minor_offset - 1);

        if (val) { // 置为 1

            bits[major_offset] |= mask;

        } else { // 置为 0

            bits[major_offset] &= (~mask);

        }

    }

    void print() {

        int major_offset = size / byte_size;

        int minor_offset = size % byte_size;

        for (int i = 0; i < major_offset; ++i) {

            unsigned char val = bits[i];

            for (int j = byte_size - 1; j >= 0; --j) {

                cout << ((val >> j) & 1);

            }

            cout << ' ';

        }

        unsigned char val = bits[major_offset - 1];

        for (int j = byte_size - 1; j > byte_size - 1 - minor_offset; --j) {

            cout << ((val >> j) & 1);

        }

        cout << endl;

    }

private:

    unsigned char* bits;

    size_t size;

    size_t capacity;

    static const size_t byte_size = 8;

};

int main() {

    bitmap b(10);

    b.set(1, true);

    b.set(5, true);

    b.print();

    return 0;

}

输出如下：

01000100 01

这里暂时只实现了 set 函数。

# 三

这里假定输入是没有重复的整数。其实推荐先查看习题 3，因为这里包含一个生成小于 $n$ 的不重复的 $k$ 个整数的问题。这里假定已经有这样的方法，并且得到了这样的一个随机整数集合。在习题 2 的自定义的 bitmap 的基础上添加一个 sort 函数：

class bitmap {

public:

......

    void sort() {

        int major_offset = size / byte_size;

        int minor_offset = size % byte_size;

        size_t cnt = 0;

        for (int i = 0; i < major_offset; ++i) {

            unsigned char val = bits[i];

            for (int j = byte_size - 1; j >= 0; --j, ++cnt) {

                if ((val >> j) & 1) {

                    cout << cnt << ' ';

                }

            }

        }

        unsigned char val = bits[major_offset - 1];

        for (int j = byte_size - 1; j > byte_size - 1 - minor_offset; --j, ++cnt) {

            if ((val >> j) & 1) {

                cout << cnt << ' ';

            }

        }

        cout << endl;

    }

......

};

这里的代码假定已经通过遍历输入集合，将对应比特位置的值置为 true 。

如果是使用 C++ 库中的 bitset 实现则更加简单，也是直接遍历即可。示例代码中假定数字的输入范围不超过 $20$。

#include <bitset>

#include <iostream>

bitset<20> b{0x0};

    for (int num : arr) {

        b[num] = true;

    }

    for (int i = 0; i < b.size(); ++i) {

        if (b[i]) {

            cout << i << ' ';

        }

    }

    cout << endl;

# 四

题目想问的就是洗牌算法相关的内容。下面摘抄一些比较经典的洗牌算法。

# 洗牌算法 ^[2]

# Fisher-Yates Shuffle 算法

此算法最早由 Ronald A. Fisher 和 Frank Yates 提出。算法步骤如下：

1. 初始化原始数组长度为 $n$，存储 $[0, n\text{-}1]$；
2. 假设原始数组中还剩余 $k$ 个数字，随机产生一个 $[0, k)$ 之间的数字 $p$；
3. 将剩余数组中的第 $p$ 个数字取出，放入新数组；
4. 重复步骤 2 和步骤 3，直到所有数组均被取出；
5. 新数组中存放的即是一个打乱后的数列。

其随机性证明 —— 即每个元素放置在新数组中的第 $i$ 个位置的概率为 $\frac{1}{n}$—— 如下：

一个元素 $m$ 放入第 $i$ 个位置的概率 $P$ $=$ 前 $i\text{-}1$ 个位置选择元素时没有选择 $m$ 的概率 $\times$ 第 $i$ 个位置选中 $m$ 的概率，即：

$$P = \frac{n-1}{n}\times\frac{n-2}{n-1}\times\cdots\times\frac{n-i+1}{n-i+2}\times\frac{1}{n-i+1}=\frac{1}{n}$$

void Fisher_Yates_Shuffle(vector<int>& arr, vector<int>& res) {

    srand((unsigned)time(NULL));

    int k;

    int len = arr.size();

    for (int i = 0; i < len; ++i) {

        k = rand() % arr.size();

        res.push_back(arr[k]);

        arr.erase(arr.begin() + k);

    }

}

算法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。这里时间复杂度为 $O(n^2)$ 的原因是， vector 在移除元素时，会对该元素之后的其他元素进行移动。

# Knuth-Durstenfeld Shuffle 算法

Knuth 和 Durstenfeld 在 Fisher 和 Yates 洗牌算法的基础上进行了改进，在原数组中进行数据交换，将空间复杂度降低为 $O(1)$。算法步骤为：

1. 初始化原始数组 $A$，长度为 $n$，存储 $[0, n\text{-}1]$；
2. 对 $i$ 从 $1$ 到 $n\text{-}1$ 进行循环：
   1. 生成一个 $[0,n\text{-}i]$ 范围内的随机数 $k$；
   2. 将 $A[n-i]$ 和 $A[k]$ 进行交换；
3. 最终 $A$ 中存放被打乱的数组。

证明：

对于数组 $A$ 的元素 $A[i]$，洗牌后：

• 在第 $n\text{-}1$ 位置的概率是 $\frac{1}{n}$；
• 在第 $n\text{-}2$ 位置的概率是 $\frac{n-1}{n}\times\frac{1}{n-1}=\frac{1}{n}$；
• $\cdots$；
• 在第 $n\text{-}k$ 位置的概率是 $\frac{n-1}\times\frac{n-2}{n-1}\times\cdots\times\frac{n-k+1}{n-k+2}\times\frac{1}{n-k+1}=\frac{1}{n}$；

即 $A[i]$ 在任意一个位置的概率均为 $\frac{1}{n}$。

void Knuth_Durstenfeld_Shuffle(vector<int>& arr) {

    for (int i = arr.size() - 1; i >= 0; --i) {

        srand((unsigned)time(NULL));

        swap(arr[rand() % (i + 1)], arr[i]);

    }

}

以上算法的时间复杂度为 $O(n)$, 空间复杂度为 $O(1)$。需要注意的是，该算法是在原数组上进行操作的，如果不希望原数组的内容被修改，那么则需要先进行复制操作；对于流式数据也无法进行处理。

# Inside-Out Shuffle 算法

Inside-Out Shuffle 算法的基本思想是从前向后扫描原始数组 $A$，对元素 $A[i]$，在位置 $[0, i]$ 中随机选择一个位置 $k$，在新数组 $A^\prime$ 中将 $A^\prime[k]$ 赋值给 $A^\prime[i]$，然后将 $A[i]$ 赋值给 $A^\prime[k]$。

证明：

原数组中元素 $A[i]$ 在新数组 $A^\prime$ 中前 $i$ 个位置的概率均为：

$$\frac{1}{i}\times\frac{i}{i+1}\frac{i+1}{i+2}\times\cdots\times\frac{n-1}{n}=\frac{1}{n}$$

即第 $i$ 次刚好随机放到了该位置，在后面的 $n\text{-}i$ 次选择中该数字不被选中）。

原数组中元素 $A[i]$ 在新数组 $A^\prime$ 中 $i+1$ 以后位置的概率为：

$$\frac{1}{k}\times\frac{k}{k+1}\frac{k+1}{k+2}\times\cdots\times\frac{n-1}{n}=\frac{1}{n}$$

即第 $k$ 次刚好随机放到了该位置，在后面的 $n\text{-}k$ 次选择中该数字不被选中。

该算法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。因为是从前往后遍历，可以处理动态增长的数组。

# 蓄水池抽样算法

从大小未知的 $n$ 个元素中等概率取出 $k$ 个元素，能够在 $O(n)$ 时间内对 $n$ 个数据进行等概率随机抽取。即使元素数量在继续增长，依然可以做到等概率抽取。

伪代码：(下标从 $1$ 开始)

Init: a reservoir with size: k

    for i = k + 1 to N

        M = random(1, i)

        if (M < k)

            swap the Mth value and ith value

    end for

上述伪代码的含义是，第 $i$ 个元素有 $\frac{k}{i}$ 的概率被选中，然后能够等概率 $\frac{1}{k}$ 替换掉已经选中的元素中的一个。最终前 $k$ 个元素即我们所需的最后结果。

证明：在选择第 $i$ 个元素时，前 $i\text{-}1$ 个元素出现在 $k$ 个元素中的概率是 $\frac{k}{i}$，$i\in [k+1, N]$

1. 对于第 $k+1$ 个元素，此时蓄水池中的元素为前 $k$ 个元素，$M$ 此时随机从 $[1,k+1]$ 中选取，$M < k$ 的概率为 $\frac{k}{k+1}$，即第 $k+1$ 个元素被选中的概率；而对于前 $k$ 个元素，他们如果要被替换，那么必须 $M < k$，且 $M$ 和自己的下标相等。$P(M<k) = \frac{k}{k+1}$，$P(M=x,x\in[1,k])=\frac{1}{k}$，即被替换的概率为 $P(M<k)\cdot P(M=x,x\in[1,k])=\frac{k}{k+1}\cdot\frac{1}{k}=\frac{1}{k+1}$，那么他们不被替换的 —— 即还在 $k$ 个选中的元素中的概率为 $\frac{k}{k+1}$；
2. 假设当 $j=i$ 的时候结论成立，第 $i$ 个元素被选中的概率为 $\frac{k}{i}$，前 $i\text{-}1$ 个元素在选中的 $k$ 个元素中的概率为 $\frac{k}{i}$；
3. 下面证明当 $j=i+1$ 的时候结论成立：
   1. 第 $i+1$ 个元素被选中的概率为 $\frac{k}{i+1}$；
   2. 由 2 的假设可知前 $i$ 个元素出现在被选择的 $k$ 个元素中的概率为 $\frac{k}{i}$；
   3. 前 $i$ 个元素中，在 $k$ 个元素中的元素，被替换的概率为 $\frac{k}{i+1}\times\frac{1}{k}=\frac{1}{i+1}$；
   4. 那么不被替换的概率为 $1 - \frac{1}{i+1}=\frac{i}{i+1}$；
4. 综上，前 $i$ 元素出现在蓄水池中的概率为 $\frac{k}{i}\times\frac{i}{i+1}=\frac{k}{i+1}$。

证明：数据中的每个元素被选中的概率为 $\frac{k}{n}$。

第 $m$ 个元素被选中的概率 $=$ 选择 $m$ 个概率 $\times$ (其后元素不被选中的概率 + 其后元素被选中的概率$\times$ 不替换第 $m$ 个元素的概率)，即：

$$P = \frac{k}{m}\times\prod\limits_{m+1}^{n}(\frac{i-k}{i} + \frac{k}{i}\times\frac{k-1}{k}) = \frac{k}{m}\times\frac{m}{n} = \frac{k}{n}$$

蓄水池抽样算法适合不知道数据总量的场景，例如对机器学习的数据集进行划分或者采样的时候可以使用。

# 五

采用多趟排序的算法， 1 MB 可以存储约 500 万个数字，那么可以先排序 $[0,4999999]$，第二趟再排序 $[5000000, 9999999]$。

# 六

10 需要用 4 比特的空间来表示。对每个数字，用 4 比特存储其出现次数，即半比特的空间。总共需要 $10000000 \times 4 / 2 = 20000000$ 字节的空间来完成排序。当保存的数字出现次数发生变化时，可以进一步调整分配的比特大小。另外，比特的大小最好是 $2$ 的幂次，这样便于使用位运算进行处理。

假定我们使用 unsigned char 类型进行存储，对应 1 个字节，即 8 个比特。如果每个数字使用 4 比特存储出现的次数，那么可以存储 2 个数字出现的次数。更进一步，假定一个数字需要使用 $k$ 比特进行存储（这里假设 $k = 2^m$），那么总共可以存储 $n = 8/k$ 个数字的数量。用 $A$ 表示存储所有数字数量的数组。

如果我们需要对特定数字的内容进行操作，假设该数字是 $i$，那么要对应的 $A$ 中的内容应该在 $A[i >> m]$。在定位到这个元素之后，我们需要对 $i$ 对应的比特进行操作。

如何找到对应的比特？我在之前的习题中是按照 |0 1|2 3|4 5|... 这样的顺序来存储每个数字的数量，但是在查找其他人的博客^[3]之后发现，使用 |1 0|3 2|5 4|... 这样的方式进行存储时，位运算会更加简洁。这里两个 | 即表示一个 unsigned char 存储的对应数字的数量，这里假设每个数字使用 4 比特存储。如果使用 2 比特存储，那么内容应该是 |3 2 1 0|7 6 5 4|... 这样的内容。

我们现在已经找到了对应数组元素 $A[i >> m]$，要进一步确定比特的位置。对于 $i$，$i$ 即表示 $i$ 对应 $A[i >> m]$ 中的第 $i$ 组 $k$ 比特。

假定现在加入了一个 $i$，那么 $i$ 的数量应当加一，对应的代码应该是 A[i >> m] += 1 << (k * (i % n)) 。

如果要把 $i$ 对应的值置 0，为了不影响其他数字的值，需要使用按位与操作，即其他值对应的比特位置都需要为 1，而 $i$ 对应的值需要为 0 。为了更具一般性，假设使用 2 比特存储出现的次数，那么 unsigned char 的 8 个比特可以分为 4 组。假设现在 01 10 00 11 分别对应 3 2 1 0 出现的次数 1 2 0 3 。如果 $i = 2$，那么我们需要使用 11 00 11 11 与 01 10 00 11 进行 & 运算。

11 00 11 11 可以通过 00 11 00 00 取反得到，而 00 11 00 00 可以通过 0x03 左移得到。而 0x03 这个 magic number，对于 unsigned char ，可以通过 0xF >> (8 - m) 得到。如果使用 unsigned int ，则对应 0xFFFF >> (32 - m) 。

所以置零操作代码为 A[i >> m] &= ~((0xF >> (8 - m)) << (4 * (i % n))) 得到。

假如要取出 2 对应的数值，只要在置零操作的基础上进行修改。使用 00 11 00 11 进行 & 运算，然后进行移位： A[i >> m] & ((0xF >> (8 - m)) << (4 * (i % n))) >> (4 * (i % n)) 。

# 七

第一个问题：某个数字出现次数超过一次，那么最终输出结果的时候，只有对应的一个值，不会有多个值。

第二个问题：输入整数 $< 0$ 或者 $\ge n$，需要在读取数字的时候做出判断，过滤掉不在范围内的输入数据。

第三个问题：输入数据不是数值，在读取输入时，检查输入的结果类型。如果不符合要求，直接 continue 或者报错结束程序，根据实际需求实现。

# 八

排序操作依然可以使用位图进行排序。可以将位图作为文件进行存储，查找的时候，直接访问数字对应的位图比特，如果对应的值为 1，那么说明该号码存在，这样的时间复杂度是 $O(1)$。

# 九

这道问题参考了相关的博客^[4]，当数组的大小 $n$ 非常大时，初始化也是一个非常耗时的操作。因此对所有数据进行统一初始化是不可取的。为了达到时间性能的要求，我们仅对访问的元素（访问到的元素的数量远小于 $n$）进行初始化。

而这样做就带来了一个问题 —— 我们需要在访问元素之前，对其进行判断，是否已经对该元素进行了初始化。《编程珠玑》的答案中引入了两个数组 from 和 to 以及整数 top ， top 初始化为 0，对于元素 data[i] ，其已经初始化的条件是 from[i] < top && to[from[i]] == i 。

现在具体分析一下这个条件。假设第一次访问的元素下标为 $i$，一般而言 from[i] 中的随机数是大于 top 的，但是并没有 100% 的保证。此时，第二个判断条件 to[from[i]] == i 就起了作用，这个条件里面相当于取出了 from[i] 和 to[from[i]] 两个随机数，并且该随机数还要恰好等于 i ，虽然在未初始化的情况也有概率可能满足这个结果，但是概率几乎为 0。因此，对于满足这个条件的元素 data[i] 的下标 $i$，可以认为其已经经过了初始化。

在不满足该条件时，我们需要执行下述代码进行初始化：

from[i] = top;

to[top] = i;

data[i] = 0;

++top;

这是一个用空间换时间的方法。

# 十

对电话号码的最后 $k$ 位进行哈希，发生冲突时使用开链法，按照手机尾号顺序存储。当顾客抵达进行检索商品时，营业员按顺序检索订单，这是经典的用 “顺序搜索来解决冲突的开放散列”。如果两位不够，也可以使用更多位，比如我们在验证时，经常使用手机后 4 位判断是否是本人的手机号码。

# 十一

飞鸽传书；网络传输（传真机）。emmm

# 十二

According to the urban legend, the Soviets solved their problem with a pencil, of course. For background on the true story, learn about the Fisher Space Pen company. The company was founded in 1948, and its writing instruments have been used by the Russian Space Agency, underwater explorers, and Himalayan climbing expeditions. ^[5]

所以根据都市传说，苏联使用的是铅笔。但是实际上，他们也是使用的特别研制的所谓 “太空笔”。

# 深入阅读

本章描述的问题中，既有技术相关的问题，也有一些看似非常无厘头，但是却能够出发创新型思维的问题。作者提供这样的一些习题正是为了激励读者去打破一些这样的壁垒。