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

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

Question

Il s’agit d’un exercice permettant aux gars de CS de briller avec la théorie.

Imaginez que vous avez 2 conteneurs avec des éléments. Les dossiers, les URL, les fichiers, les chaînes, peu importe.

Qu'est-ce qu'un algorithme AN ??pour calculer l'ajout et l'élimination?

Remarque : s'il existe plusieurs façons de résoudre ce problème, postez-en une par réponse afin qu'elle puisse être analysée et votée.

Modifier : toutes les réponses permettent de résoudre le problème avec 4 conteneurs. Est-il possible de n'utiliser que le 2 initial?

Était-ce utile?

La solution

En supposant que vous disposiez de deux listes d’articles uniques et que le classement importe peu, vous pouvez les considérer comme des ensembles plutôt que comme des listes

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

Supprimez 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é.

Alors, parcourez A en cherchant chaque élément de B. Si vous le trouvez, supprimez-le de A et B

Alors A est une liste d'éléments supprimés et B une liste d'éléments ajoutés

Je pense ...

[modifier] Ok, avec le nouveau " seulement 2 conteneurs " restriction, la même chose est toujours valable: 

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

Ensuite, vous ne construisez pas une nouvelle liste, ni ne détruisez les anciennes ... mais cela prendra plus de temps que dans l'exemple précédent, vous pouvez simplement parcourir la liste la plus courte et supprimer les éléments de la plus longue. Ici, vous devez faire les deux listes

Je dirais que ma première solution n’utilisait pas 4 conteneurs, elle en détruisait deux ;-)

Autres conseils

Je n'ai pas fait cela depuis un moment, 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 entre la liste de droite et la liste de gauche, supprime contient les éléments supprimés et ajoute contient désormais de nouveaux éléments.

Ce que Joe a dit. Si les listes sont trop volumineuses pour tenir en mémoire, utilisez un utilitaire de tri de fichiers externe ou un tri Merge.

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, il est synchronisé. Si j’attends maintenant 10 jours, génère à nouveau les listes et les compare, 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 non trouvés sur le serveur B et / ou l'inverse. Que ce soit parce qu’un fichier a été ajouté au serveur A (le fichier n’est donc pas trouvé sur B) ou qu’un fichier a été supprimé sur le serveur B (le fichier n’est donc plus trouvé sur B ) est quelque chose que je ne peux pas déterminer simplement en ayant une liste de noms de fichiers.

Pour la solution que je suggère, je supposerai simplement 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 des listes ont été créées à des dates différentes).

De plus, je supposerai qu’il n’ya pas de doublons. Cela signifie que chaque élément de l'une ou l'autre liste est unique en ce sens: si je compare cet élément à n'importe quel 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 auquel je le compare, mais jamais égal. Par exemple. Lorsque je traite des chaînes, je peux les comparer lexicographiquement et la même chaîne ne figure jamais deux fois dans la liste.

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

  1. Triez les anciennes listes. 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, à condition qu'il existe déjà (ou pour déterminer rapidement, il n'existe pas du tout dans la liste). Si la liste n'est pas triée, la recherche de l'objet présente une complexité de O (n) (je dois examiner chaque élément de la liste). Si la liste est triée, la complexité n'est que de O (log n), car après chaque tentative de correspondance d'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, la recherche d'un élément (ou la détection du fait que l'élément ne figure pas dans la liste) prend au plus 7 tests (ou bien est-ce 8? Quoi qu'il en soit, beaucoup moins que 100). La nouvelle liste n'a pas besoin d'être triée.

  2. Nous procédons maintenant à l'élimination des listes. Pour chaque élément de la liste NEW, essayez de le trouver dans la liste OLD (en utilisant la recherche binaire). Si l'élément est trouvé, supprimez-le de la liste OLD et également , supprimez-le de la liste NEW. Cela signifie également que les listes deviennent plus petites au fur et à mesure que l'élimination progresse et que les recherches deviennent de plus en plus rapides. Étant donné que 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 à l'ancienne liste pendant la phase d'élimination.

  3. À la fin de l'élimination, les deux listes peuvent être vides, auquel cas elles sont é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). Il s'agit donc des éléments supprimés . Tous les éléments encore dans la liste NEW sont des éléments qui ne figuraient pas dans la liste OLD (là encore, nous les avions supprimés), il s’agit donc des éléments ajoutés .

Les objets de la liste "unique" sont-ils Dans ce cas, je construirais d’abord deux cartes (hashmaps), puis numériserais les listes et rechercherais chaque objet de la carte. 

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 l'horrible méta-langage mélangeant Ruby et Java :-P

À la fin, removeElements 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 de O (4 * N) car la recherche dans la carte / le dictionnaire peut être considérée comme constante. D'autre part, une recherche linéaire / binaire recherchant chaque élément dans les listes fera que O (N ^ 2).

MODIFIER : si vous déplacez la dernière vérification dans la deuxième boucle, vous pouvez supprimer 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)
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top