8

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

4

9 回答 9

20

是的

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

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 字节（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例如，而在此之前它会被禁止。代价是访问变慢了，因为我们得到了一个除法和模数（什么时候我们将得到一个标准化的操作，一次返回两个结果？）。

于 2012-05-29T11:02:29.183 回答
12

您不能修改n内存中的位置小于O(n)（即使您的硬件足够小n，可能允许恒定时间操作将某些对齐良好的内存块归零，例如闪存）。

但是，如果练习的对象有点横向思维，那么您可以编写一个表示“稀疏”数组的类。稀疏数组的一般思想是您保留一个集合（可能是 a map，尽管取决于使用情况，它可能不是全部），并且当您查找索引时，如果它不在基础集合中，则返回0.

如果您可以在 O(1) 中清除基础集合，那么您可以在 O(1) 中将稀疏数组归零。清除 astd::map通常不是地图大小的恒定时间，因为所有这些节点都需要被释放。但是您可以设计一个可以O(1)通过将整个树从“我的地图内容”移动到“我为将来使用而保留的节点树”来清除的集合。缺点只是这个“保留”空间仍然被分配，有点像 avector变小时发生的情况。

于 2012-05-29T10:51:11.843 回答
9

只要您接受一个非常大的常数因子，当然可以在 O(1) 中将数组归零：

void zero_out_array_in_constant_time(void* a, size_t n)
{
    char* p = (char*) a;
    for (size_t i = 0; i < std::numeric_limits<size_t>::max(); ++i)
    {
        p[i % n] = 0;
    }
}

无论数组的大小如何，这将始终采取相同数量的步骤，因此它是 O(1)。

于 2012-05-29T10:40:56.920 回答
4

不。

您不能在少于 O(N) 的时间内访问 N 元素集合的每个成员。

正如 Mike Kwan 所观察到的，您可能会将成本从运行时转移到编译时，但这不会改变操作的计算复杂性。

于 2012-05-29T10:33:25.870 回答
2

显然不可能在固定的时间长度内初始化任意大小的数组。但是，完全有可能创建一个类似数组的 ADT，它可以在整个使用过程中分摊初始化数组的成本。然而，通常的结构需要 3 倍以上的存储空间。到白衣：

template <typename T, size_t arr_size>
class NoInitArray
{
    std::vector<T> storage;

    // Note that 'lookup' and 'check' are not initialized, and may contain
    // arbitrary garbage.
    size_t lookup[arr_size];
    size_t check[arr_size];
public:
    T& operator[](size_t pos)
    {
        // find out where we actually stored the entry for (*this)[pos].
        // This could be garbage.
        size_t storage_loc=lookup[pos];

        // Check to see that the storage_loc we found is valid
        if (storage_loc < storage.size() && check[storage_loc] == pos)
        {
            // everything checks, return the reference.
            return storage[storage_loc];
        }
        else
        {
            // storage hasn't yet been allocated/initialized for (*this)[pos].
            // allocate storage:
            storage_loc=storage.size();
            storage.push_back(T());

            // put entries in lookup and check so we can find 
            // the proper spot later:
            lookup[pos]=storage_loc;
            check[storage_loc]=pos;

            // everything's set up, return appropriate reference:
            return storage.back();
        }
    }
};

如果是某种不需要销毁的类型，至少在概念上，可以很容易地添加一个clear()成员来清空这样一个数组的内容。T

于 2012-05-29T11:02:25.680 回答
1

在运行时不可能将O(1). 这是直观的，因为没有允许在固定时间内对任意大小的内存块进行值设置的语言机制。您可以做的最接近的是：

int blah[100] = {0};

这将允许在编译时进行初始化。在运行时，memset通常是最快的，但会是O(N). 但是，在特定数组类型上使用存在相关问题。memset

于 2012-05-29T10:28:15.760 回答
1

我喜欢 Eli Bendersky 的网页http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time，他将解决方案归功于著名的《计算机算法的设计与分析》一书啊，霍普克罗夫特和厄尔曼。这确实是初始化的 O(1) 时间复杂度，而不是 O(N)。空间需求是 O(N) 额外的存储空间，但分配这个空间也是 O(1)，因为空间充满了垃圾。出于理论上的原因，我喜欢这个，但我认为如果您需要重复初始化一个非常大的数组，并且每次只访问数组中相对较少数量的位置，它对于实现一些算法也可能具有实用价值。Bendersky 提供了该算法的 C++ 实现。

一个非常纯粹的理论家可能会开始担心 N 需要 O(log(N)) 个数字，但我忽略了这个细节，这可能需要仔细查看计算机的数学模型。The Art of Computer Programming第 1 卷可能给出了 Knuth 对这个问题的看法。

于 2017-07-18T11:25:56.580 回答
0

虽然仍然是 O(N)，但映射到硬件辅助操作（如清除整个缓存行或内存页面）的实现可以以每个字 <1 个周期运行。

实际上，重复史蒂夫·杰索普的想法……

如果您有硬件支持以同时清除任意大量内存，则可以这样做。如果您设置一个任意大的数组，那么您还可以设置一个具有硬件并行性的任意大内存，以便单个复位引脚同时同时清除每个寄存器。这条线必须由任意大的逻辑门驱动（消耗任意大的功率），电路走线必须任意短（以克服 R/C 延迟）（或超导），但这些事情很常见在异次元空间。

于 2012-05-29T10:51:27.633 回答
0

可以使用 O(1) 时间，甚至 O(1) 额外空间来完成。

我解释了大卫在另一个答案中提到的 O(1) 时间解决方案，但它使用了 2n 个额外的内存。

存在更好的算法，它只需要 1 位额外的内存。
请参阅我刚刚写的关于该主题的文章。
它还解释了大卫提到的算法，还有一些，以及当今最先进的算法。它还具有后者的实现。

在一个简短的解释中（因为我只是重复这篇文章），它巧妙地采用了大卫回答中提出的算法，并在原地完成所有工作，同时只使用（非常）很少的额外内存。

于 2020-12-08T14:07:49.443 回答