Get index of array element faster than O(n)

ruby arrays performance indexing
gmile picture gmile · Jun 5, 2011 · Viewed 109.3k times · Source

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

Roger picture Roger · Jul 24, 2012

Why not use index or 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')

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

Related questions

Ruby Array find_first object?

Am I missing something in the Array documentation? I have an array which contains up to one object satisfying a certain criterion. I'd like to efficiently find that object. The best idea I have from the docs is this: candidates = …

Read More
How to check if a value exists in an array in Ruby

I have a value 'Dog' and an array ['Cat', 'Dog', 'Bird']. How do I check if it exists in the array without looping through it? Is there a simple way of checking if the value exists, nothing more?

Read More
What is the "right" way to iterate through an array in Ruby?

PHP, for all its warts, is pretty good on this count. There's no difference between an array and a hash (maybe I'm naive, but this seems obviously right to me), and to iterate through either you just do foreach (array/…

Read More