Ruby-删除排序（唯一的）阵列在O的值（log n）的运行时间 [英] Ruby- delete a value from sorted (unique) array at O(log n) runtime
问题描述
我有一个排序的数组（唯一值，不重复）。
I have a sorted array (unique values, not duplicated).
我知道我可以使用阵列＃BinarySearch的，但它用来查找值不能删除它们。
我可以删除在O的值（log n）的呢？怎么样？
I know I can use Array#binarysearch but it's used to find values not delete them. Can I delete a value at O(log n) as well? How?
可以说我有此数组：
arr = [-3, 4, 7, 12, 15, 20] #very long array
和我想删除值7。
到目前为止，我有这样的：
And I would like to delete the value 7. So far I have this:
arr.delete(7) #I'm quite sure it's O(n)
我可以做 arr.delete_at（value_index）
现在我只需要得到该值的指数。
二进制搜索可以做到这一点，因为数组已排序。
但是，利用有序属性（据我所知）的唯一方法就是二进制搜索，返回值，一无所知删除或返回索引。
Assuming Array#delete-at works at O(1).
I could do arr.delete_at(value_index)
Now I just need to get the value's index.
binary search can do it, since the array is already sorted.
But the only method utilizing the sorted attribute (that i know of) is binary search which returns values, nothing about deleting or returning indexes.
要总结一下：
1）如何在澳删除排序的不重复的数组值（log n）的？
1) How to delete a value from sorted not duplicated array at O(log n) ?
或者
2）假设的阵列＃删除 - 在的工作在O（1）（它？），我怎么能在澳获得价值指数（log n）的？ （我指的是阵列已经排序，我必须实现它自己？）
2) Assuming array#delete-at works at O(1) (does it?), how can I get the value's index at O(log n)? ( I mean the array is already sorted, must I implement it myself?)
感谢您。
推荐答案
标准阵列实现对排序或复制没有任何约束。因此，默认的实现有交易灵活的表现。
The standard Array implementation has no constraint on sorting or duplicate. Therefore, the default implementation has to trade performance with flexibility.
阵列＃删除删除元素为O（n）。 这里的C实现。注意循环
for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
...
}
费用由事实Ruby有扫描所有的物品合理匹配给定值（注删除删除全部的条目匹配的值，不只是第一个），然后转移下一项压缩阵列
The cost is justified by the fact Ruby has to scan all the items matching given value (note delete deletes all the entries matching a value, not just the first), then shift the next items to compact the array.
delete_at 具有相同的成本。事实上，它由给定的索引中删除该元素，但随后它使用 memmove与 却将其余条目一个索引少阵列上。
delete_at has the same cost. In fact, it deletes the element by given index, but then it uses memmove to shift the remaining entries one index less on the array.
使用二进制搜索将不会改变的成本。搜索将花费你 O（log n）的，但你将需要删除在给定键的元素。在最坏的情况下，当元素在位置 [0] ，成本在内存中的所有其他项目1个职位转移将是 0 （N）。
Using a binary search will not change the cost. The search will cost you O(log n), but you will need to delete the element at given key. In the worst case, when the element is in position [0], the cost to shift all the other items in memory by 1 position will be O(n).
在所有的情况下，成本 O（N）。这并不意外。在Ruby中默认的数组实现使用数组。那是因为，正如前面所说，有没有可能被用于优化运营特定的约束。集合容易迭代和操作是首要问题。
In all cases, the cost is O(n). This is not unexpected. The default array implementation in Ruby uses arrays. And that's because, as said before, there are no specific constraints that could be used to optimize operations. Easy iteration and manipulation of the collection is the priority.
阵列，阵列排列，列表和分类列表：所有的这些数据结构是灵活的，但你在一些特定的操作付出的成本
Array, sorted array, list and sorted list: all these data structures are flexible, but you pay the cost in some specific operations.
回到你的问题，如果你关心的性能和阵列进行排序和独特的，你绝对可以利用它。如果你的主要目标是找到并从您的数组删除项目，有更好的数据结构。例如，您可以创建一个存储自定义类阵列内部使用 D -heap 其中删除（）成本 O（日志[D，N]），如果您使用二项堆同样适用。
Back to your question, if you care about performance and your array is sorted and unique, you can definitely take advantage of it. If your primary goal is finding and deleting items from your array, there are better data structures. For instance, you can create a custom class that stores your array internally using a d-heap where the delete() costs O(log[d,n]), same applies if you use a binomial heap.
这篇关于Ruby-删除排序（唯一的）阵列在O的值（log n）的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
