数组元素的索引比O（n）快
鉴于我有一个巨大的数组，并从它的价值。 我想获得数组中的值的索引。 有没有其他的方法，而不是调用Array#index来获取它？ 这个问题来自保持真正巨大的数组并且需要调用Array#index巨大的时间。
经过几次尝试之后，我发现通过使用(value, index)字段而不是值本身存储结构来caching索引内容会给性能带来巨大的一步（20倍的胜利）。
我仍然想知道是否有一个更方便的方式来find没有caching的元素索引（或者有一个很好的caching技术可以提高性能）。
将数组转换为哈希。 然后寻找钥匙。
array = ['a', 'b', 'c'] hash = Hash[array.map.with_index.to_a] # => {"a"=>0, "b"=>1, "c"=>2} hash['b'] # => 1
为什么不使用索引或rindex？
array = %w( abcde) # 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
其他答案没有考虑到一个列表中多次列出条目的可能性。 这将返回一个散列，其中每个键是数组中的唯一对象，每个值都是与对象所在位置对应的索引数组：
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] }
这允许快速search重复条目：
indices.select { |k, v| v.size > 1 } => { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5] }
有没有好的理由不使用哈希？ 对于数组，查找是O(1)对O(n) 。
结合@ sawa的答案和在那里列出的注释，你可以在数组类上实现一个“快速”索引和rindex。
class Array def quick_index el hash = Hash[self.map.with_index.to_a] hash[el] end def quick_rindex el hash = Hash[self.reverse.map.with_index.to_a] array.length - 1 - hash[el] end end
如果它是一个sorting数组，你可以使用二进制searchalgorithm（ O(log n) ）。 例如，用这个function扩展Array-class：
class Array def b_search(e, l = 0, u = length - 1) return if lower_index > upper_index midpoint_index = (lower_index + upper_index) / 2 return midpoint_index if self[midpoint_index] == value if value < self[midpoint_index] b_search(value, lower_index, upper_index - 1) else b_search(value, lower_index + 1, upper_index) end end end
如果你的数组有自然顺序使用二进制search。
使用二进制search。
二进制search有O(log n)访问时间。
以下是如何使用二进制search的步骤，
- 你arrays的sorting是什么？ 例如，它是按名称sorting的吗？
- 使用
bsearch查找元素或索引
代码示例
# assume array is sorted by name! array.bsearch { |each| "Jamie" <=> each.name } # returns element (0..array.size).bsearch { |n| "Jamie" <=> array[n].name } # returns index
