这个页面帮助了我:http ://comments.gmane.org/gmane.comp.programming.algogeeks/30667
但是让我看看我能不能解释一下。
基本上问题是:如果向量足够大,将向量初始化为全 0 会花费大量时间。那么,我们如何通过使用更多空间来避免初始化为 0 呢?即我们如何区分这个向量中的随机数据和我们故意放在那里的数据?
Bentley 的解决方案是使用与数据向量大小相同的“from”(映射)和“to”(签名 [实际上只是从索引的反向映射])向量和“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[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
.
其余为 top = 2...n
高温高压