Ruby- 在 O(log n) 运行时从排序的（唯一）数组中删除一个值
Ruby- delete a value from sorted (unique) array at O(log n) runtime
我有一个排序数组（唯一值，不重复）。
我知道我可以使用 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)
现在我只需要获取值的索引。
二进制搜索可以做到这一点，因为数组已经排序。
但是唯一利用排序属性（据我所知）的方法是二进制搜索，其中 returns 值，与删除或返回索引无关。
总结一下：
1) 如何从 O(log n) 的已排序非重复数组中删除一个值？
或者
2) 假设 array#delete-at 在 O(1) 时工作（是吗？），我怎样才能在 O(log n) 时获得值的索引？ （我的意思是数组已经排序了，我必须自己实现吗？）
谢谢。
标准数组实现对排序或重复没有限制。因此，默认实现必须以性能与灵活性进行权衡。
Array#delete 删除 O(n) 中的一个元素。 Here's the C implementation。注意循环
for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
...
}
成本是合理的，因为 Ruby 必须扫描所有匹配给定值的项目（注意 delete 删除 all 匹配值的条目, 而不仅仅是第一个), 然后移动下一个项目以压缩数组。
delete_at 具有相同的成本。事实上，它按给定索引删除元素，但随后它使用 memmove 将数组中的剩余条目少移动一个索引。
使用二分查找不会改变成本。搜索将花费您 O(log n)，但您需要删除给定键处的元素。在最坏的情况下，当元素位于 [0] 位置时，将内存中所有其他项目移动 1 个位置的成本将为 O(n).
在所有情况下，成本都是 O(n)。这并不意外。 Ruby 中的默认数组实现使用数组。这是因为，如前所述，没有可用于优化操作的特定约束。易于迭代和操作集合是优先事项。
数组、排序数组、列表和排序列表：这些数据结构都很灵活，但在某些特定操作中你付出了代价。
回到你的问题，如果你关心性能并且你的数组是有序且唯一的，你绝对可以利用它。如果您的主要目标是从数组中查找和删除项目，则有更好的数据结构。例如，您可以创建一个自定义 class，使用 d-heap where the delete() costs O(log[d,n]), same applies if you use a binomial heap.
在内部存储您的数组
我有一个排序数组（唯一值，不重复）。
我知道我可以使用 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)
现在我只需要获取值的索引。
二进制搜索可以做到这一点，因为数组已经排序。
但是唯一利用排序属性（据我所知）的方法是二进制搜索，其中 returns 值，与删除或返回索引无关。
总结一下：
1) 如何从 O(log n) 的已排序非重复数组中删除一个值？
或者
2) 假设 array#delete-at 在 O(1) 时工作（是吗？），我怎样才能在 O(log n) 时获得值的索引？ （我的意思是数组已经排序了，我必须自己实现吗？）
谢谢。
标准数组实现对排序或重复没有限制。因此，默认实现必须以性能与灵活性进行权衡。
Array#delete 删除 O(n) 中的一个元素。 Here's the C implementation。注意循环
for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
...
}
成本是合理的，因为 Ruby 必须扫描所有匹配给定值的项目（注意 delete 删除 all 匹配值的条目, 而不仅仅是第一个), 然后移动下一个项目以压缩数组。
delete_at 具有相同的成本。事实上，它按给定索引删除元素，但随后它使用 memmove 将数组中的剩余条目少移动一个索引。
使用二分查找不会改变成本。搜索将花费您 O(log n)，但您需要删除给定键处的元素。在最坏的情况下，当元素位于 [0] 位置时，将内存中所有其他项目移动 1 个位置的成本将为 O(n).
在所有情况下，成本都是 O(n)。这并不意外。 Ruby 中的默认数组实现使用数组。这是因为，如前所述，没有可用于优化操作的特定约束。易于迭代和操作集合是优先事项。
数组、排序数组、列表和排序列表：这些数据结构都很灵活，但在某些特定操作中你付出了代价。
回到你的问题，如果你关心性能并且你的数组是有序且唯一的，你绝对可以利用它。如果您的主要目标是从数组中查找和删除项目，则有更好的数据结构。例如，您可以创建一个自定义 class，使用 d-heap where the delete() costs O(log[d,n]), same applies if you use a binomial heap.