Manera mas eficaz de comparar dos arreglos

publicado por: Anonymous

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

solución

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).

Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *