Самый эффективный способ сравнить два массива

Поскольку у вопроса есть тег, я lenguaje-agnósticoотвечу на вопрос как на вычислительную проблему и на основе алгоритмического анализа.

Вычислительная задача, которую он пытается решить, следующая: задан массив A из n элементов и массив B из m элементов с n и m неотрицательными целыми числами, вернуть массив C с k элементами, где каждый k-й элемент этого массива C принадлежит как к массиву 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 раз (нам нужно добавить n элементов массива A к хэшу D , для каждого выполнения строки 2 строка 3 выполняется 1 раз (потому что вставка в структуру занимает постоянное время) Строка 4 казнен мраз и для каждого выполнения мы берем постоянное время, чтобы проверить, находится ли m-й элемент массива в хеш-структуре, если да, то видно, что элемент повторяется и мы добавляем его в массив C.

Из вышеизложенного видно, что вычислительная сложность нового алгоритма составляет O(n) , то есть она линейна по отношению к размеру элементов массива. Это существенное улучшение по сравнению с предыдущим алгоритмом со сложностью O(n^2) . Помните, что целью установки сложности является определение времени выполнения, когда размер входных данных стремится ко все большим и большим значениям.

Тогда возникает вопрос, можно ли побороть предыдущий алгоритм? , ответ нет . Ясно, что для того, чтобы определить, какие элементы повторяются в обоих массивах, мы должны пройтись по некоторым массивам хотя бы один раз, поэтому необходимо выполнить как минимум O(n) операций.

Другие реализации алгоритма допускают достойную вычислительную сложность. Одной из возможных стратегий является сортировка обоих массивов и линейный обход, сравнивающий каждый из элементов (не попарно, как в первом алгоритме, а с использованием двух итераторов, которые гарантируют обход двух массивов за O(n+m) или O(n , если мы предполагаем, что используем алгоритм упорядочения порядка O(nlogn) , сложность этого алгоритма точно равна O(nlogn) . Другая возможность состоит в том, чтобы предположить, что и A , и B упорядочены, поэтому вычислительная сложность равна , используя алгоритм выше , О(п) .

Вкратце: самый эффективный способ сравнить два массива без каких-либо дополнительных предположений — это использовать хэш, который гарантирует вычислительную сложность в большинстве случаев O(n) .

Не существует универсального метода, который был бы наиболее эффективным. Это будет зависеть от многих факторов, но очень важным из них будет используемый язык. Для каждого языка возможно, что существует более эффективный способ, чем другой. Список Python — это не то же самое, что массив C или вектор C++. Всегда есть общие идеи, такие как максимальное избегание количества полных итераций по массиву, использование хеш-таблиц, если это возможно, и т. д., но это будет зависеть от каждого языка и даже от типа данных.

Говоря конкретно о Python и основываясь на вашем примере, проблема с использованием этого метода заключается в том, что для каждого элемента arreglo1вы перебираете arreglo2целое число. В Python гораздо более эффективный способ одновременно увидеть элементы, присутствующие в двух итерируемых объектах, — это использовать метод set intersection()( 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списков вычитает еще большую эффективность, если это возможно. Результаты не оставляют сомнений:

для цикла: 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.

Ваша реализация занимает: 6003 секунды, та, которую я предлагаю, занимает: 2001 секунду.

Всего наилучшего.