有没有一种方法可以将时间复杂度为O(1)的数组归零?显然,这可以通过for循环,内存集来完成。但是它们的时间复杂度不是O(1)。

最佳答案


但是没有任何数组。它需要一个专门为此设计的数组。

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属性
  • 定义一个纪元
  • 设置项目时,记录已设置项目的时期
  • 只能看到当前纪元的项目
  • 因此,清除
  • 等效于增加时期计数器

  • 该方法有两个问题:
  • 存储增加:对于每个项目,我们存储一个时期
  • 生成计数器溢出:epoch最大次数为

  • 可以使用一个大整数(uint64_t以更大的存储空间为代价)来阻止后者。
    前者是很自然的结果,一种可能的解决方案是使用存储桶,例如通过使多达64个与单个计数器相关联的项以及标识该计数器中有效的位掩码,来淡化问题。

    编辑:只是想重新了解一下桶的想法。
    原始解决方案的每个元素(如果已对齐8字节)的开销为8个字节(64位)。根据存储的元素,它可能不是很重要。
    如果这很重要,那就是使用存储桶。当然,像所有折衷方案一样,它甚至会进一步降低访问速度。
    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,而以前这是禁止的。代价是访问速度变慢,因为我们得到了除法和模(当我们得到标准化的操作时,一次返回两个结果都将返回?)。

    关于c++ - 如何将O(1)中的数组归零?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10797284/

    10-12 12:36
    查看更多