Как получить индексы подмассива в большом массиве

Question

У меня есть два массива следующим образом:

a = [1,2,3,4,5,6,7,8,9,10]
b = [3,5,8,10,11]

Я хочу найти индекс подмассива в основном массиве, если число присутствует.Ожидаемый результат:

res = [2,4,7,9] 

Я сделал следующее:

[3,5,8,10,11].each do |_element|
  res_array = []
  if [1,2,3,4,5,6,7,8,9,10].find_index(_element).present?
   res_array << (header_array.find_index(_element)
  end
  res_array
 end

Но я думаю, что есть лучший подход для этого.

Answer 1

Все ответы до сих пор пересекают все a один раз (@ Stefan's) или пересекают все или часть a b.size раз.Мой ответ проходит часть или все из a один раз.Это относительно эффективно, когда a велико, b мало по отношению к a и все элементы в b появляются в a.

Мое решение особенно эффективно, когда aупорядочено таким образом, что элементы b обычно появляются в начале a.Например, a может быть списком фамилий, отсортированных по убыванию частоты встречаемости среди населения в целом (например, ['smith', 'jones',...]), а b - это список имен, которые нужно искать в a.

a и b могут содержать дубликаты ¹ , и не все элементы b гарантированно находятся в a.Я предполагаю, что b не является пустым.

Код

require 'set'

def lookup_index(a, b)
  b_set = b.to_set
  b_hash = {}
  a.each_with_index do |n,i|
    next unless b_set.include?(n)
    b_hash[n] = i
    b_set.delete(n)
    break if b_set.empty?
  end
  b_hash.values_at(*b)
end

Я преобразовал b в набор, чтобы сделать поиск сопоставимым по скорости с поиском по хешу (которыйне должно быть ничего удивительного, учитывая, что наборы реализованы с базовым хешем).Конечно, хеш-поиск выполняется очень быстро.

Примеры

a = [1,2,3,4,5,6,7,8,9,10,8]
b = [3,5,8,10,11,5]

Обратите внимание, что в этом примере a и b содержат дубликаты, а 11в b отсутствует в a.

lookup_index(a, b)
  #=> [2, 4, 7, 9, nil, 4]

Обратите внимание, что возвращаемый массив содержит индекс 4 дважды, один раз для каждого 5 в b.Кроме того, массив содержит nil в индексе 4, чтобы показать, что это b[4] #=> 11, который не появляется в a.Без заполнителя nil не было бы возможности сопоставить элементы b с индексами в a.Однако, если заполнитель nil нежелателен, можно заменить b_hash.values_at(*b) на b_hash.values_at(*b).compact или, если дубликаты нежелательны, на b_hash.values_at(*b).compact.uniq.

В качестве второго примера предположим, что нам дано следующее.

a = [*1..10_000]
b = 10.times.map { rand(100) }.shuffle
  #=> [30, 62, 36, 24, 41, 27, 83, 61, 15, 55]
lookup_index(a, b)
  #=> [29, 61, 35, 23, 40, 26, 82, 60, 14, 54]

Здесь решение было найдено после перечисления первых 83 элементов a.

^{1 Мое решение не будет более эффективным, если дубликаты не будут разрешены в a и / или b.}

Answer 2

Если производительность имеет значение (то есть, если ваши массивы огромные ), вы можете создать хэш всех пар числовых индексов в a, используя each_with_index и to_h:

a.each_with_index.to_h
#=> {1=>0, 2=>1, 3=>2, 4=>3, 5=>4, 6=>5, 7=>6, 8=>7, 9=>8, 10=>9}

Хеш позволяет получать значения (то есть индексы) для чисел в b гораздо быстрее (в отличие от обхода массива каждый раз), например, через values_at:

a.each_with_index.to_h.values_at(*b)
#=> [2, 4, 7, 9, nil]

Используйте compact для исключения nil значений:

a.each_with_index.to_h.values_at(*b).compact
#=> [2, 4, 7, 9]

или альтернативно slice и values:

a.each_with_index.to_h.slice(*b).values
#=> [2, 4, 7, 9]

Answer 3

Вот еще одно более простое решение,

indxs = a.each_with_index.to_h
(a&b).map{|e| indxs[e]}

Answer 4

b.map { |e| a.index(e) }.compact
#⇒ [2, 4, 7, 9]

или, более кратко:

b.map(&a.method(:index)).compact