logo标签列表

使用更多的空间进行初始化可以实现常数时间-编程珠玑-第一章

bitmapinitializationprogramming-pearls
4
我正在阅读《编程珠玑》，但在第一列的问题9中，有一个解决方案的解释让我感到非常困惑。
问题是：使用位图数据表示一组整数时，第一阶段将集合初始化为空。但初始化空间本身可能需要很长时间。展示如何通过设计技术来初始化向量的条目为零，以绕过此问题。
答案是：初始化向量 data [0…n-1] 的效果可以通过包含两个额外的n元向量 from 和 to 以及整数 top 的签名来实现。如果已经初始化元素 data [i]，则 from [i] < top 并且 to [*from* [i]] = i。因此， from 是一个简单的签名，而 to 和 top 共同确保 from 不会被内存的随机内容意外签名。
我已经多次阅读了这个答案，但仍然不理解它。能否有人解释一下？
谢谢，
2个回答
5

这个页面帮助了我：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，其余部分如下。
希望对你有所帮助。
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接