获取比O(n)更快的数组元素索引
获取比O(n)更快的数组元素索引
提问于 2011-06-05 18:22:38
假设我有一个巨大的数组，并从中得到一个值。我想获取数组中的值的索引。有没有其他方法，而不是调用Array#index来获取它？这个问题来自于需要保存非常大的数组和大量调用Array#index的次数。
经过几次尝试，我发现在元素中缓存索引的方法是将结构与(value, index)字段一起存储，而不是值本身，这在性能上有很大的提升(20倍于win)。
尽管如此，我想知道是否有一种更方便的方法来查找en元素的索引而无需缓存(或者有一种很好的缓存技术可以提高性能)。
回答 4
Stack Overflow用户
回答已采纳
发布于 2011-06-05 18:41:14
将数组转换为哈希。然后去找钥匙。
array = ['a', 'b', 'c']
hash = Hash[array.map.with_index.to_a] # => {"a"=>0, "b"=>1, "c"=>2}
hash['b'] # => 1Stack Overflow用户
发布于 2015-07-12 11:30:13
其他答案没有考虑到一个条目在一个数组中多次列出的可能性。这将返回一个散列，其中每个键都是数组中唯一的对象，每个值都是一个索引数组，对应于对象所在的位置：
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] }Stack Overflow用户
发布于 2011-06-05 18:41:08
有没有一个不使用散列的好理由？针对阵列的查找是O(1)与O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/6242311
复制相关文章
相似问题