Как сравнить 2 разных набора данных в рубине

Question

У меня есть 2 массива, первый состоит из ~ 2000 элементов.

Второй массив содержит ~ 500 массивов с 2 элементами в каждом.

Мне нужен способ проверить, существуют ли элементы во втором массиве в первом массиве, и если это так, создайте новый массив соответствующих элементов.

ex) 

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

array2 = [[1,2],[3,4],[5,6],[7,14],[9,11]] 

new_array = [1,2,3,4,5,6,7,9,11] 

Я хочу сделать это без необходимости прокручивать все элементы в любых массивах.

Что было бы самым эффективным способом сделать это? Улучшится ли производительность, если я реализовал их как хэши, а не массивы?

Answer 1

Я бы просто flatten второй массив и не использовать Array#& (пересечение):

array1 = [1,2,3,4,5,6,7,8,9,10,11] 
array2 = [[1,2],[3,4],[5,6]] 

new_array = array1 & array2.flatten 
#=> [1,2,3,4,5,6] 

Эта версия использует Ruby, идиомы и очень читаемым. Производительность зависит от реализации метода пересечения в Ruby. Я не знаю реализации, но предполагаю, что он использует хэш внутри. Таким образом, мы закончили бы создание нового массива в flatten (O(m)), а также построение структуры хеша (в среднем O(n)), плюс сравнение (O(m)).

Если мы можем предположить, что как массивы, так и подмассивы (!) всегда сортируются, чем вы можете захотеть вручную с помощью этих массивов. Это будет делать максимум O(m + n) шагов и может быть немного быстрее, чем версия пересечения, потому что нет необходимости сначала сгладить массив и не нужно вычислять хэши для каждого значения.

array1 = [1,2,3,4,5,6,7,8,9,10,11] 
array2 = [[1,2],[3,4],[5,6]] 

index1 = 0 
index2 = [0, 0] 

intersection = [] 

loop do 
    break intersection if index1 >= array1.size || index2[0] >= array2.size 

    if array1[index1] == array2[index2[0]][index2[1]] 
    intersection << array1[index1] 
    index1 += 1 
    index2 = index2[1] == 0 ? [index2[0], 1] : [index2[0] + 1, 0] 

    elsif array1[index1] < array2[index2[0]][index2[1]] 
    index1 += 1 

    else 
    index2 = index2[1] == 0 ? [index2[0], 1] : [index2[0] + 1, 0] 
    end 
end 

Возможно, вы захотите сравнить обе версии. По соображениям удобочитаемости я предпочел бы первую версию.