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

Question

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

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

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

Answer 1

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

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

Answer 2

Конвертировать массив в хеш.Тогда ищи ключ.

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 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