寻找具有 O(1) 索引和 O(log(n)) 插入和删除的数据容器 [英] Looking for a data container with O(1) indexing and O(log(n)) insertion and deletion

问题描述

我不确定这是否可能，但对我来说似乎有点合理，我正在寻找一种允许我执行这些操作的数据结构:

I'm not sure if it's possible but it seems a little bit reasonable to me, I'm looking for a data structure which allows me to do these operations:

• 用 O(log n) 插入一个项目
• 用 O(log n) 移除一个项目
• 查找/编辑 O(1) 中的第 k 个最小元素，用于任意 k(O(1) 索引)

当然，编辑不会导致元素顺序发生任何变化.使之成为可能的原因是我将以递增的顺序一个接一个地插入元素.因此，例如，如果我尝试第五次插入，我确信在这之前的所有四个元素都比它小，而在这之后的所有元素都会更大.

of course editing won't result in any change in the order of elements. and what makes it somehow possible is I'm going to insert elements one by one in increasing order. So if for example I try inserting for the fifth time, I'm sure all four elements before this one are smaller than it and all the elements after this this are going to be larger.

推荐答案

我不知道这样的数据容器是否可以实现请求的时间复杂度.但这里有几种方法，几乎​​可以实现这些复杂性.

I don't know if the requested time complexities are possible for such a data container. But here is a couple of approaches, which almost achieve these complexities.

第一个是 分层向量与 O(1) 插入和索引，但是 O(sqrt N) 删除.由于您预计此容器中只有大约 10000 个元素并且 sqrt(10000)/log(10000) = 7，因此您在这里几乎可以获得所需的性能.分层向量被实现为一个环形缓冲区数组，因此删除一个元素需要移动所有元素，在环形缓冲区中跟随它，并将一个元素从后面的每个环形缓冲区移动到它之前的一个；在此容器中进行索引意味着在环形缓冲区数组中进行索引，然后在环形缓冲区内进行索引.

First one is tiered vector with O(1) insertion and indexing, but O(sqrt N) deletion. Since you expect only about 10000 elements in this container and sqrt(10000)/log(10000) = 7, you get almost the required performance here. Tiered vector is implemented as an array of ring-buffers, so deleting an element requires moving all elements, following it in the ring-buffer, and moving one element from each of the following ring-buffers to the one, preceding it; indexing in this container means indexing in the array of ring-buffers and then indexing inside the ring-buffer.

可以创建一个不同的容器，与分层向量非常相似，具有完全相同的复杂性，但工作速度更快一些，因为它对缓存更友好.分配一个 N 元素数组来存储值.并分配一个 sqrt(N) 元素数组来存储索引更正(用零初始化).我将在 100 元素容器的示例中展示它是如何工作的.要删除索引为 56 的元素，请将元素 57..60 移动到位置 56..59，然后在索引更正数组中将 1 添加到元素 6..9.要查找第 84 个元素，请在索引校正数组中查找第 8 个元素(其值为 1)，然后将其值添加到索引 (84+1=85)，然后从主数组中取出第 85 个元素.删除主数组中大约一半的元素后，需要压缩整个容器以实现连续存储.这仅获得 O(1) 累积复杂度.对于实时应用程序，此操作可以分几个较小的步骤执行.

It is possible to create a different container, very similar to tiered vector, having exactly the same complexities, but working a little bit faster because it is more cache-friendly. Allocate a N-element array to store the values. And allocate a sqrt(N)-element array to store index corrections (initialized with zeros). I'll show how it works on the example of 100-element container. To delete element with index 56, move elements 57..60 to positions 56..59, then in the array of index corrections add 1 to elements 6..9. To find 84-th element, look up eighth element in the array of index corrections (its value is 1), then add its value to the index (84+1=85), then take 85-th element from the main array. After about half of elements in main array are deleted, it is necessary to compact the whole container to attain contiguous storage. This gets only O(1) cumulative complexity. For real-time applications this operation may be performed in several smaller steps.

这种方法可以扩展到深度为 M 的 Trie，花费 O(M) 时间对于索引，删除时间为 O(M*N^1/M)，插入时间为 O(1).只需分配一个 N 元素数组来存储值，N^(M-1)/M, N^(M-2)/M, ..., N^1/M-元素数组来存储索引更正.要删除元素 2345，移动主数组中的 4 个元素，在最大的更正"数组中增加 5 个元素，在下一个中增加 6 个元素，在最后一个中增加 7 个元素.要从此容器中获取元素 5678，请将元素 5、56、567 中的所有更正添加到 5678，并使用结果来索引主数组.为M"选择不同的值，可以平衡索引和删除操作之间的复杂性.例如，对于 N=65000，您可以选择 M=4；所以索引只需要 4 次内存访问和删除更新 4*16=64 个内存位置.

This approach may be extended to a Trie of depth M, taking O(M) time for indexing, O(M*N^1/M) time for deletion and O(1) time for insertion. Just allocate a N-element array to store the values, N^(M-1)/M, N^(M-2)/M, ..., N^1/M-element arrays to store index corrections. To delete element 2345, move 4 elements in main array, increase 5 elements in the largest "corrections" array, increase 6 elements in the next one and 7 elements in the last one. To get element 5678 from this container, add to 5678 all corrections in elements 5, 56, 567 and use the result to index the main array. Choosing different values for 'M', you can balance the complexity between indexing and deletion operations. For example, for N=65000 you can choose M=4; so indexing requires only 4 memory accesses and deletion updates 4*16=64 memory locations.

这篇关于寻找具有 O(1) 索引和 O(log(n)) 插入和删除的数据容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！