寻找与O（1）分度和O（日志（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）的删除项目
• 找到/编辑澳第k-最小元素（1），对于任意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（开方N）删除。既然你想到只有约10000这个容器和开方（10000）/日志（10000）= 7元，你几乎需要在这里的表现。分层向量实现为环缓冲器阵列，所以删除一个元素需要移动的所有元素，在环形缓冲器它后面，并移动一个元件下述每一环缓冲器的所述一个，preceding它;索引此容器是指索引的环形缓冲区数组中，然后索引环形缓冲区内。

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.

有可能创建一个不同的容器，​​非常类似于分层载体，具有完全相同的复杂性，但工作得快一点，因为它是更多的缓存友好。分配A N个元素的数组来存储值。而分配的sqrt（N）k-元阵列来存储指数修正（零初始化）。我将展示它是如何工作的100元容器的例子。要删除元素的索引56，移动元素57..60于位置56..59，然后在指数修正的阵列中添加1至元素6..9。要找到84个元素，查找第八元素索引改正的数组（其值为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.

该方法可以扩展到特里深度男，取O（M）时间索引，0（M * N ^{1 / M} ）时间删除和O（1）时间插入。仅分配A N个元素的数组来存储值，N ^{（M-1）/ M} ，N ^{（M-2）/ M} ，...，N < SUP> 1 / M k-元数组存储索引更正。要删除单元2345，将在主阵列4个元素，增加最大的更正排列5元素，增加下一个6个元素，并在最后一节7元。为了让5678元这个容器中，加入5678的所有修正中的元素5，56，567，并使用结果指标的主阵列。选择为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（日志（n））的插入和删除数据容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！