13

Me gustaría saber cual es la manera mas eficaz de comparar el contenido de dos arreglos, realizar esto en la menor cantidad de tiempo posible y ocupar la menor cantidad de recursos.

Presento este ejemplo en Python de como lo realizo de manera diaria. Para este ejemplo que existen pocos elementos demora muy poco tiempo pero sin embargo a medida que agregamos elementos los tiempos aumentan de manera exponencial.

Si desean dar un ejemplo en otro lenguaje bienvenido, la idea es conocer la lógica de como realizarlo por sobre el lenguaje.

Aquí el ejemplo:

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

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

for x in arreglo1:
    for y in arreglo2:
        if x == y:
            repetidos.append(x)

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

La salida es: Los Repetidos son 2 4 6

5 respuestas 5

8

Dado que la pregunta tiene la etiqueta lenguaje-agnóstico responderé a la pregunta como problema computacional y desde un análisis algorítmico.

El problema computacional que intenta resolver es el siguiente: dado un arreglo A de n elementos y un arreglo B de m elementos con n y m enteros no negativos retornar un arreglo C con k elementos donde cada k-ésimo elemento de este arreglo C pertenece tanto al arreglo A como al arreglo B. Es claro que si el arreglo C esta vacío significa que no existen elementos comunes a ambos arreglos.

Una solución trivial a este problema en pseudocódigo es la siguiente:

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

La solución trivial consiste en comparar todos los elementos del arreglo B con cada uno de los elementos del arreglo A e ir añadiendo aquellos que se encuentran repetidos en el arereglo C y retornarlos. Esta solución es, en esencia, la misma que propone en el código en Python que acompaña la pregunta.

Para este ejemplo que existen pocos elementos demora muy poco tiempo pero sin embargo a medida que agregamos elementos los tiempos aumentan de manera exponencial.

Precisemos la anterior afirmación. A partir del pseudocódigo anterior encontramos un doble ciclo anidado. El primer ciclo (línea 2.) se ejecuta n veces (porque el arreglo A tiene n elementos), por cada vez que se ejecuta esa línea la línea 3. se ejecuta m veces (porque el arreglo B tiene m elementos. Esto quiere decir que la cantidad de comparaciones que realiza este procedimiento es n veces m. El análisis del algoritmo muestra entonces que la complejidad del mismo es O(nm) (esta complejidad es una abstracción que, bajo un modelo computacional definido, nos permite determinar el tiempo de ejecución del algoritmo para un tamaño de entrada grande). Si suponemos que ambos arreglos tienen el mismo número de elementos n, la complejidad del algoritmo es O(n^2). Es decir, la complejidad del algoritmo no es 'exponencial' como menciona coloquialmente, sino cuadrática con respecto a n, el tamaño de la entrad del problema.

Dado el contexto anterior la pregunta ahora es: ¿existe un algoritmo mejor que O(n^2) para comparar dos arreglos de tamaño n?. La respuesta es sí.

Si agrega los elementos del primer arreglo a una estructura de datos llamada Hash y luego, recorriendo los elementos del segundo arreglo para verificar si estos se encuentran en la estructura, en caso afirmativo lo agrega al arreglo 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

Las operaciones de añadir y consultar elementos a una estructura hash tienen complejidad computacional O(1), un análisis amortizado deja ver que en los casos promedios la inserción y consulta tardan tiempo constante. Para el algoritmo anterior, la línea 2 se ejecuta n veces (necesitamos añadir n elementos del arreglo A al hash D, para cada ejecución de la línea 2, la línea 3 se ejecuta 1 vez (porque la inserción en la estructura tarda tiempo constante). La línea 4 se ejecuta m veces y por cada ejecución tardamos tiempo constante en verificar si el elemento m-ésimo del arreglo se encuentra en la estructura hash, de ser así, es claro que el elemento está repetido y lo agregamos al arreglo C.

A partir de lo anterior es claro que la complejidad computacional del nuevo algoritmo es O(n), es decir, es lineal con respecto al tamaño de los elementos del arreglo. Esta es una mejora sustancial al algoritmo anterior con complejidad O(n^2), recordemos que el objetivo de establecer la complejidad es identificar el tiempo de ejecución cuando el tamaño de la entrada tiende a valores cada vez más grandes.

Surge entonces una duda, ¿es posible superar el algoritmo anterior?, la respuesta es no. Claramente, para identificar cuáles elementos están repetidos en ambos arreglos debemos recorrer al menos una vez alguno de los arreglos, por lo que al menos hay que realizar O(n) operaciones.

Otras implementaciones de algoritmos permiten tener complejidades computacionales decentes. Una estrategia posible es ordenar ambos arreglos y hacer un recorrido lineal comparando cada uno de los elementos (no de a pares como el primer algoritmo, sino usando dos iteradores que garantizan recorrer los dos arreglos en O(n+m), o O(n). Si suponemos que usamos un algoritmo de ordenamiento de orden O(nlogn), la complejidad de este algoritmo es, precisamente O(nlogn). Otra posibilidad consiste en suponer que tanto A como B vienen ordenados, por lo que la complejidad computacional es, usando el algoritmo anterior, O(n).

En definitiva: la forma más eficaz para comparar dos arreglos, sin hacer ningún tipo de suposición adicional es usando un Hash, que garantiza una complejidad computacional en la mayoría de los casos de O(n).

4
  • Buena respuesta, pero garantiza una complejidad computacional en la mayoria de los casos de O(n) viene a ser, mas o menos, que no se garantiza esa complejidad ¿cierto?. De hecho, una tabla hash puede degenerar, en el peor de los casos, en una complejidad O(n) para cada acceso, con lo que tendriamos O(n) para recorrer el arreglo, + O(n) por cada inserción en la hash, mas O(n) por cada búsqueda en ella. Tu propuesta, en el mejor de los casos, tarda O(n), y, en el peor, O(3n). Mas una duplicación de datos.
    – Trauma
    el 21 dic. 2016 a las 6:10
  • Asintóticamente O(3n) es equivalente a O(n). Y sí, en el peor de los casos las operaciones de búsqueda e inserción de datos en un hashtable tienen complejidad O(n), por lo que en estos casos el algoritmo tardaría nuevamente O(n^2), pero esto depende fuertemente de los datos contenidos en los arreglos y suponiendo que no exista una gran cantidad de colisiones producto de estos elementos.
    – dwarandae
    el 21 dic. 2016 a las 6:38
  • Creo que deberias matizar la respuesta, indicándola como una posible solucion para un tipo de caso concreto. Y las hash no se llevan bién con los datos repetidos. [ 1 1 1 2 3 3 3 ] comparado con [ 1 1 1 2 3 3 2 ]. Es que la pregunta es muy, pero que muy amplia, y una respuesta categórica y asi de concreta no me parece correcta; al final dejas entrever otras posibles técnicas, pero sin desarrollarlas.
    – Trauma
    el 21 dic. 2016 a las 6:56
  • Entiendo la inquietud, la pregunta del OP es 'cuál es la manera más eficaz de comparar el contenido de dos arreglos' (para encontrar duplicados) y sin ninguna suposición adicional la mejor solución tiene complejidad O(n), no hay una mejor cota inferior. Es lo único que se puede asumir.
    – dwarandae
    el 21 dic. 2016 a las 6:59
5

No existe un método general que sea el más eficiente. Va a depender de muchos factores, pero uno muy importante va a ser el lenguaje que se usa. Para cada lenguaje es posible que exista una forma más eficiciente que otra. Una lista de Python no es lo mismo que un array de C o un Vector de C++. Hay siempre ideas generales como evitar al máximo el numero de iteraciones completas sobre el array, usar tablas hash si es posible, etc pero va a depender de cada lenguje e incluso del tipo de dato.

Hablando específicamente de Python y basandome en tu ejemplo, el problema de usar ese método es que por cada elemento de arreglo1 recorres el arreglo2 entero. en Python una forma mucho más eficiente de ver los elementos que estan presentes en dos iterables simultaneamente es usar el método intersection() de los conjuntos (set), que toma dos conjuntos y retorna otro conjunto con los elementos presentes en ambos:

#!/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

Edición:

Añado una pequeña comparativa usando dos listas de 100000 elementos cada una. Comparo tu código, con una alternativa más eficiente usando in y list comprehensions y con set.intersection(). Las tres funciones retornan una lista.

#!/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

A lo comentado antes hay que añadir que el método append de las listas resta aún más eficiencia si cabe. Los resultados no dejan muchas dudas:

ciclo for: 199.760999918
list_comprehensions: 92.1570000648
set_intersection: 0.0139999389648

1
  • 1
    @PatricioNicolas he añadido una comparativa entre tu método, uno más eficiente usando lists comprehensions y set.intersection() usando una lista de 100000. El manejo de conjuntos es realmente mucho más eficiente que el de listas dada la forma de almacenamiento interno de los datos (hash table) que hace las búsquedas infinitamente más rápidas que en las listas.
    – FJSevilla
    el 17 dic. 2016 a las 2:47
3
  • En PHP existe 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
    )
    
  • En Python existe 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])
    
0
2

En php existe una función que lo hace es array_diff(). Lo que hace es comparar dos array y sacar las que no coinciden. Ej:

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

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

print_r($resultado);
1
  • No sirve de mucho si la implementación de esta función es de tiempo cuadrático.
    – user227
    el 18 dic. 2016 a las 15:18
1

Así lo haría yo:

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)

Probé ambos algoritmos con arreglo1 = 1-6000 de 1 en 1 y arreglo2 = 1-10000 de 2 en 2.

Tu implementación tardo: 6.003 segundos, la que propongo tarda: 2.001 segundos.

Un saludo.

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.