algorithm - que - Cómo determinar las diferencias en dos listas de datos

comparar dos listas en excel y marcar diferencias con colores

Question

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

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

¿Qué es un algoritmo AN para calcular el agregado y el eliminado?

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

Editar : Todas las respuestas resuelven el problema con 4 contenedores. ¿Es posible usar solo los 2 iniciales?

Answer 1

¿Los objetos en la lista son "únicos"? En este caso, primero construirí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, los elementos eliminados contendrán los elementos que pertenecen a la lista1, pero no a la lista2, y los elementos agregados contendrán los elementos que pertenecen a la lista2.

El costo 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 : en un segundo pensamiento moviendo el último cheque al segundo ciclo, puedes 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)
}

Answer 2

Información faltante: ¿cómo se define agregado / eliminado? Por ejemplo, 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 eliminó algo? No puedo. Solo puedo decir que hay archivos en el Servidor A que no se encuentran en el Servidor B y / o al revés. Si eso se debe a que se ha agregado un archivo al Servidor A (por lo tanto, el archivo no se encuentra en B) o se ha eliminado un archivo en el Servidor B (el archivo ya no se encuentra en B) es algo que no puedo determinar con solo una lista de nombres de archivos.

Para la solución que sugiero, solo asumiré que tiene una lista llamada OLD y una lista llamada NEW. Todo lo que se encontró en VIEJO pero no en NUEVO ha sido eliminado. Todo lo que se encuentra en NUEVO, pero no en OLD se ha agregado (por ejemplo, el contenido del mismo directorio en el mismo servidor, sin embargo, las listas se han creado en diferentes fechas).

Además, asumiré que no hay duplicados. Eso significa que cada elemento de una u otra lista es único en el sentido de: si comparo este artículo con cualquier otro artículo de la lista (no importa cómo funcione esta comparación), siempre puedo decir que el artículo es más pequeño o más grande que el que Estoy comparando, pero nunca igual. Por ejemplo, cuando se trata de cadenas, puedo compararlas lexicográficamente y la misma cadena nunca está dos veces en la lista.

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

1. Ordene las listas VIEJAS. Por ejemplo, si la lista consta de cadenas, ordénelas alfabéticamente. La ordenación es necesaria, porque significa que puedo usar la búsqueda binaria para encontrar rápidamente un objeto en la lista, suponiendo que exista allí (o para determinar rápidamente, no existe en absoluto en la lista). Si la lista no está ordenada, encontrar el objeto tiene una complejidad de O (n) (necesito ver 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 que el 50% de los elementos de la lista no coincidan. Incluso si la lista tiene 100 elementos, encontrar un artículo (o detectar que el artículo no está en la lista) toma como máximo 7 pruebas (¿o es 8? De todos modos, mucho menos de 100). La lista NUEVA no tiene que ser ordenada.

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

3. Al final de la eliminación, ambas listas pueden estar vacías, en cuyo caso son iguales. Si no están vacíos, todos los elementos que aún están en la lista VIEJA son elementos que faltan en la lista NUEVA (de lo contrario, los habíamos eliminado), por lo tanto, estos son los elementos eliminados . Todos los artículos que todavía están en la lista NUEVA son artículos que no estaban en la lista ANTIGUO (de nuevo, los habíamos quitado de otra manera), por lo tanto estos son los elementos agregados .

Answer 3

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

Answer 4

No he hecho esto por un 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

Con respecto a la relación de la lista de la derecha con la lista de la izquierda, las eliminaciones contienen elementos eliminados y ahora agrega nuevos elementos.

Answer 5

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

Si piensas 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 conjunto constante.

Elimina todos los elementos en esta intersección de A y B, y todo lo que queda en A se ha eliminado, mientras que todo lo que queda en B se ha agregado.

Por lo tanto, itere por A buscando cada elemento en B. Si lo encuentra, elimínelo de A y B

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

Creo...

[edit] De acuerdo, 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 estás construyendo una nueva lista, o destruyendo las viejas ... pero tomará más tiempo que con el ejemplo anterior, podrías pasar por encima de la lista más corta y eliminar los elementos de la lista más larga. Aquí tienes que hacer ambas listas

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