Come determinare le differenze in due elenchi di dati

StackOverflow https://stackoverflow.com/questions/127151

Domanda

Questo è un esercizio per i ragazzi CS per brillare con la teoria.

Immagina di avere 2 contenitori con elementi. Cartelle, URL, file, stringhe, non importa davvero.

Che cos'è un algoritmo AN per calcolare l'aggiunta e la rimozione?

Avviso : se esistono molti modi per risolvere questo problema, pubblicane uno per risposta in modo che possa essere analizzato e votato.

Modifica : tutte le risposte risolvono la questione con 4 contenitori. È possibile utilizzare solo il 2 iniziale?

È stato utile?

Soluzione

Supponendo che tu abbia due elenchi di articoli unici e l'ordine non ha importanza, puoi pensarli entrambi come set piuttosto che elenchi

Se pensi a un diagramma di Venn, con l'elenco A come un cerchio e l'elenco B come l'altro, allora l'intersezione di questi due è il pool costante.

Rimuovi tutti gli elementi in questa intersezione sia da A che da B, e tutto ciò che è rimasto in A è stato eliminato, mentre è stato aggiunto qualsiasi elemento lasciato in B.

Quindi, scorrere A cercando ogni elemento in B. Se lo trovi, rimuovilo sia da A che da B

Quindi A è un elenco di cose che sono state eliminate e B è un elenco di cose che sono state aggiunte

Penso ...

[modifica] Ok, con il nuovo " solo 2 container " restrizione, lo stesso vale ancora: 

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

Quindi non stai costruendo un nuovo elenco, o distruggendo quelli vecchi ... ma ci vorrà più tempo come nell'esempio precedente, potresti semplicemente passare in rassegna l'elenco più breve e rimuovere gli elementi dal più lungo. Qui devi fare entrambe le liste

Direi che la mia prima soluzione non ha usato 4 contenitori, ne ha solo distrutti due ;-)

Altri suggerimenti

Non lo faccio da un po 'ma credo che l'algoritmo vada in questo modo ... 

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

Per quanto riguarda la relazione dell'elenco di destra con l'elenco di sinistra, elimina contiene elementi rimossi e aggiunge ora contiene nuovi elementi.

Quello che ha detto Joe. E, se gli elenchi sono troppo grandi per adattarsi alla memoria, utilizzare un'utilità di ordinamento file esterna o un ordinamento Merge.

Informazioni mancanti: come definisci aggiunto / rimosso? Per esempio. se gli elenchi (A e B) mostrano la stessa directory sul server A e sul server B, è sincronizzato. Se ora aspetto 10 giorni, genera di nuovo le liste e le confronta, come posso sapere se qualcosa è stato rimosso? Non posso. Posso solo dire che ci sono file sul server A non trovati sul server B e / o viceversa. Sia perché un file è stato aggiunto al server A (quindi il file non è stato trovato su B) o un file è stato eliminato sul server B (quindi il file non si trova più su B più ) è qualcosa che non posso determinare semplicemente avendo un elenco di nomi di file.

Per la soluzione che suggerisco, presumo solo che tu abbia una lista chiamata OLD e una lista chiamata NEW. Tutto ciò che è stato trovato su OLD ma non su NEW è stato rimosso. Tutto ciò che è stato trovato su NEW, ma non su OLD è stato aggiunto (ad es. Il contenuto della stessa directory sullo stesso server, tuttavia gli elenchi sono stati creati in date diverse).

Inoltre supporrò che non ci siano duplicati. Ciò significa che ogni elemento in entrambi gli elenchi è unico nel senso di: Se confronto questo oggetto con qualsiasi altro elemento dell'elenco (non importa come funziona questo confronto), posso sempre dire che l'elemento è più piccolo o più grande di quello con cui lo sto confrontando, ma mai uguale. Per esempio. quando ho a che fare con le stringhe, posso confrontarle lessicograficamente e la stessa stringa non è mai due volte nell'elenco.

In quel caso la soluzione più semplice (non necessariamente migliore) è:

  1. Ordina gli elenchi VECCHI. Per esempio. se l'elenco è composto da stringhe, ordinale in ordine alfabetico. L'ordinamento è necessario, perché significa che posso usare la ricerca binaria per trovare rapidamente un oggetto nell'elenco, supponendo che esista lì (o per determinare rapidamente, non esiste affatto nell'elenco). Se l'elenco non è ordinato, la ricerca dell'oggetto presenta una complessità di O (n) (ho bisogno di guardare ogni singolo elemento dell'elenco). Se l'elenco è ordinato, la complessità è solo O (log n), poiché dopo ogni tentativo di abbinare un elemento nell'elenco, posso sempre escludere che il 50% degli elementi nell'elenco non corrisponda. Anche se l'elenco contiene 100 elementi, trovare un oggetto (o rilevare che l'oggetto non è nell'elenco) richiede al massimo 7 test (o sono 8? Comunque, molto meno di 100). La NUOVA lista non deve essere ordinata.

  2. Ora eseguiamo l'eliminazione dell'elenco. Per ogni elemento nella NUOVA lista, prova a trovare questa voce nella VECCHIA lista (usando la ricerca binaria). Se l'elemento viene trovato, rimuovilo dall'elenco VECCHIO e anche rimuovilo dall'elenco NUOVO. Questo significa anche che le liste diventano più piccole man mano che procede l'eliminazione e quindi le ricerche diventeranno sempre più veloci. Poiché la rimozione di un elemento dall'elenco a non ha alcun effetto sul corretto ordinamento degli elenchi, non è necessario ricorrere all'elenco OLD durante la fase di eliminazione.

  3. Alla fine dell'eliminazione, entrambe le liste potrebbero essere vuote, nel qual caso erano uguali. Se non sono vuoti, tutti gli elementi ancora presenti nell'elenco OLD sono elementi mancanti nell'elenco NEW (altrimenti li abbiamo rimossi), quindi questi sono gli elementi rimossi . Tutti gli elementi ancora nella NUOVA lista sono elementi che non erano nella VECCHIA lista (di nuovo, li avevamo rimossi altrimenti), quindi questi sono gli elementi aggiunti .

Gli oggetti nella lista " unique " ;? In questo caso, per prima cosa creerei due mappe (hashmaps) e quindi scansionerò le liste e cercherò ogni oggetto nelle mappe. 

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

Ci scusiamo per il terribile meta-linguaggio che mescola Ruby e Java :-P

Alla fine rimossoElementi conterrà gli elementi appartenenti all'elenco1, ma non a elenco2, e elementi aggiunti conterrà gli elementi appartenenti all'elenco2.

Il costo dell'intera operazione è O (4 * N) poiché la ricerca nella mappa / dizionario può essere considerata costante. D'altra parte la ricerca lineare / binaria di ciascun elemento nelle liste renderà quella O (N ^ 2).

MODIFICA : con un secondo pensiero spostando l'ultimo controllo nel secondo ciclo puoi rimuovere uno dei circuiti ... ma è brutto ... :) 

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)
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top