如何比较ruby中的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中交集方法的实现.我不知道实现,但会猜测它在内部使用Hash.所以我们最终会在flatten(O(m))中构建一个新数组,再加上构建Hash结构(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

您可能希望对两个版本进行基准测试 出于可读性原因,我更喜欢第一个版本.