数组元素的索引比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 
  • 了解Rails真实性令牌
  • 在FUN中访问lapply索引名称
  • 从Ruby学习Python; 异同
  • 如何避免Java游戏中的垃圾收集延迟? (最佳实践)
  • Rails:validation3列的唯一组合
  • python:pythonbrew和virtualenv有什么区别?
  • 列出相关模型的名称
  • 用Paperclip获取服务器文件path
  • 如何在Rails环境中运行一个Ruby文件?
  • FactoryGirl:多次创build相同的对象
  • Ruby类实例variables与类variables