编程珠玑 1-9 证明

似乎找到了丢失的脑子
中午书到货了,下午上课时翻了翻编程珠玑,对于第一章的习题 9 比较困惑

问题大致如下: 空间很廉价,时间很宝贵且向量很稀疏的情况下,如何设计一种技术,在第一次访问向量的项时将其初始化为 0

通俗点说就是有一个很长的数组,只会用到其中几个元素。所以不想去遍历数组将每一项初始化为 0, 设计一种惰性的初始化方法

书后解法: 借助于两个长度为 n 的数组 fromto 和一个整型变量 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] < topfrom[i] < 1from[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 成立

给出如下的数学证明:

1) top = 0 时,因为 from[i] >= 0 恒成立,所以 from[i] >= top 恒成立

2) top > 0 时,利用反证法,存在索引 i (i ∈ {未访问的 i}),有 from[i] < top && to[from[i]] == i 成立。即 to[x] = i (x < top, x = from[i], i ∈ {未访问的 i}) 成立。但是根据前提对于任意的 x < topto[x] = i (i ∈ {访问过的 i}), 与假设产生矛盾。所以猜想正确