10

我有一个排序的唯一数组，并希望有效地将一个不在数组中的元素插入其中，如下所示：

a = [1,2,4,5,6]
new_elm = 3
insert_at = a.bsearch_index {|x| x > new_elm } # => 2
a.insert(insert_at, new_elm) # now a = [1,2,3,4,5,6]

该方法bsearch_index不存在： only bsearch，它返回匹配元素而不是匹配元素的索引。有没有内置的方法来实现这一点？

4

6 回答 6

10

您可以使用返回的Enumerator对象返回each_with_index嵌套的[value, index]对数组，然后对该数组进行二进制搜索：

a = [1,2,4,5,6]
new_elm = 3

index = [*a.each_with_index].bsearch{|x, _| x > new_elm}.last
=> 2

a.insert(index, new_elm)

编辑：

我已经运行了一些简单的基准测试来回答您的问题，其中包含一个长度数组1e6 - 1：

require 'benchmark'

def binary_insert(a,e)
  index = [*a.each_with_index].bsearch{|x, _| x > e}.last
  a.insert(index, e)
end

a = *1..1e6
b = a.delete_at(1e5)
=> 100001

Benchmark.measure{binary_insert(a,b)}
=> #<Benchmark::Tms:0x007fd3883133d8 @label="", @real=0.37332, @cstime=0.0, @cutime=0.0, @stime=0.029999999999999805, @utime=0.240000000000002, @total=0.2700000000000018>

考虑到这一点，您可能会考虑尝试使用堆或 trie 而不是数组来存储您的值。特别是堆具有恒定的插入和删除时间复杂性，使其成为大型存储应用程序的理想选择。在此处查看这篇文章：Ruby 算法：排序、trie 和堆

于 2014-05-05T21:44:12.260 回答
9

如何使用SortedSet？：

require 'set'

a = SortedSet.new [1,2,4,5,6]
new_elm = 3
a << new_elm # now a = #<SortedSet: {1, 2, 3, 4, 5, 6}>

SortedSet 是使用rbtree. 我做了以下基准：

def test_sorted(max_idx)
  arr_1 = (0..max_idx).to_a
  new_elm = arr_1.delete(arr_1.sample)
  arr_2 = arr_1.dup
  set_1 = SortedSet.new(arr_1)
  Benchmark.bm do |x|
    x.report { arr_1.insert(arr_1.index { |x| x > new_elm }) }
    x.report { arr_2.insert([*arr_2.each_with_index].bsearch{|x, _| x > new_elm}.last) }
    x.report { set_1 << new_elm }
  end
end

结果如下：

test_sorted 10_000
# =>       user     system      total        real
# =>   0.000000   0.000000   0.000000 (  0.000900)
# =>   0.010000   0.000000   0.010000 (  0.001868)
# =>   0.000000   0.000000   0.000000 (  0.000007)

test_sorted 100_000
# =>       user     system      total        real
# =>   0.000000   0.000000   0.000000 (  0.001150)
# =>   0.000000   0.010000   0.010000 (  0.048040)
# =>   0.000000   0.000000   0.000000 (  0.000013)

test_sorted 1_000_000
# =>       user     system      total        real
# =>   0.040000   0.000000   0.040000 (  0.062719)
# =>   0.280000   0.000000   0.280000 (  0.356032)
# =>   0.000000   0.000000   0.000000 (  0.000012)
于 2014-05-05T21:00:52.400 回答
7

“该方法bsearch_index不存在”：Ruby 2.3 引入了bsearch_index。（在它存在之前获得方法名称的荣誉）。

于 2015-11-16T22:36:33.633 回答
3

尝试这个

(0...a.size).bsearch { |n| a[n] > new_element }

这使用bsearchdefined onRange来搜索数组并因此返回索引。

性能将比each_with_index具体化O(n)临时数组元组更好，从而阻塞垃圾收集。

于 2017-01-20T08:47:26.337 回答
3

Ruby 2.3.1 引入了bsearch_index因此问题现在可以这样解决：

a = [1,2,4,5,6]
new_elm = 3

index = a.bsearch_index{|x, _| x > new_elm}
=> 2

a.insert(index, new_elm)
于 2017-04-21T03:52:23.267 回答
-2

该index方法接受一个块并将返回该块为真的第一个索引

a = [1,2,4,5,6] 
new_elem = 3
insert_at = a.index{|b| b > new_elem}
#=> 2
a.insert(insert_at, new_elm) 
#=>[1,2,3,4,5,6]
于 2014-05-05T21:04:37.543 回答