如何在 O(1) 时间内将数组归零？

有没有一种方法可以将数组归零，时间复杂度为 O(1)？很明显，这可以通过for-loop、memset来完成。但它们的时间复杂度不是O(1)。

Yes

但不是任何数组。它需要一个专门为此工作而设计的数组。

template <typename T, size_t N>
class Array {
public:
    Array(): generation(0) {}

    void clear() {
        // FIXME: deal with overflow
        ++generation;
    }

    T get(std::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(std::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;
};

原理很简单：

• 我们使用以下方法定义一个纪元generation属性
• 当设置一个项目时，会记录该项目被设置的纪元
• 只能看到当前纪元的项目
• 因此，清除相当于增加纪元计数器

该方法有两个问题：

• 存储增加：对于每个项目，我们存储一个纪元
• 生成计数器溢出：有一个最大纪元数

后者可以使用真正的大整数来阻止（uint64_t以更多存储为代价）。

前者是自然的结果，一种可能的解决方案是使用存储桶来淡化该问题，例如将最多 64 个项目与单个计数器关联，并使用一个位掩码来标识哪些项目在该计数器内有效。

EDIT：只是想回到桶的想法。

原来的解决方案有一个每个元素 8 字节（64 位）的开销（如果已经 8 字节对齐）。根据存储的元素，这可能是也可能不是一个大问题。

如果是大事，想法是使用桶；当然，就像所有的权衡一样，它会进一步减慢访问速度。

template <typename T>
class BucketArray {
public:
     BucketArray(): generation(0), mask(0) {}
     
     T get(std::size_t index, std::size_t gen) const {
         assert(index < 64);

         return gen == generation and (mask & (1 << index)) ?
                data[index] : T{};
     }

     void set(std::size_t index, T t, std::size_t gen) {
         assert(index < 64);

         if (generation < gen) { mask = 0; generation = gen; }

         mask |= (1 << index);
         data[index] = t;
     }

private:
     std::uint64_t generation;
     std::uint64_t mask;
     T data[64];
};

请注意，这个包含固定数量元素的小数组（我们实际上可以对其进行模板化并静态检查它是否小于或等于 64）仅具有 16 字节的开销。这意味着我们有一个每个元素 2 位的开销.

template <typename T, size_t N>
class Array {
    typedef BucketArray<T> Bucket;
public:
    Array(): generation(0) {}
    
    void clear() { ++generation; }

    T get(std::size_t i) const {
        if (i >= N) { throw ... }

        Bucket const& bucket = data[i / 64];
        return bucket.get(i % 64, generation);
    }

    void set(std::size_t i, T t) {
        if (i >= N) { throw ... }

        Bucket& bucket = data[i / 64];
        bucket.set(i % 64, t, generation);
    }

private:
    std::uint64_t generation;
    Bucket data[N / 64 + 1];
};

我们将空间开销降低了... 32。现在数组甚至可以用来存储char例如，而在此之前，这将是令人望而却步的。代价是访问速度变慢，因为我们进行了划分and取模（什么时候我们会得到一种标准化的操作，一次返回两个结果？）。