比较两个数组的最有效方法

由于这个问题有标签，我lenguaje-agnóstico将把这个问题作为一个计算问题和算法分析来回答。

它试图解决的计算问题如下：给定一个包含 n 个元素的数组A和一个包含n 个和m个非负整数的m个元素的数组B ，返回一​​个包含k个元素的数组C ，其中该数组C的每个第 k 个元素属于到数组A和数组B。很明显，如果数组C为空，则意味着两个数组没有共同的元素。

用伪代码解决这个问题的简单方法如下：

REPETIDOS(A[0..n-1],B[0..m-1])
//Compara dos arreglos para identificar elementos comunes
//Entrada: dos arreglos A y B a comparar
//Salida: un arreglo C que contiene los elementos comunes a ambos arreglos
1. crear C, un arreglo vacío
2. para i ← 0 hasta i ← n -1
3.     para j ← 0 hasta j ←  m -1
4.        si A[i] = B[j]
5.            añada el elemento A[i] al arreglo C
6. retorne C

简单的解决方案是将数组 B 的所有元素与数组 A 的每个元素进行比较，然后将数组 C 中重复的元素相加并返回。此解决方案与问题随附的 Python 代码中提出的解决方案基本相同。

对于这个例子，元素很少，只需要很少的时间，但是随着我们添加元素，时间呈指数增长。

让我们澄清前面的说法。从上面的伪代码中我们发现了一个嵌套的双循环。第一个循环（第 2 行）执行 n 次（因为数组A有n 个元素），每次执行该行第 3. 行执行m次（因为数组B有m个元素。这意味着比较的次数这个过程执行的时间是n 乘以 m。然后对算法的分析表明它的复杂度是O(nm)（这种复杂性是一种抽象，在定义的计算模型下，它允许我们确定大输入大小的算法的执行时间）。如果我们假设两个数组具有相同数量的元素n，则算法的复杂度为O(n^2)。也就是说，算法的复杂性不是它通俗地提到的“指数”，而是关于n的二次方，即问题输入的大小。

鉴于上述情况，现在的问题是：有没有比 O(n^2) 更好的算法来比较两个大小为 n 的数组？. 答案是肯定的。

如果将第一个数组的元素添加到名为 Hash 的数据结构中，然后遍历第二个数组的元素以查看它们是否在结构中，如果是，则将其添加到数组 C。

REPETIDOSCONHASH(A[0..n-1],B[0..m-1])
//Compara dos arreglos para identificar elementos comunes
//Entrada: dos arreglos A y B a comparar
//Salida: un arreglo C que contiene los elementos comunes a ambos arreglos
1. crear C, un arreglo vacío y D una estructura hash
2. para i ← 0 hasta i ← n -1
3.     agregue A[i] a D.
4. para j ← 0 hasta j ← m -1
5.     si B[j] se encuentra en D
6.         añada el elemento B[j] al arreglo C
7. retorne C

向哈希结构添加和查询元素的操作具有计算复杂度O(1)，摊销分析表明，在平均情况下，插入和查询需要恒定的时间。对于上述算法，第 2 行执行 n 次（我们需要将数组A的n 个元素添加到哈希D中，对于第 2 行的每次执行，第 3 行执行 1 次（因为插入结构需要恒定时间）第 4 行是执行m次并且对于每次执行，我们都会花费常数时间来验证数组的第 m 个元素是否在哈希结构中，如果是，则很明显该元素是重复的，我们将其添加到数组 C 中。

由上可知，新算法的计算复杂度为O(n)，即与数组元素的大小成线性关系。这是对复杂度为O(n^2)的先前算法的实质性改进，请记住，设置复杂度的目标是确定输入的大小趋于越来越大的值时的执行时间。

那么问题来了，有没有可能克服之前的算法呢？，答案是否定的。显然，为了识别哪些元素在两个数组中重复，我们必须至少遍历一些数组一次，因此至少必须执行O(n)次操作。

其他算法实现允许体面的计算复杂性。一种可能的策略是对两个数组进行排序并进行线性遍历比较每个元素（不像第一个算法那样成对，而是使用两个迭代器保证遍历O(n+m)或O(n If我们假设我们使用O(nlogn)阶的排序算法，该算法的复杂度恰好是O(nlogn) 。另一种可能性是假设A和B都是有序的，因此计算复杂度为 ，使用上面的算法, O(n)。

简而言之：在不做任何额外假设的情况下比较两个数组的最有效方法是使用 Hash，这在大多数情况下保证了计算复杂度O(n)。

没有最有效的通用方法。这将取决于许多因素，但一个非常重要的因素将是使用的语言。对于每种语言，都可能有比另一种更有效的方法。Python 列表与 C 数组或 C++ 向量不同。总有一些通用的想法，例如尽可能避免数组上的完整迭代次数，尽可能使用哈希表等，但这取决于每种语言，甚至取决于数据类型。

具体来说Python并根据您的示例，使用该方法的问题在于，对于每个元素arreglo1，您都需要遍历arreglo2整数。在 Python 中，同时查看两个可迭代对象中存在的元素的一种更有效的方法是使用 intersection()sets( set) 方法，该方法接受两个集合并返回另一个集合，其中包含两个集合中的元素：

#!/usr/bin/python
# -*- coding: utf-8 -*-

arreglo1   = [1,2,3,4,5,6]
arreglo2   = [0,2,4,6,8,10]
repetidos = set(arreglo1) & set(arreglo2)

print "Los Repetidos son"
for z in repetidos:
    print z

版：

我使用两个包含 100,000 个元素的列表添加了一个小比较。我将您的代码与更有效的替代方案进行比较，使用in和列表推导以及使用set.intersection(). 所有三个函数都返回一个列表。

#!/usr/bin/python
# -*- coding: utf-8 -*-
import random
from time import time

def ciclo_for(a, b):
    repetidos = []
    for x in a:
        for y in b:
            if x == y:
                repetidos.append(x)
    return repetidos

def set_intersection(a, b):
    repetidos = list(set(a) & set(b))
    return repetidos

def list_comprehensions(a, b):
    return [n for n in a if n in b]

arreglo1 = [n for n in xrange(0,100000)]
arreglo2 = [n for n in xrange(0,200000,2)]

t0 = time()
ciclo_for(arreglo1, arreglo2)
print 'ciclo for:', time()-t0

t0 = time()
list_comprehensions(arreglo1, arreglo2)
print 'list_comprehensions:', time()-t0

t0 = time()
set_intersection(arreglo1, arreglo2)
print 'set_intersection:', time()-t0

对于前面所说的，必须补充一点append，如果可能的话，列表的方法会降低更多的效率。结果毫无疑问：

for循环：199.760999918
list_comprehensions：92.1570000648
set_intersection：0.0139999389648

• 在PHP存在array_intersect

  $array1 = array(1,2,3,4,5,6);
  $array2 = array(0,2,4,6,8,10);
  $result = array_intersect($array1, $array2);
  print_r($result);
  
  // Salida
  Array
  (
      [1] => 2
      [3] => 4
      [5] => 6
  )
  

• 在Python存在intersection

  array1 = [1,2,3,4,5,6]
  array2 = [0,2,4,6,8,10]
  
  array3 = set(array1).intersection(array2)
  print array3
  
  // Salida
  set([2, 4, 6])
  

在 php 中有一个函数是array_diff()。它所做的是比较两个数组并删除不匹配的数组。前任：

$array1    = array("a" => "a", "b", "c", "d");
$array2    = array("b" => "a", "b", "d");

$resultado = array_diff($array1, $array2);

print_r($resultado);

我会这样做：

arreglo1   = [1,2,3,4,5,6]
arreglo2   = [0,2,4,6,8,10]
repetidos  = []

print("Elementos repetidos: ")
for elemento in arreglo1:
    if elemento in arreglo2:
        repetidos.append(elemento)
        print(elemento)

我尝试了两种算法，array1 = 1-6000 从 1 到 1，array2 = 1-10000 从 2 到 2。

您的实施需要：6,003 秒，我建议的实施需要：2,001 秒。

一切顺利。