comparar dos secuencias

[wruano]

Hola estoy trabajando un programa que me debe compara dos secuencias y decirme cuales elemntos son iguales.
el problema es que no quiero compara cada elemnto con todos los elemtos de la otra secuencia y no se me ocurre nada. si alguien puede ayudarme le agradesco de antemano

[yalmar]

Para este tipo de consultas STL tiene algoritmos ya listos para usar

std::set<int> a, b;

std::set_intersection<...>(...);
std::set_difference<...>(...);
std::set_union<...>(...);
std::set_symmetric_difference<...>(...);

vean el manual.

salu2

[andresprimo]

Hola.

Ya han transcurrido varios años desde la formulacion de la pregunta, pero doy una respuesta para colaborar con quienes necesiten una orientacion al respecto.
Para ahorrar comparaciones, es imprescindible que los datos esten *ordenados* en ambas listas (por ej de menor a mayor). Ademas, ayudaria que en cada lista no hayan datos repetidos, es decir, que aparezcan 1 sola vez. Para recordar los elementos iguales en ambas listas se puede tener una 3ra lista para guardar esos elementos, o bien para recordar la posicion del elemento (nro de celda de la lista) en la lista 1 o lista 2 (alguna de ellas, pues el elemento repetido estara en ambas aunque en posiciones posiblemente distintas). Como la posicion relativa es un numero, consume menos espacio que recordar una cadena larga por ejemplo.

Trabajaremos con punteros. Esto significa que habran dos variables, cada una de ellas tendra el nro de celda de la lista en que estamos trabajando. Pueden llamarse PosLista1 y PosLista2. Tambien habra otro puntero adicional para la 3ra lista donde guardamos los elementos iguales - PosListaIguales (valor inicial=1).

Se compara el elemento en curso de ambas listas empezando con 1 (PosLista1=PosLista2=1).
Aclaro que el elemento "en curso" de la lista1 es Lista1[PosLista1], y de la lista2 es Lista2[PosLista2].

INICIO DEL BUCLE
- Si son iguales (Lista1[PosLista1]==Lista2[PosLista2]), se guarda el elemento o su posicion en la lista auxiliar
(ListaIguales[PosListaIguales]=Lista1[PosLista1]). Luego se avanzan los 3 punteros (PosLista1++,PosLista2++,PosListaIguales++).
-Si es menor (Lista1[PosLista1]<Lista2[PosLista2]), se incrementa PosLista1 para trabajar con el siguiente elemento.
-Si es mayor (Lista1[PosLista1]>Lista2[PosLista2]), se incrementa PosLista2 para trabajar con el siguiente elemento.

aclaracion: los casos deben procesarse el uno o el otro en forma excluyente.
Ej: IF iguales then esto1 ELSE IF menor then esto2 ELSE IF mayor then esto3.

Ahora hay que verificar si (PosLista1>CantElemLista1) o (PosLista2>CantElemLista2) en cuyo caso terminan las comparaciones (se sale del bucle) por haberse recorrido todos los elementos de alguna de las listas. Se asume que el puntero de la lista de iguales siempre podra avanzar porque hay espacio en la lista auxiliar. Para que eso sea siempre posible, CantElemListaIguales debe ser igual a MIN(CantElemLista1,CantElemLista2), es decir, tantos elementos como la lista mas corta de elementos a comparar.

Luego de esto volvemos al inicio del bucle y se itera hasta que salga por agotarse alguna de las listas.

Finalmente, la cantidad de elementos iguales sera PosListaIguales-1, porque el puntero PosListaIguales simpre señala una celda vacia donde colocar el elemento igual que se haya encontrado. Si (PosListaIguales-1)=0 significa que no hay elementos iguales en las listas comparadas.

Se ve que siempre avanzamos el puntero en la lista que tiene el elemento menor hasta que sea mayor o igual. Si es igual procesamos ese elemento en la lista de iguales, sino volvemos a avanzar el puntero en la lista del elemento menor hasta agotar todos los elementos.
Esta claro que ambas listas se recorren linealmente una sola vez sin retrocesos lo que minimiza la cantidad de comparaciones, y esto es posible gracias a que las listas estan ordenadas. Tambien vemos que si hubieran elementos repetidos en cada lista, habria que complicar el programa para manejar ese caso molesto.

---------------------

*** Tambien hay otra forma de hacerlo, y mas simple todavia.

Una vez ordenadas ambas listas, y procesadas para que no hayan elementos repetidos (para hacerlo hay que ordenar las listas aunque con tecnicas HASH podemos ahorrar eso) como hicimos en el algoritmo anterior, se coloca todo junto en una *ListaUnificada* y se la ordena de menor a mayor como venimos haciendo. Esto consumira mas espacio en memoria, pero simplificara el algoritmo.
Entonces, si hay elementos iguales necesariamente estaran repetidos en la lista unificada (aparecera 2 veces). La idea es comparar el elemento con el siguiente de la lista unica para ver si es igual. Si lo es guardamos ese elemento en la lista de iguales, sino avanzamos el puntero. Entonces empezamos con PosListaUnica=1 y PosListaIguales=1.

INICIO DEL BUCLE

Ahora comparamos ListaUnica[PosListaUnica] con ListaUnica[PosListaUnica+1].
-Si son iguales, ListaIguales[PosListaIguales]=ListaUnica[PosListaUnica], y PosListaUnica += 2 para saltear el elemento repetido. PosListaIguales++.
-Si no son iguales, PosListaUnica++.

Ahora verificamos el puntero de la lista. Debemos saber que habra un elemento siguiente porque podemos estar parados sobre el ultimo elemento. Preguntamos si PosListaUnica es menor a CantElemListaUnica. Si es menor, seguimos adelante volviendo al comienzo del bucle, pero en caso contrario se termino la busqueda. Vale decir que CantElemListaUnica es CantElemLista1+CantElemLista2.

Vemos que gracias a la lista unica ordenada nos ahorramos manejar 2 punteros (1 para cada lista) ya que no hay necesidad de averiguar cual es menor gracias al ordenamiento de la lista unificada. Siempre estaremos parados en el elemento menor y si son iguales lo sabremos con el elemento siguiente en la lista (tan simple como eso!!), pero el costo es consumir mas memoria.

------------------------------------

Uso de tecnicas HASH para eliminar elementos repetidos en Lista1 y Lista2 haciendo que sean unicos.
Esto acelera mucho la eliminacion de elementos repetidos en ambas listas de datos.

Este paso es necesario porque la repeticion de elementos en cada una de las listas de datos trae problemas en los algoritmos descriptos aqui. Quitar esos elementos repetidos requiere ordenar las listas, y luego recorrerlas comparando cada elemento con el siguiente para ver si son iguales, en cuyo caso se trata de un elemento repetido que debe eliminarse. Pero pueden haber varias repeticiones (por ejemplo, estar 3 veces en la lista). Es decir, una vez eliminado el dato repetido, el que sigue puede ser otro igual que tambien hay que quitar.

Con una tabla HASH, podemos recorrer cada lista de datos, Y SIN NECESIDAD DE ORDENARLAS poder saber si ese elemento es repetido por haberlo visto antes. Para eso hay que tener una tabla hash que seria una lista adicional, que contendra valores generados por la funcion hash. ElementoHASH=FuncionHASH(ElementoLista). La funcion hash es una formula matematica que genera un numero a partir de un dato que ingresa como argumento de la funcion. Ese elemento hash generado debe ser unico para cada dato, es decir, la funcion hash no deberia generar un mismo elemento hash para dos datos distintos porque arruinaria este metodo. Para estar seguros, ese numero debe ser de 64 bits (8 bytes) con una funcion hash de buena calidad (buscar en bibliografia) que trabaje con numeros primos, y varias operaciones de procesamiento de bits (XOR, etc). Lo practico de esto es que el dato puede ser una cadena larga de muchos bytes que se compacta con un elemento hash de menor longitud (aunque suficientemente grande para evitar el problema mencionado). A su vez, el valor hash debe tener asociado una posicion en la tabla hash, para lo cual se aplica una funcion de ubicacion sobre el valor hash que es muy sencilla, a fin de distribuir los valores a lo largo de toda la tabla. PosHASH=FuncionPosHASH(ElementoHASH). Si la longitud de la tabla es potencia de dos todo se hace muy simple. Por ejemplo, con 1024 posiciones tenemos 2 elevado a la potencia 10. Esto significa que tomamos los ultimos 10 bits del valor hash para generar su posicion en la tabla. (PosHASH=ElementoHASH AND 1023).

Entonces se toma el elemento de la lista, se genera su valor hash y su posicion en la tabla hash. Vemos que hay en ListaHASH[PosHASH]. Si hay cero, significa que la celda esta vacia y no se habia visto antes ese elemento. Entonces, guardamos el valor hash generado alli. ListaHASH[PosHASH]=ElementoHASH. Si habia algo, vemos si es igual al valor hash generado. ListaHASH[PosHASH]==ElementoHASH?. Si es igual entonces se trata de un elemento repetido que ya aparecio antes el cual debe ignorarse. Si es distinto pero no cero, se trata de una "colision". Esto significa que dos valores hash distintos generaron la misma posicion en la tabla. En los libros se analizan distintas estrategias para el manejo de colisiones, pero vale decir que ese riesgo se minimiza haciendo un poco mas grande la tabla hash (un 30% mas de celdas), tomando como base CantElemLista.

Gracias al uso de la tabla hash no hay que ordenar la lista de datos para descubrir sus elementos repetidos, y tambien la lista se recorre linealmente sin retrocesos ganando velocidad.
Hay que aclarar que Lista1 y Lista2 pueden tener tamaños diferentes, exigiendo lo mismo con la tabla hash que se use. La tabla hash se usa para cada lista por vez, y siempre comienza vacia, es decir, con todos sus valores en cero.

*********************

Y como metodo avanzado, se puede hacer un algoritmo avanzado usando una tabla hash no ya para detectar elementos repetidos en una lista, sino tambien para saber si el elemento de la otra lista ya fue visto en la primera lista que seria el caso de un elemento coincidente buscado. La tabla hash contendria codigos hash de los elementos de la primera lista unicamente, y la segunda lista de datos generaria codigos solo para buscarlos y compararlos con el contenido de la tabla hash. Si al comparar se descubre una coincidencia, hay que marcarla en la tabla hash para que ignore las coincidencias posteriores debido a elementos repetidos en la lista2 que pudieran estar en la lista1. Las coincidencias no marcadas indicarian el caso de elementos iguales en ambas listas (a guardar en ListaIguales), Y TODO SIN ORDENAR NADA AHORRANDO TIEMPO DE EJECUCION. Tambien es mas inteligente utilizar la lista de datos mas corta para cargarla en la tabla hash ahorrando memoria y colisiones tambien.

--------------------------------

Espero haber aportado un panorama bastante completo sobre como trabajar con casos como este, desde una solucion sencilla hasta otra mucho mas avanzada como la que utiliza tecnicas HASH de localizacion rapida de elementos sin ordenacion requerida.


ANDRES.-