《编程珠玑》的笔记。

作者 Jon Bentley 推荐的阅读方法，因此每次完成一章，重点是自己思考习题。

One hint about reading the essays: don’t go too fast. Read them carefully, one per sitting. Try the problems as they are posed — some of them look easy until you’ve butted your head against them for an hour or two. Afterwards, work hard on the problems at the end of each column: most of what you learn from this book will come out the end of your pencil as you scribble down your solutions. If possible, discuss your ideas with friends and colleagues before peeking at the hints and solutions in the back of the book. The further reading at the end of each chapter isn’t intended as a scholarly reference list; I’ve recommended some good books that are an important part of my personal library.

Column 1: Cracking the Oyster

中文版将“Cracking the Oyster”译为了“开篇”。

Precise Problem Statement 准确的问题描述

输入：一个最多包含 n 个正整数的文件，每个数都小于 n，其中 n=10^7。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表。

约束：最多有（大约）1 MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

Program Design 程序设计

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

如果每个号码都使用7个字节来存储，那么在可用的1 MB存储空间里大约可以存143 000个号码。如果每个号码都使用32位整数来表示的话，在1 MB存储空间里就可以存储250 000个号码。

7B: 100 0000/7 = 142,857.1428571429 即143 000个号码

32b=4B: 100 0000/4=250 000

因此，可以使用遍历输入文件40趟的程序来完成排序。在第一趟遍历中，将0至249 999之间的任何整数都读入内存，并对这（最多）250 000 个整数进行排序，然后写到输出文件中。第二趟遍历排序250 000至499 999之间的整数，依此类推，到第40趟遍历的时候对9 750 000至9 999 999之间的整数进行排序。

解决方法：

1、归并排序

• 读入输入文件1次
• 需要工作文件的帮助完成排序，工作文件需要多次读写
• 写入输出文件1次

2、多遍排序

• 读入输入文件多次
• 不需要中间文件
• 写入输出文件1次

3、神奇排序

• 读入输入文件1次
• 不需要中间文件
• 写入输出文件1次

只有在输入文件中的所有整数都可以在可用的1 MB内存中表示的时候才能够实现该方案。于是问题就归结为是否能够用大约800万个可用位来表示最多1 000万(10^7)个互异的整数。

// 1MB=10^6B=8*10^6b 即800万个可用位

Implementation Sketch 实现概要

800万个可用位——>1 000万个互异的整数

由是观之，应该用位图或位向量表示集合。

每个7位十进制整数表示一个小于1 000万的整数。我们使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。（那个程序员后来找到了200万个稀疏位，习题5研究了最大存储空间严格限制为1 MB的情况。）

这种表示利用了该问题的三个在排序问题中不常见的属性：

• 输入数据限制在相对较小的范围内；
• 数据没有重复；
• 对于每条记录而言，除了单一整数外，没有任何其他关联数据。

Principles 原理

位图数据结构：

该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。

Problems 习题

1 If memory were not scarce, how would you implement a sort in a language with libraries for representing and sorting sets?

my answer:

macOS系统中，可以使用Ctrl+D来触发EOF或者下面C++代码中的while(cin >> i)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int a[1000000];
int main()
{
    int i, n = 0;
    while (scanf("%d", &a[n]) != EOF)
    {
        n++;
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", a[i]);
    }
    return 0;
}

writer’s answer:

This C program uses the Standard Library qsort to sort a file of integers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int intcomp(int *x, int *y)
{
    return *x - *y;
}
int a[1000000];
int main(void)
{
    int i, n = 0;
    while (scanf("%d", &a[n]) != EOF)
        n++;
    qsort(a, n, sizeof(int), intcomp);
    for (int i = 0; i < n; i++)
        printf("%d\n", a[i]);
    return 0;
}
// 本来自己形成编码习惯只要是循环就会加大括号。
// 但发现作者并没有加，不加代码是更短更简洁，那就不加，或许慢慢改变习惯。

This C++ program uses the set container from the Standard Template Library for the same job.

C++的set容器会自动排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int main()
{
  set<int> S;
  int i;
  set<int>::iterator j;
  while (cin >> i)
    S.insert(i);
  for (j = S.begin(); j != S.end(); ++j)
    cout << *j << "\n";
  return 0;
}
 // 按照我的习惯，写这种短代码的时候，一定会把set<int>::iterator j;放到要使用的地方即for循环中
 // 又想到之前看的书中说将变量声明放到最前面。
 // 所以改变自己的固有写法，模仿作者这种大佬级别的代码。

原本担心题目会比较旧，但作者用C语言写的答案可以帮自己复习C语言相关的知识。记得大一学了面向过程的C之后就立马学C++了，所以自己的C其实写的很少。操作系统、编译原理也并没有好好用C写代码。代码真的写太少了。

2 How would you implement bit vectors using bitwise logical operations (such as and, or and shift)?

如何使用位逻辑运算实现位向量？

32位系统中，实现步骤¹：

（1）、找到数据i所对应的字节位置

i / 32 相当于位操作 i >> 5

（2）、找到数据i对应的字节中位位置

i % 32 相当于位操作 i & 0x1F (0x1F 是31)

m mod n 运算，当n = 2的X次幂的时候,m mod n = m & (n-1) ，这里32为2^5,所以是 i & 0X1F

n=2^x 写成二进制：1后面x个0，m % n就是m的低x位。

n-1=2^x-1 写成二进制：x个1，m & (n-1)就是m的低x位。

（3）、判断某位是否为1，如果是就置为1

数字a的第i位是1: a & (1 << i)

将数据a的第i位置1: a | (1 << i)

writer’s answer:

 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

#include <stdio.h>
#include <stdlib.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N / BITSPERWORD];
void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i)
{
    a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}
int main(void)
{
    int i;
    for (i = 0; i < N; i++)
        clr(i);
    while (scanf("%d", &i) != EOF)
        set(i);
    for (i = 0; i < N; i++)
        if (test(i))
            printf("%d\n", i);
    return 0;
}

测试结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

(base) chengjing@Anjana-MacBook-Pro column1 % gcc 2.c
(base) chengjing@Anjana-MacBook-Pro column1 % ./a.out
7 23 1 9 45 88 99999 23343 47581
1D
7
9
23
45
88
23343
47581
99999

3 Run-time efficiency was an important part of the design goal, and the resulting program was efficient enough. Implement the bitmap sort on your system and measure its run time; how does it compare to the system sort and to the sorts in Problem 1? Assume that n is 10,000,000, and that the input file contains 1,000,000 integers.

顺序：

 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
57
58
59

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
clock_t start, stop;
double duration;
// bitmap sort
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N / BITSPERWORD];
void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i)
{
    a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}
// system sort
int intcomp(int *x, int *y)
{
    return *x - *y;
}
int b[N];
int main(void)
{
    // bitmap sort
    start = clock();
    int i;
    for (i = 0; i < N; i++)
        clr(i);
    for (int i = 0; i < N; i++)
    {
        set(i);
    }
    for (i = 0; i < N; i++)
        test(i);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("bitmap sort: %lf\n", duration);

    // system sort
    start = clock();
    for (int i = 0; i < N; i++)
    {
        b[i] = i;
    }
    qsort(b, N, sizeof(int), intcomp);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("system sort: %lf\n", duration);

    return 0;
}

bitmap sort: 0.083938

system sort: 0.069051

逆序：

 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
57
58
59

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
clock_t start, stop;
double duration;
// bitmap sort
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N / BITSPERWORD];
void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i)
{
    a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}
// system sort
int intcomp(int *x, int *y)
{
    return *x - *y;
}
int b[N];
int main(void)
{
    // bitmap sort
    start = clock();
    int i;
    for (i = 0; i < N; i++)
        clr(i);
    for (int i = 0; i < N; i++)
    {
        set(N - i);
    }
    for (i = 0; i < N; i++)
        test(i);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("bitmap sort: %lf\n", duration);

    // system sort
    start = clock();
    for (int i = 0; i < N; i++)
    {
        b[i] = N - i;
    }
    qsort(b, N, sizeof(int), intcomp);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("system sort: %lf\n", duration);
    
    return 0;
}

bitmap sort: 0.078902

system sort: 0.268980

4 If you take Problem 3 seriously, you will face the problem of generating k integers less than n without duplicates. The simplest approach uses the first k positive integers. This extreme data set won’t alter the run time of the bitmap method by much, but it might skew the run time of a system sort. How could you generate a file of k unique random integers between 0 and n – 1 in random order? Strive for a short program that is also efficient.

产生随机数

C++中没有自带的random函数，要实现随机数的生成就需要使用rand()和srand()

不过，由于rand()的内部实现是用线性同余法做的，所以生成的并不是真正的随机数，而是在一定范围内可看为随机的伪随机数。

1、rand()

rand()会返回一随机数值, 范围在0至RAND_MAX间。

RAND_MAX定义在stdlib.h, 其值为 2147483647(2^31-1)。

#define RAND_MAX 0x7fffffff

2、srand()

srand()可用来设置rand()产生随机数时的随机数种子。通过设置不同的种子获取不同的随机数序列。

可以利用srand((int)(time(NULL))或srand((int)(time(0))的方法，利用系统时钟，产生不同的随机数种子。不过要调用time()，需要加入头文件<ctime>或<time.h>。

3、其他随机数的范围通式

产生一定范围随机数的通用表示公式：

要取得[0,n) 就是rand() % n 表示 从0到n-1的数

要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;

要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;

要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;

通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。

要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。

要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。

 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
57
58
59
60
61
62
63

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
clock_t start, stop;
double duration;
// bitmap sort
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N / BITSPERWORD];
void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i)
{
    a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}
// system sort
int intcomp(int *x, int *y)
{
    return *x - *y;
}
int b[N];
int main(void)
{
    srand((int)time(NULL));
  
    // bitmap sort
    start = clock();
    int i;
    for (i = 0; i < N; i++)
        clr(i);
    for (int i = 0; i < N; i++)
    {
        int t=rand()%N;
        set(t);
    }
    for (i = 0; i < N; i++)
        test(i);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("bitmap sort: %lf\n", duration);

    // system sort
    start = clock();
    for (int i = 0; i < N; i++)
    {
        int t=rand()%N;
        b[i] = t;
    }
    qsort(b, N, sizeof(int), intcomp);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("system sort: %lf\n", duration);

    return 0;
}

bitmap sort: 0.090350

system sort: 0.073280

5 The programmer said that he had about a megabyte of free storage, but the code we sketched uses 1.25 megabytes. He was able to scrounge the extra space without much trouble. If the megabyte had been a hard and fast boundary, what would you have recommended? What is the run time of your algorithm?

使用bitmap:

1MB可以表示 8*10^6b=800万个数字

1.25MB可以表示 1.25*8*10^6b=10^7=1000万个数字

Consider a two-pass algorithm. 两趟算法

1000万/2=500万

500万数字=0.625*8*10^6b=0.625MB空间

首先使用0.625MB空间来排序 0 ~ 4 999 999 之间的整数，然后在第二趟排序 5 000 000 ~ 9 999 999 的整数。k 趟算法可以在 kn 的时间开销和 n / k 的空间开销内完成对最多 n 个小于 n 的无重复正整数的排序。

6 What would you recommend to the programmer if, instead of saying that each integer could appear at most once, he told you that each integer could appear at most ten times? How would your solution change as a function of the amount of available storage?

如果每个整数最多出现 10 次，那么我们就可以使用 4 位 (2^3<10<2^4) 的半字节来统计它出现的次数。

利用习题 5 的答案，可以使用 10 000 000 / 2 个字节在 1 趟内完成对整个文件的排序，或使用 10 000 000 / 2k 个字节在 k 趟内完成对整个文件的排序。

7 [R. Weil] The program as sketched has several flaws. The first is that it assumes that no integer appears twice in the input. What happens if one does show up more than once? How could the program be modified to call an error function in that case? What happens when an input integer is less than zero or greater than or equal to n? What if an input is not numeric? What should a program do under those circumstances? What other sanity checks could the program incorporate? Describe small data sets that test the program, including its proper handling of these and other ill-behaved cases.

sanity checks:

• one show up more than once: use set
• input integer is <0 or >=n
• input is not numeric

8 When the programmer faced the problem, all toll-free phone numbers in the United States had the 800 area code. Toll-free codes now include 800, 877 and 888, and the list is growing. How would you sort all of the toll-free numbers using only a megabyte? How can you store a set of toll-free numbers to allow very rapid lookup to determine whether a given toll-free number is available or already taken?

建立set，查找时间是O(logn)

9 One problem with trading more space to use less time is that initializing the space can itself take a great deal of time. Show how to circumvent this problem by designing a technique to initialize an entry of a vector to zero the first time it is accessed. Your scheme should use constant time for initialization and for each vector access, and use extra space proportional to the size of the vector. Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is dear and the vector is sparse.

One problem with trading more space to use less time is that initializing the space can itself take a great deal of time.

• space is cheap
• time is dear
• the vector is sparse

reduces initializtion time by using even more space

借助于两个额外的n元向量from、to和一个整数top，可以使用标识来初始化向量data[0..n-l]。如果元素data[i]已初始化，那么from[i]<top并且to[from[i]] = i。因此，from是一个简单的标识，to和top一起确保了from中不会被写入内存里的随机内容。

变量top初始为0，下面的代码实现对数组元素i的首次访问：

1
2
3
4

from[i] = top
to[top] = i
data[i] = 0
top++

10 Before the days of low-cost overnight deliveries, a store allowed customers to order items over the telephone, which they picked up a few days later. The store’s database used the customer’s telephone number as the primary key for retrieval (customers know their phone numbers and the keys are close to unique). How would you organize the store’s database to allow orders to be inserted and retrieved efficiently?

商店将纸质订单表格放在 10 * 10 的箱数组中，使用客户电话号码的最后两位作为散列索引。当客户打电话下订单时，将订单放到适当的箱中。当客户来取商品时，销售人员顺序搜索对应箱中的订单——这就是经典的“用顺序搜索来解决冲突的开放散列”。电话号码的最后两位数字非常接近于随机，因此是非常理想的散列函数，而最前面的两位数字则很不理想——为什么？一些市政机关使用类似的方案在记事本中记录信息。