似乎找到了丢失的脑子
中午书到货了，下午上课时翻了翻编程珠玑，对于第一章的习题 9 比较困惑
问题大致如下： 空间很廉价，时间很宝贵且向量很稀疏的情况下，如何设计一种技术，在第一次访问向量的项时将其初始化为 0
通俗点说就是有一个很长的数组，只会用到其中几个元素。所以不想去遍历数组将每一项初始化为 0， 设计一种惰性的初始化方法
书后解法：
借助于两个长度为 n 的数组 from 和 to 和一个整型变量 top。在访问数组的某一项 i 时先判断
from[i] < top && to[from[i]] == i。如果成立则此项已经初始化过，如果不成立则执行下面操作初始化
from[i] = top;
to[top] = i;
data[i] = 0;
top++; // top 初始值为 0
好吧，你可能对于这个问题会想 from[i] 的值如果为一个负数，那么 to[from[i]] 会是什么？
这的确是书中没有提及的，不过很容易解决：
对于 4 bytes 的 int 类型来说，其范围为 –2,147,483,648 到 2,147,483,647
那么对 from[i] 的值加上 2,147,483,648，这样便转移到安全的范围了
回到这个问题的解决方法上来，蠢作者起初认为，这个方法仅保证了已经被初始化过的项不会被再次初始化，存在随机的值使得条件成立，不过概率很小
但是仔细考虑觉得给出的第二个条件比较奇怪 为什么特意判断 to[from[i]] == i 呢
于是在纸上写写画画， x 代表未经初始化的随机值：
index 0 1 2
data x x x
from x x x
to x x x
top = 0
访问 index = 1 由于 from[i] < top 不满足，进行初始化
index 0 1 2
data x 0 x
from x 0 x
to 1 x x
top = 1
如果访问 index = 0
那么要满足 from[i] < top 即 from[i] < 1 则 from[i] 只能为 0
而第二个条件则是 to[from[i]] == i 显然不满足
index 0 1 2
data x 0 x
from x 0 x
to 1 x x
凭感觉猜测：不存在一个未访问过的 i 使得 from[i] < top && to[from[i]] == i 成立
给出如下的数学证明：
top = 0时，因为from[i] >= 0恒成立，所以from[i] >= top恒成立top > 0时，利用反证法，存在索引i (i ∈ {未访问的 i})，有from[i] < top && to[from[i]] == i成立。即to[x] = i (x < top, x = from[i], i ∈ {未访问的 i})成立。但是根据前提对于任意的x < top有to[x] = i (i ∈ {访问过的 i})， 与假设产生矛盾。所以猜想正确