Cómo determinar diferencias en dos listas de datos

Question

Este es un ejercicio para que los chicos de CS brillen con la teoría.

Imagina que tienes 2 contenedores con elementos.Carpetas, URL, archivos, cadenas, realmente no importa.

¿Qué es UN algoritmo para calcular lo agregado y lo eliminado?

Aviso:Si hay muchas formas de resolver este problema, publique una por respuesta para que pueda analizarse y votarse.

Editar:Todas las respuestas resuelven el asunto con 4 contenedores.¿Es posible utilizar sólo los 2 iniciales?

Answer 1

Suponiendo que tiene dos listas de elementos únicos y que el orden no importa, puede considerarlas como conjuntos en lugar de listas.

Si piensa en un diagrama de Venn, con la lista A como un círculo y la lista B como el otro, entonces la intersección de estos dos es el grupo constante.

Elimine todos los elementos en esta intersección tanto de A como de B, y todo lo que quede en A se eliminará, mientras que todo lo que quede en B se agregará.

Entonces, itere a través de A buscando cada elemento en B.Si lo encuentras, retíralo tanto de A como de B.

Entonces A es una lista de cosas que se eliminaron y B es una lista de cosas que se agregaron.

Creo...

[editar] Ok, con la nueva restricción de "solo 2 contenedores", lo mismo sigue siendo válido:

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

Entonces no estará construyendo una nueva lista ni destruyendo las antiguas... pero llevará más tiempo como en el ejemplo anterior, podría simplemente recorrer la lista más corta y eliminar los elementos de la más larga.Aquí necesitas hacer ambas listas.

Y yo diría que mi primera solución no usó 4 contenedores, solo destruyó dos ;-)

Answer 2

No he hecho esto desde hace tiempo pero creo que el algoritmo es así...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

En lo que respecta a la relación de la lista de derecha con la lista de izquierda, elimina contiene elementos eliminados y agrega ahora contiene nuevos elementos.

Answer 3

Lo que dijo Joe.Y, si las listas son demasiado grandes para caber en la memoria, utilice una utilidad de clasificación de archivos externa o una clasificación por combinación.

Answer 4

Información faltante:¿Cómo se define agregado/eliminado?P.ej.si las listas (A y B) muestran el mismo directorio en el Servidor A y el Servidor B, eso está sincronizado.Si ahora espero 10 días, vuelvo a generar las listas y las comparo, ¿cómo puedo saber si se ha eliminado algo?No puedo.Sólo puedo decir que hay archivos en el Servidor A que no se encuentran en el Servidor B y/o al revés.Ya sea porque se agregó un archivo al servidor A (por lo tanto, el archivo no se encuentra en B) o se eliminó un archivo en el servidor B (por lo tanto, el archivo no se encuentra en B). ya no) es algo que no puedo determinar con solo tener una lista de nombres de archivos.

Para la solución que sugiero, asumiré que tiene una lista llamada ANTIGUA y una lista llamada NUEVA.Todo lo que se encuentra en ANTIGUO pero no en NUEVO se ha eliminado.Todo lo que se encuentra en NUEVO, pero no en ANTIGUO, se ha agregado (p. ej.el contenido del mismo directorio en el mismo servidor, sin embargo las listas se han creado en fechas diferentes).

Además, asumiré que no hay duplicados.Eso significa que cada elemento de cualquiera de las listas es único en el sentido de:Si comparo este elemento con cualquier otro elemento de la lista (sin importar cómo funcione esta comparación), siempre puedo decir que el elemento es menor o más grande que con el que lo estoy comparando, pero nunca igual.P.ej.cuando trato con cadenas, puedo compararlas lexicográficamente y la misma cadena nunca aparece dos veces en la lista.

En ese caso, la solución más simple (aunque no necesariamente la mejor) es:

1. Ordena las listas ANTIGUAS.P.ej.si la lista consta de cadenas, ordénelas alfabéticamente.La clasificación es necesaria, porque significa que puedo usar la búsqueda binaria para encontrar rápidamente un objeto en la lista, asumiendo que existe allí (o para determinar rápidamente, no existe en la lista en absoluto).Si la lista no está ordenada, encontrar el objeto tiene una complejidad de O(n) (necesito mirar cada elemento de la lista).Si la lista está ordenada, la complejidad es solo O (log n), ya que después de cada intento de hacer coincidir un elemento de la lista, siempre puedo excluir el 50% de los elementos de la lista que no coinciden.Incluso si la lista tiene 100 elementos, encontrar un elemento (o detectar que el elemento no está en la lista) requiere como máximo 7 pruebas (¿o son 8?De todos modos, mucho menos de 100). No es necesario ordenar la lista NUEVA.

2. Ahora realizamos la eliminación de la lista.Para cada elemento de la lista NUEVA, intente encontrar este elemento en la lista ANTIGUA (mediante búsqueda binaria).Si se encuentra el artículo, elimínelo de la lista ANTIGUA y también elimínelo de la NUEVA lista.Esto también significa que las listas se hacen más pequeñas a medida que avanza la eliminación y, por lo tanto, las búsquedas serán cada vez más rápidas.Dado que eliminar un elemento de la lista a no tiene ningún efecto en el orden correcto de las listas, no es necesario recurrir a la lista ANTIGUA durante la fase de eliminación.

3. Al final de la eliminación, ambas listas podrían quedar vacías, en cuyo caso serían iguales.Si no están vacíos, todos los elementos que aún están en la lista ANTIGUA son elementos que faltan en la lista NUEVA (de lo contrario, los habríamos eliminado), por lo tanto, estos son los elementos eliminados.Todos los elementos que aún están en la lista NUEVA son elementos que no estaban en la lista ANTIGUA (nuevamente, de lo contrario los habíamos eliminado), por lo tanto, estos son los elementos añadidos.

Answer 5

¿Los objetos de la lista son "únicos"?En este caso, primero crearía dos mapas (hashmaps) y luego escanearía las listas y buscaría cada objeto en los mapas.

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

Perdón por el horrible metalenguaje que mezcla Ruby y Java :-P

Al final elementos eliminados contendrá los elementos pertenecientes a lista1, pero no a lista2, y elementos añadidos contendrá los elementos pertenecientes a list2.

El coste de toda la operación es O(4*N) ya que la búsqueda en el mapa/diccionario puede considerarse constante.Por otro lado, la búsqueda lineal/binaria de cada elemento en las listas hará que O(N^2).

EDITAR:Pensándolo bien, moviendo el último cheque al segundo bucle, puede quitar uno de los bucles...pero eso es feo...:)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}