Получить индекс элемента массива быстрее, чем O(n)

учитывая, что у меня есть огромный массив, и значение из него. Я хочу получить индекс значения в массиве. Есть ли другой способ, а не звонить Array#index чтобы получить его? Проблема исходит из необходимости сохранения действительно огромного массива и вызова Array#index огромное количество раз.

после нескольких попыток я обнаружил, что кэширование индексирует внутри элементов, сохраняя структуры с (value, index) поля вместо самого значения дают огромный шаг в производительности (в 20 раз выиграть.)

тем не менее мне интересно, есть ли более удобный способ найти индекс элемента en без кэширования (или есть хороший метод кэширования, который повысит производительность).

7 99
arrays ruby-on-rails performance indexing

7 ответов:

преобразовать массив в хэш. Тогда ищи ключ.

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

почему бы не использовать index или 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')

индекс: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

199

другие ответы не учитывать возможность записи несколько раз в массив. Это вернет хэш, где каждый ключ является уникальным объектом в массиве, и каждое значение является массивом индексов, который соответствует тому, где живет объект:

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

есть ли веская причина не использовать хэш? Поиск O(1) и O(n) для массива.

6

принимая комбинацию ответа @sawa и комментария, указанного там, вы можете реализовать "быстрый" индекс и rindex в классе массива.

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
2

Если это отсортированный массив вы можете использовать двоичный алгоритм поиска (O(log n)). Например, расширение класса Array с помощью этой функции:

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
2

Если Ваш массив имеет естественный порядок использования бинарного поиска.

использовать двоичный поиск.

бинарный поиск имеет O(log n) время доступа.

вот шаги, о том, как использовать бинарный поиск,

  • каков порядок вашего массива? Например, отсортированных по имени?
  • использовать bsearch найти элементы или показатели

пример кода

# 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
1