《编程珠玑》第 10 章──节省空间

节省空间的同时,程序变小后加载也更快,更容易填入高速缓存中;此外,需要操纵的数据变少通常意味着操作时间减少。

示例程序

如图来存储一些点:

稀疏矩阵的一种浅显的表示就是使用数组表示所有的列,同时使用链表来表示给定列中的活跃元素。

搜索的代码:

1
2
3
4
for (p = colhead[i]; p != NULL; p = p->next)
if p->row == j
return p->pointnum
return -1

上面的版本存储指针花了比较多的空间,下面要修改成没有指针的版本。

搜索的代码:

1
2
3
4
for k [firstcol[i], firstcol[i+1]]
if row[k] == j
return pointnum[k]
return -1

数据空间技术

  • 不储存,重新计算
  • 稀疏数据结构
  • 数据压缩
  • 分配策略,比如动态分配
  • 垃圾回收

代码空间技术

  • 函数定义
  • 解释程序
  • 翻译成机器语言

习题

1. 20 世纪 70 年代末期,Stuart Feldmen 构建了一个 Fortran 77 编译器,它刚好能装入 64KB 的代码空间。为了节省空间,他将一些关键记录中的整数压缩存储到 4 位的字段中。在去除该处理并将这些字段保存到 8 位中,他发现尽管数据空间增加了数百个字节,但是整个程序的大小却下降了好几千个字节。为什么?

虽然数据空间增加了,但是代码空间减少了。因为访问未压缩字段所需要的机器指令则少一些。

2. 如何编写程序来构建 10.2 节中所描述的系数矩阵数据结构?你能够为该任务找出简单但空间效率很高的其他数据结构么?

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
struct location {
unsigned int x;
unsigned int y;
};
struct point {
location l;
int value;
};

class Solution {
public:
vector<int> pointnum;
vector<int> row;
vector<int> firstcol;

Solution() {
firstcol = vector<int>(200, 0);
}

bool add(point p) {
firstcol[p.l.x] = count + 1;
row.emplace_back(p.l.y);
pointnum.emplace_back(p.value);
++count;
return false;
}

int search(location l) {
for (int i = 0; i < firstcol[l.x]; ++i) {
if (row[i] == l.y) {
return pointnum[i];
}
}
return -1;
}

private:
int count = 0;
};

可以使用二分搜索来代替顺序搜索,这要求 y 轴插入时应该排序。

4. 请研究一下非计算机应用(比如年鉴以及其他参考书)中的数据,说明如何进行空间节省。

对于任意一年而言,1 月 1 日是星期几有 7 种可能,闰年还是非闰年有两种可能,两数相乘得到 14。

6. 在 10.3 节中对数据压缩的讨论曾提及使用 /% 运算解码 10×a+b10\times a + b 的问题。试探讨使用逻辑运算或查表来替换那些运算时所涉及的时间和空间折中。

编码使用 c = (a << 4) | b,解码时使用 a = c >> 4b = c & 0xF。移位和掩码通常闭乘除法快,而且十六进制转储等常用工具能够以可读的形式显示解码后的数据。

8. 浅显的数据表示方法为日期(MMDDYYYY)分配了 8 个字节的空间,为社会保障号(DDD-DD-DDDD)分配了 9 个字节的空间,为名字分配了 25 个字节(其中姓 14 个字节、名 10 个字节、中间名 1 个字节)的空间。如果空间紧缺,你该如何减少这些需求呢?

月份第一个 M 范围 0 到 1,第二个 M 范围 0 到 9,只需要 1 + 4 位。日期第一个 D 范围 0 到 3,第二个 D 范围 0 到 9,所以需要 2 + 4 位。年份最多是 16 位。所以总共需要 5 + 6 + 16 = 27 位,用一个 int 即可。