我正在阅读"编程珍珠"，我对其中一个解决方案解释感到非常困惑 - 第 1 列中的问题 9。
问题是：当使用位图数据表示一组整数时，第一阶段将该集初始化为空。但是初始化空间本身可能需要大量时间。演示如何通过设计一种技术来规避此问题，以便在第一次访问向量时将向量的条目初始化为零。
答案是：初始化向量数据[0...n-1]的效果可以通过签名来完成包含在两个额外的 n 元素向量 from 和 to 以及一个整数 top 中。如果元素data[i] 已被初始化，然后从 [i] <<em>顶部和 to[*from*[i]] = i。因此从是一个简单的签名，并将 to 和 top 一起确保 from 不会意外地被内存中的随机内容签名。
这个答案我已经读了好几遍了。我不明白。
有人可以解释一下吗？
谢谢
这个页面帮助了我：http://comments.gmane.org/gmane.comp.programming.algogeeks/30667
但让我看看我是否可以解释一下。
基本上问题是：如果向量足够大，将向量初始化为所有 0 需要相当长的时间。那么，我们如何通过使用更多空间来避免初始化为 0？即我们如何区分这个向量中的随机数据和我们故意放在那里的数据？
Bentley 的解决方案是使用与数据向量大小相同的"from"（映射）和"to"（签名 [实际上只是指向 from 索引的反向映射]）向量，以及"top"，即到目前为止数据数组中的元素数。重要的是，from[i] < top如下所述。
使用解决方案中的示例：我们声明一个数据数组并将元素数设置为零：
top = 0
data = int array of integers of size 1,000,000
(all random values since we did not initialize it)
在索引 1 处插入一个元素（在本例中为 i=1）。但是现在我们怎么知道这不是一个随机值呢？我们使用地图和签名。"from"的索引等于数据的索引。
from[i] = top
to[top] = i
data[i] = 0 (I don't think it matters whether you set it to 0 or your intended value of 3)
top++ (top is now 1)
所以你可能会说，如果to[from[i]] == i偶然呢？好吧，既然我们声明from[i] < top，这是不可能的。
检查以下两种情况：
A） 数据数组中尚未插入任何元素（即 top = 0）这意味着from[i] < 0它不是有效的数组索引。所以这是不可能的。
B）插入了一个元素（即顶部>0，假设它是1）由于from[i] < top => from[i] = 0 . 但是，我们在数据数组中插入了一个元素，因此我们显式设置了to[from[i]] = i 。
其余部分如下，顶部 = 2...n
呵呵
我发现以下链接中的帖子对于理解常量时间初始化技巧背后的想法非常有帮助。
链接： http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/
希望对您有所帮助-