获取数组元素的索引比O（n）更快

鉴于我有一个巨大的数组，以及它的值。我想获得数组中的值的索引。有没有其他的方法，而不是打电话Array#index得到它？这个问题来自保持真正巨大的阵列的需要并且呼叫Array#index巨大的时间。获取数组元素的索引比O（n）更快

多试几次后，我发现，缓存中的元素指标通过存储结构与(value, index)领域，而不是本身的价值给出了性能的一大步（20X次夺冠）。

我还想知道是否有一种更方便的方式来查找没有缓存的en元素索引（或者有一个好的缓存技术可以提高性能）。

来源

2011-06-05 gmile

112

将数组转换为散列。然后寻找钥匙。

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

来源

2011-06-05 10:41:14 sawa

如果阵列很长，则速度最快 – Kevin 2012-11-19 19:13:50

+16

根据您的使用情况，如果存在重复值，则可能会出现问题。上述方法将返回等价或#rindex（最后一次出现的值）要获得#index等效结果，意味着返回值的第一个索引的散列需要沿着反转的方向在创建散列之前的数组，然后从初始数组的总长度中减去返回的索引值 - 1. ＃（array.length - 1） - hash ['b'] – ashoda 2013-05-30 02:49:37

不转换为散列准时？我猜想如果它将被多次使用，那么散列转换将更加高效。但对于一次性使用，是否没有不同，然后遍历数组？ – ahnbizcad 2016-09-16 19:45:53

有没有好的理由不使用哈希？查找数组为O(1)与O(n)。

来源

2011-06-05 10:41:07

重点是 - 我打电话'＃keys'哈希，它返回我使用数组。不过，我可能会考虑我的架构以及... – gmile 2011-06-05 12:29:28

如果它是一个分类阵列可以使用二进制搜索算法（O(log n)）。例如，使用此功能扩展Array类：

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

来源

2011-06-05 10:52:28 isakkarlsson

你认为这很容易阅读？答案背后的逻辑是以简单的方式传递信息，并且可以清晰地表达你的观点。 – YoniGeek 2014-06-14 12:21:08

它实际上并不难读。第一部分，如果下界大于上界（递归已存档），则返回。第二部分通过比较中点m和该点到e的值来检查我们是否需要左侧或右侧。如果我们没有我们想要的答案，我们就会缓解。 – ioquatix 2014-07-20 08:17:43

我认为这对人们自我低估而不是编辑更好。 – 2017-06-06 21:07:13

199

为什么不使用索引或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')

指数：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

来源

2012-07-24 08:05:14 Roger

+12

由于数组的大小，这正是OP表示他们不想要的东西。 Array＃索引是O（n），并且多次执行会影响性能。哈希查找是O（1）。 – Tim 2013-05-01 03:46:47

@tim，以及我在回答时记不清这是**相同的问题，也许OP稍后修改了这个问题，这将使这个答案失效。 – Roger 2013-05-01 07:41:32

那不是说它已经在特定的时间编辑过了吗？ – Tim 2013-05-01 21:08:41

以@泽的回答的组合和那里列出的评论，你可以实现阵列上的 “快速” 指数和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

来源

2015-02-09 03:13:07 ianstarz

其他答案没有考虑到一个条目在列表中多次列出的可能性。这将返回一个散列结果，其中每个键是数组中唯一的对象和每个值是索引数组对应于对象的居住地：

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] }

来源

2015-07-12 03:30:13 hololeap

如果您的数组有自然顺序使用二进制搜索。

使用二进制搜索。

二进制搜索有O(log n)访问时间。

下面是关于如何使用二进制搜索的步骤，

什么是你数组的排序？例如，它是按名称排序的吗？
使用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

来源

2016-12-26 00:23:14 akuhn

获取数组元素的索引比O（n）更快

回答

相关问题