110

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).

Improve this question

8 Answers 8

Reset to default
199

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

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

This is exactly what the OP said they DIDN'T want, due to the large size of their array. Array#index is O(n) and doing that multiple times will kill on performance. Hash lookup is O(1).
@tim, well i can't remember at the time of my answer that THIS was the same question, maybe the OP revised the question later on, which would invalidate this answer.
Would it not say that it had been edited at a specific time then?
Hehe, yeah thats true. Well me and another 30 people were reading over it then. I guess :/
122

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
Improve this answer

5 Comments

fastest if the array is very long
Depending on your use case this could be problematic if there are duplicate values. The method described above will return the equivalent or #rindex(last occurrence of value) To get #index equivalent results, meaning the hash returning the first index of the value you'd need to do something along the lines of reversing the array before creating the hash then subtracting the returned index value from the total length of the initial array - 1. # (array.length - 1 ) - hash['b']
Doesn't the conversion into a hash take O(n) time? I suppose if it's going to be used more than once, then hash conversion will be more performant. but for single usage, is it no different then iterating through the array?
Yes, and probably worse for single use if it really matters as hash calculation won't short-circuit as quickly as a comparison.
If you have duplicate elements, @hololeap's answer is more complete.
12

Other answers don't take into account the possibility of an entry listed multiple times in an array. This will return a hash where each key is a unique object in the array and each value is an array of indices that corresponds to where the object lives:

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

This allows for a quick search for duplicate entries:

indices.select { |k, v| v.size > 1 } => { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5] }
Improve this answer

1 Comment

This is a more complete answer than @sawa's.
6

Is there a good reason not to use a hash? Lookups are O(1) vs. O(n) for the array.

Improve this answer

1 Comment

The point is -- I'm calling #keys on hash, which returns an array I am using. Still, I might think over my architecture as well...
3

If your array has a natural order use binary search.

Use binary search.

Binary search has O(log n) access time.

Here are the steps on how to use binary search,

  • What is the ordering of you array? For example, is it sorted by name?
  • Use bsearch to find elements or indices

Code example

# 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
Improve this answer

Comments

3

If it's a sorted array you could use a Binary search algorithm (O(log n)). For example, extending the Array-class with this functionality:

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
Improve this answer

2 Comments

It actually isn't that hard to read. First part, return if lower bound is bigger than upper bound (the recursion has filed). second part checks if we need the left side or right side by comparing the midpoint m with the value at that point to e. if we don't have the answer we want, we recurse.
I think it do better to the ego of people downvoting rather than editing.
2

Taking a combination of @sawa's answer and the comment listed there you could implement a "quick" index and rindex on the array class.

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
Improve this answer

Comments

0

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).

You can use binary search (if your array is ordered and the values you store in the array are comparable in some way). For that to work you need to be able to tell the binary search whether it should be looking "to the left" or "to the right" of the current element. But I believe there is nothing wrong with storing the index at insertion time and then using it if you are getting the element from the same array.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.