gmile gmile - 3 months ago 7
Ruby Question

Get index of array element faster than O(n)

Given I have a HUGE array, and a value from it. I want to get index of the value in array. Is there any other way, rather then call

Array#index
to get it? The problem comes from the need of keeping really huge array and calling
Array#index
enormous amount of times.

After a couple of tries I found that caching indexes inside elements by storing structs with
(value, index)
fields instead of the value itself gives a huge step in performance (20x times win).

Still I wonder if there's a more convenient way of finding index of en element without caching (or there's a good caching technique that will boost up the performance).

Answer

Convert the array into a hash. Then look for the key.

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