获取数组元素的索引比O(n)更快

Question

鉴于我有一个巨大的数组,以及它的值.我想得到数组中的值的索引.还有其他方式,而不是打电话Array#index来获得它吗？问题来自需要保持真正庞大的阵列和Array#index大量的时间.

经过几次尝试后,我发现通过存储带有字段而不是值本身的结构来缓存元素内部的索引(value, index)会给性能带来巨大的进步(20倍的胜利).

我仍然想知道是否有更方便的方法来查找en元素的索引而不进行缓存(或者有一个很好的缓存技术可以提高性能).

Answer 1

为什么不使用索引或rindex？

array = %w( a b c d e)
# get FIRST index of element searched
puts array.index('a')
# get LAST index of element searched
puts array.rindex('a')

index:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-index

rindex:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-rindex

Answer 2

将数组转换为哈希值.然后寻找钥匙.

array = ['a', 'b', 'c']
hash = Hash[array.map.with_index.to_a]    # => {"a"=>0, "b"=>1, "c"=>2}
hash['b'] # => 1

Answer 3

其他答案没有考虑在数组中多次列出条目的可能性.这将返回一个散列,其中每个键是数组中的唯一对象,每个值都是一个索引数组,对应于对象所在的位置:

a = [1, 2, 3, 1, 2, 3, 4]
=> [1, 2, 3, 1, 2, 3, 4]

indices = a.each_with_index.inject(Hash.new { Array.new }) do |hash, (obj, i)| 
    hash[obj] += [i]
    hash
end
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5], 4 => [6] }

这样可以快速搜索重复的条目:

indices.select { |k, v| v.size > 1 }
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5] }

Answer 4

是否有充分的理由不使用哈希？查找是阵列的O(1)vs.O(n)