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

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

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

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

Ответы

Ответ 1

Преобразуйте массив в хэш. Затем найдите ключ.

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

Если это массив отсортированный, вы можете использовать алгоритм двоичного поиска (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

Ответ 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

Ответ 7

Если ваш массив имеет естественный порядок, используйте двоичный поиск.

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

Двоичный поиск имеет 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

Ответ 8

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

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