通过使用更多空间来实现恒定的初始化时间-编程珍珠 - 第 1 栏

Question

我正在阅读《Programming Pearls》，我对其中一个解决方案的解释感到非常困惑——第 1 列中的问题 9。

问题是：当使用位图数据表示一组整数时，第一阶段将该组初始化为空。但初始化空间本身可能会花费大量时间。展示如何通过设计一种在第一次访问向量时将向量条目初始化为零的技术来规避此问题。

答案是：初始化向量数据[0...n-1] 的效果可以通过包含在两个附加 n 元素向量from和to以及整数top 中的签名来实现。如果元素 data [i] 已初始化，则from [i] < top且to [*from*[i]] = i。因此，from是一个简单的签名，to和top一起确保from不会被内存的随机内容意外签名。

这个答案我已经读过好几遍了。我不明白。

有人可以解释一下吗？

谢谢，

Answer 1

此页面帮助了我：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) 插入了一个元素（即 top > 0，假设它是 1），因为from[i] < top=> from[i] = 0。然而，我们在数据数组中插入了一个元素，因此我们显式设置了to[from[i]] = i。

其余部分如下：top = 2...n

华泰