Get index of array element faster than O n

Question

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

User · Answer

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

User · Answer

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

User · Answer

Convert the array into a hash  Then look for the key   array     a    b    c   hash   Hash array map with index to a         gt    a   gt 0   b   gt 1   c   gt 2  hash  b       gt  1

User · Answer

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

User · Answer

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

User · Answer

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  gt  upper index      midpoint index    lower index   upper index    2     return midpoint index if self midpoint index     value      if value  lt  self midpoint index        b search value  lower index  upper index - 1      else       b search value  lower index   1  upper index      end   end end

User · Answer

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    gt   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   gt    1   gt   0  3   2   gt   1  4   3   gt   2  5   4   gt   6      This allows for a quick search for duplicate entries   indices select    k  v  v size  gt  1     gt    1   gt   0  3   2   gt   1  4   3   gt   2  5

User · Answer

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

[ruby] Get index of array element faster than O(n)

Examples related to ruby

Examples related to arrays

Examples related to performance

Examples related to indexing