3

假设我有一个数组：

bool eleme[1000000] = {false};

在我的代码中的某个时刻，我n将此数组的一些第一个元素更改为true. 之后我想确保数组的所有元素都是false. 所以我这样做：

for (int i =0; i < n; ++i)     
       eleme[i] = false;

哪个费用Θ(n)。

有没有办法在恒定时间内做到这一点？例如像 make_false(eleme, n);

4

4 回答 4

3

一般答案
如果你想修改内存中的 N 个元素，那最终将是一个 O(N) 操作，不管你是否可以用一个命令来表达它，比如memsetor std::fill。

如果您设计算法以使尽可能多的数组位于缓存中，则操作将大大加快。使用优化的内置命令memset也有助于加快速度。

建议 1
但是，常量时间数组初始化有一个旧的算法技巧，它也适用于您的情况（常量时间数组重置）——但代价是大量额外的内存使用。

它如下所示：除了主数组之外A1，您还分配了第二个A2相同长度的数组和一个S大小为 N 的堆栈。这些结构都不需要初始化（并且仅分配它们可以说是 O(1 ） 手术）。您还需要一个堆栈指针SP。

最初堆栈指针为 0（指向堆栈底部）。

每当你进入A1，比如说A1[i]=j，你设置A2[i]=SP，S[SP]=i并增加SP。

如果要检查是否A1[i]已设置某个条目，请查找A2[i]。如果A2[i]<SP，即小于堆栈指针的当前值，您就知道相应的堆栈条目SP[A2[i]]一定是您之前设置过的。如果该堆栈条目的值为i，A1[i]则为有效条目。否则它永远不会被初始化。

现在，为了重置 的所有条目A1，您只需将堆栈指针设置回 0。这是一个恒定时间操作。

我必须承认我从来没有遇到过我发现这个技巧真正有用的情况。通常memset，虽然不是恒定时间，但足够快。

Gonzalo Navarro 最近发表了一篇笔记，他在其中描述了一组进一步压缩额外数组的技巧，以便它们使用更少的空间，同时保持 O(1) 时间限制。

建议 2
另一种可能性是仅在必要时以惰性方式重置值。正如您所描述的，这利用了这样一个事实，即在重置时，实际上只会使用前几个元素中的一些元素。

这涉及在变量中维护尚未初始化（或在最近重置期间重置）的最左侧元素的索引，以及当A[i]要设置元素时，初始化（或重置）左侧之间的所有元素- 最未初始化的一个 和i。

要访问 index 处的元素i，请检查是否i小于最左侧未初始化的元素，在这种情况下返回A[i]; 否则它没有被初始化（或重置），所以你将初始化值（可能为 0）作为文字返回。

要重置数组，只需将最左侧未初始化元素的索引设置回 0，这是一个恒定时间操作。

当然，这意味着更改条目现在是 O(N) 操作，但如果您通常只设置数组的前几个元素，它永远不会变得非常昂贵。另请注意，两次重置之间所有操作的总成本仍然是 O(N)，因为每个元素将被重置不超过一次。

另一个重要的优点是缓存友好性：每次设置元素时，需要初始化的元素范围可能很小，并且比一次重置所有元素时更有可能完全在缓存中。

在 C++ 中，它可能看起来像这样：

template <typename T, std::size_t N, T init_val>
class FastResetArray
{
  std::array<T,N> _data;                // the array
  unsigned        _min_uninitialised;   // the left-most non-initialised element
public:
  FastResetArray()
    :_data(),_min_uninitialised(0)
  {}

  T at(const unsigned index) {
    return (index < _min_uninitialised ? _data[index] : init_val);
  }

  void set(const unsigned index, const T val) {
    if (index > _min_uninitialised)
      std::fill_n(begin(_data) + _min_uninitialised,
          index - _min_uninitialised,
          init_val);
    _data[index] = val;
    _min_uninitialised = index + 1;
  }

  void reset() {
    _min_uninitialised = 0;
  }
};

（请注意，在构造函数中，我将_min_uninitialised（最左侧未初始化元素的索引）设置为 0。由于默认构造std::array函数将整个数组初始化为零，我也可以设置为Nifinit_val为零。所以上面的实现无助于避免最初的 O(N) 初始化——我们只避免 O(N) in reset()。）

于 2012-10-13T03:30:30.667 回答
1

有没有办法在恒定时间内做到这一点[并且不访问超过n元素]？

不，你必须设置n元素，这将采取n步骤，因此 O(n)。

您可以通过不手动编写循环来使其运行得更快。我想你会发现：

std::fill(eleme, eleme+n, false);

比

for (int i =0; i < n; ++i)     
   eleme[i] = false;

即使它们具有相同的大 O 复杂性。

于 2012-10-13T03:16:10.057 回答
1

根据

http://en.wikipedia.org/wiki/Time_complexity#Constant_time

您的代码已经是常数时间

如果元素的数量是预先知道的并且不改变

从声明来看这似乎是真的

布尔元素[1000000] = {假};

于 2012-10-13T03:30:49.573 回答
0

如果数组中的元素数为 n（不是常数），则将该数组中的所有值初始化为 false 将始终处于线性时间。但是，如果您考虑一下，如果这个数组是某个更大算法的一部分，您通常可以找到一种不同的方法在恒定时间内解决您的问题（我做出这个假设是因为如果您正在初始化所有元素数组为“假”，那么您不必关心当前存储在那里的数据，那么为什么此时要对它做任何事情呢？）。

于 2012-10-13T07:03:32.840 回答