我有一个排序数组(唯一值,不重复).
我知道我可以使用Array#binarysearch但它用于查找值而不是删除它们.我也可以删除O(log n)的值吗？怎么样？
让我们说我有这个数组:
arr = [-3, 4, 7, 12, 15, 20] #very long array
我想删除值7.到目前为止,我有这个:
arr.delete(7) #I'm quite sure it's O(n)
假设Array#delete-at在O(1)处工作.我能做到arr.delete_at(value_index)
现在我只需要获取值的索引.二进制搜索可以做到这一点,因为数组已经排序.但是利用排序属性(我所知道的)的唯一方法是返回值的二进制搜索,而不是删除或返回索引.
把它们加起来:
1)如何在O(log n)处从已排序的非重复数组中删除值？
要么
2)假设数组#lele-at在O(1)处工作(是吗？),如何在O(log n)处获取值的索引？(我的意思是数组已经排序了,我必须自己实现吗？)
谢谢.
标准Array实现对排序或重复没有约束.因此,默认实现必须灵活地交换性能.
Array#delete删除中的元素O(n).这是C实现.注意循环
for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
...
}
Ruby必须扫描匹配给定值的所有项目(注意delete删除与值匹配的所有条目,而不仅仅是第一个),然后移动下一个项目以压缩数组,从而证明成本是合理的.
delete_at有相同的成本.实际上,它通过给定索引删除元素,但随后它用于memmove将剩余条目在数组上减少一个索引.
使用二进制搜索不会改变成本.搜索将花费您O(log n),但您需要删除给定键的元素.在最坏的情况下,当元素处于适当位置时[0],将内存中的所有其他项目移位1个位置的成本将是O(n).
在所有情况下,成本是O(n).这并不意外.Ruby中的默认数组实现使用数组.这是因为,如前所述,没有可用于优化运营的具体约束.易于迭代和操作集合是首要任务.
数组,排序数组,列表和排序列表:所有这些数据结构都很灵活,但您需要在某些特定操作中支付成本.
回到你的问题,如果你关心性能并且你的阵列是有序的和独特的,你绝对可以利用它.如果您的主要目标是从数组中查找和删除项目,则可以使用更好的数据结构.例如,您可以创建一个存储阵列的内部使用一个自定义类d-heap,其中的delete()成本O(log[d,n]),如果使用同样适用二项堆.