Comment déterminer les différences dans deux listes de données

Question

Ceci est un exercice pour les gars de CS à briller avec la théorie. Imaginez que vous ayez 2 conteneurs avec des éléments.

Dossiers, URL, fichiers, chaînes, ce n'est vraiment pas important.

Qu'est-ce qu'un algorithme pour calculer l'ajout et le retrait?

Avis: S'il y a plusieurs façons de résoudre ce problème, veuillez en poster un par réponse afin qu'il puisse être analysé et voté.

Édition: Toutes les réponses résolvent le problème avec 4 conteneurs. Est-il possible d'utiliser seulement le 2 initial?

Answer 1

En supposant que vous avez deux listes d'articles uniques et l'ordre n'a pas d'importance, vous pouvez penser à eux à la fois comme des ensembles plutôt que des listes

Si vous pensez d'un diagramme de Venn, avec la liste A comme un cercle et liste B comme l'autre, puis l'intersection de ces deux est le pool constant.

Supprimer tous les éléments de cette intersection de A et B, et tout ce qui reste dans A a été supprimé, tandis que tout ce qui reste dans B a été ajouté.

Ainsi, itérer A la recherche de chaque élément B. Si vous le trouvez, retirez-le de A et B

A est une liste de choses qui ont été supprimés, et B est une liste de choses qui ont été ajoutés

Je pense ...

[modifier] Ok, avec la nouvelle restriction "à seulement 2 conteneurs", la même chose encore:

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

Ensuite, vous n'êtes pas constru cting une nouvelle liste, ou détruire vos anciennes ... mais cela prendra plus de temps que dans l'exemple précédent, vous pourriez simplement boucler la liste plus courte et enlever les éléments du plus long. Ici, vous devez faire les deux listes

Un je dirais ma première solution n'a pas utilisé 4 conteneurs, il vient de détruire deux ;-)

Answer 2

Je ne l'ai pas fait cela dans un certain temps, mais je crois que l'algorithme va comme ça ...

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 ce qui concerne la relation de droite liste à gauche liste, supprime contient les éléments supprimés et ajoute contient maintenant de nouveaux éléments.

Answer 3

Qu'est-ce que Joe a dit. Et, si les listes sont trop volumineuses pour tenir dans la mémoire, utilisez un utilitaire de tri de fichiers externe ou un tri Merge.

Answer 4

Informations manquantes: Comment définissez-vous ajouté/supprimé? Par exemple. si les listes (A et B) affichent le même répertoire sur le serveur A et le serveur B, cela est synchronisé. Si j'attends maintenant 10 jours, générer à nouveau les listes et les comparer, comment puis-je savoir si quelque chose a été supprimé? Je ne peux pas. Je peux seulement dire qu'il y a des fichiers sur le serveur A que l'on ne trouve pas sur le serveur B et/ou l'inverse.Que ce soit parce qu'un fichier a été ajouté au serveur A (donc le fichier n'est pas trouvé sur B) ou qu'un fichier a été supprimé sur le serveur B (donc le fichier n'est plus sur B plus) est quelque chose que je ne peux pas déterminer juste avoir une liste de noms de fichiers.

Pour la solution que je suggère, je suppose que vous avez une liste nommée OLD et une liste nommée NEW. Tout ce qui a été trouvé sur OLD mais pas sur NEW a été supprimé. Tout ce qui a été trouvé sur NEW, mais pas sur OLD a été ajouté (par exemple, le contenu du même répertoire sur le même serveur, mais les listes ont été créées à des dates différentes).

En outre, je supposerai qu'il n'y a pas de doublons. Cela signifie que chaque élément de chaque liste est unique au sens de: Si je compare cet élément à un autre élément de la liste (peu importe comment cette comparaison fonctionne), je peux toujours dire que l'élément est soit plus petit ou plus grand que celui que je compare, mais jamais égal. Par exemple. quand je traite des chaînes, je peux les comparer lexicographiquement et la même chaîne n'est jamais deux fois dans la liste.

Dans ce cas, le plus simple (la meilleure solution pas nécessairement, si) est:

1. Trier les listes vieux. Par exemple. si la liste est constituée de chaînes, triez-les par ordre alphabétique. Le tri est nécessaire, car cela signifie que je peux utiliser la recherche binaire pour trouver rapidement un objet dans la liste, en supposant qu'il y existe (ou pour le déterminer rapidement, il n'existe pas du tout dans la liste). Si la liste n'est pas triée, trouver l'objet a une complexité de O (n) (j'ai besoin de regarder chaque élément de la liste). Si la liste est triée, la complexité est seulement O (log n), car après chaque tentative de faire correspondre un élément de la liste, je peux toujours exclure 50% des éléments de la liste qui ne correspondent pas. Même si la liste contient 100 éléments, trouver un élément (ou détecter que l'élément ne figure pas dans la liste) nécessite au maximum 7 tests (ou est-ce 8? Quoi qu'il en soit, beaucoup moins que 100). La nouvelle liste n'a pas besoin d'être triée.

2. Maintenant, nous effectuons l'élimination de la liste. Pour chaque article de la liste NEW, essayez de trouver cet article dans la liste OLD (en utilisant la recherche binaire). Si l'élément est trouvé, supprimez cet élément de la liste OLD et également supprimez-le de la liste NEW. Cela signifie également que les listes diminuent au fur et à mesure que l'élimination progresse et que les recherches deviennent de plus en plus rapides. Comme la suppression d'un élément de la liste n'a aucun effet sur l'ordre de tri correct des listes, il n'est pas nécessaire de recourir à la liste OLD pendant la phase d'élimination.

3. À la fin de l'élimination, les deux listes pouvaient être vides, auquel cas elles étaient égales. S'ils ne sont pas vides, tous les éléments de la liste OLD sont manquants dans la liste NEW (sinon nous les avons supprimés), donc ce sont les éléments supprimés. Tous les éléments de la liste NEW sont des éléments qui ne figuraient pas dans la liste OLD (encore une fois, nous les avons supprimés). Par conséquent, ce sont les éléments ajoutés .

Answer 5

Les objets de la liste sont-ils "uniques"? Dans ce cas, je voudrais d'abord construire deux cartes (hashmaps), puis analyser les listes et rechercher tous les objets dans les cartes.

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

Désolé pour le méta-langage Ruby et horribles mélange Java :-P

En fin de removedElements contiendra les éléments appartenant à list1, mais pas List2 et addedElements contiendra les éléments appartenant à list2.

Le coût de l'ensemble de l'opération est O (4 * N) car la recherche dans la carte/dictionnaire peut être considérée comme constante. D'autre part, la recherche linéaire/binaire de chaque élément dans les listes fera que O (N^2).

EDIT: sur une seconde pensée en mouvement le dernier contrôle dans la deuxième boucle, vous pouvez retirer l'une des boucles ... mais c'est moche ... :)

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