如何清零O（1）中的数组？ [英] How to zero out array in O(1)?
问题描述
有一种方法来清零数组与时间复杂度O（1）？很明显，这可以通过for-loop，memset来完成。但是他们的时间复杂度不是O（1）。
Is there an way to zero out an array in with time complexsity O(1)? It's obvious that this can be done by for-loop, memset. But their time complexity are not O(1).
推荐答案
是
任何数组。它需要一个为此工作的数组。
However not any array. It takes an array that has been crafted for this to work.
template <typename T, size_t N>
class Array {
public:
Array(): generation(0) {}
void clear() {
// FIXME: deal with overflow
++generation;
}
T get(size_t i) const {
if (i >= N) { throw std::runtime_error("out of range"); }
TimedT const& t = data[i];
return t.second == generation ? t.first : T{};
}
void set(size_t i, T t) {
if (i >= N) { throw std::runtime_error("out of range"); }
data[i] = std::make_pair(t, generation);
}
private:
typedef std::pair<T, unsigned> TimedT;
TimedT data[N];
unsigned generation;
};
原理很简单：
- 当设置项目时，我们使用
生成属性 - 定义一个纪元已记录
- 只有当前纪元的项目才会显示
- 清除等同于递增纪元计数器
- we define an epoch using the
generationattribute - when an item is set, the epoch in which it has been set is recorded
- only items of the current epoch can be seen
- clearing is thus equivalent to incrementing the epoch counter
此方法有两个问题：
- item我们存储一个纪元
- 生成计数器溢出：有一些作为最大的纪元数
后者可以使用真正的大整数（ uint64_t ，以更多存储为代价）来阻止。
The latter can be thwarted using a real big integer (uint64_t at the cost of more storage).
前者是一个自然的结果，一个可能的解决方案是使用桶来通过例如多达64个项目关联到一个单一的计数器和位掩码识别哪些在这个计数器内有效，来减少问题。
The former is a natural consequence, one possible solution is to use buckets to downplay the issue by having for example up to 64 items associated to a single counter and a bitmask identifying which are valid within this counter.
EDIT ：只是想回到桶的想法。
EDIT: just wanted to get back on the buckets idea.
原始解决方案的每个元素8字节（64位）的开销（如果已经8字节对齐）。根据存储的元素，它可能会或可能不是一个大问题。
The original solution has an overhead of 8 bytes (64 bits) per element (if already 8-bytes aligned). Depending on the elements stored it might or might not be a big deal.
如果这是一个大问题，想法是使用桶;当然像所有的权衡，它减慢访问更多。
If it is a big deal, the idea is to use buckets; of course like all trade-off it slows down access even more.
template <typename T>
class BucketArray {
public:
BucketArray(): generation(0), mask(0) {}
T get(size_t index, size_t gen) const {
assert(index < 64);
return gen == generation and (mask & (1 << index)) ?
data[index] : T{};
}
void set(size_t index, T t, size_t gen) {
assert(index < 64);
if (generation < gen) { mask = 0; generation = gen; }
mask |= (1 << index);
data[index] = t;
}
private:
uint64_t generation;
uint64_t mask;
T data[64];
};
请注意，这个小数组的固定数量的元素（我们可以实际模板和静态检查低于或等于64）只有16字节的开销。这意味着我们有每个元素2位的开销
Note that this small array of a fixed number of elements (we could actually template this and statically check it's inferior or equal to 64) only has 16 bytes of overhead. This means we have an overhead of 2 bits per element.
template <typename T, size_t N>
class Array {
typedef BucketArray<T> Bucket;
public:
Array(): generation(0) {}
void clear() { ++generation; }
T get(size_t i) const {
if (i >= N) { throw ... }
Bucket const& bucket = data[i / 64];
return bucket.get(i % 64, generation);
}
void set(size_t i, T t) {
if (i >= N) { throw ... }
Bucket& bucket = data[i / 64];
bucket.set(i % 64, t, generation);
}
private:
uint64_t generation;
Bucket data[N / 64 + 1];
};
我们的空间开销降低了一个因子... 32.现在数组甚至可以用于存储 char ，例如，之前它将被禁止。成本是访问变得更慢，因为我们得到一个除法和模数（当我们将得到一个标准化的操作，一次返回两个结果。）。
We got the space overhead down by a factor of... 32. Now the array can even be used to store char for example, whereas before it would have been prohibitive. The cost is that access got slower, as we get a division and modulo (when we will get a standardized operation that returns both results in one shot ?).
这篇关于如何清零O（1）中的数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
