28 votes

Quel est l'algorithme standard pour la synchronisation de deux listes d'objets liés?

Je suis sûr que ce doit être dans une sorte de livre de texte (ou, plus probablement, dans chacun d'eux), mais il me semble être en utilisant le mauvais mots-clés à la recherche pour elle... :(

Une tâche récurrente que je suis confronté au moment de la programmation, c'est que j'ai affaire à des listes d'objets à partir de différentes sources dont j'ai besoin pour conserver la synchronisation en quelque sorte. Généralement, il y a une sorte de "liste principale" par exemple retourné par certaines API externe, puis une liste des objets que j'ai créer moi-même dont chacune correspond à un objet dans la liste de référence (pensez à "wrappers" ou "adaptateurs" - ils contiennent généralement des informations étendues sur les objets externes spécifiques à ma demande et/ou de simplifier l'accès aux objets externes).

Dur les caractéristiques de toutes les instances du problème:

  • la mise en œuvre de la liste principale est caché de moi; son interface est fixe
  • les éléments dans les deux listes ne sont pas compatible avec l'assignation
  • J'ai le plein contrôle sur la mise en œuvre de la liste d'esclave
  • Je ne peux pas contrôler l'ordre des éléments dans la liste de référence (c'est à dire qu'il n'est pas sortable)
  • la liste de référence ne soit pas fournir la notification ajouté ou supprimé des éléments du tout ou la notification n'est pas fiable, c'est à dire la synchronisation ne peut se faire que sur demande, de ne pas vivre
  • simplement de compensation et de la reconstruction de la liste d'esclave à partir de zéro à chaque fois que c'est nécessaire n'est pas une option:
    • l'initialisation de l'emballage des objets doit être considéré comme cher
    • d'autres objets contiennent des références à la wrappers

Caractéristiques supplémentaires dans certains cas de problème:

  • les éléments dans la liste de référence ne peut être identifié par la lecture de leurs propriétés plutôt que d'accéder directement à l'indice ou de la mémoire d'adresse:
    • après un rafraîchissement, de la liste de référence peut retourner un tout nouvel ensemble d'instances, même si elles représentent la même information
    • la seule interface pour accéder à des éléments dans la liste de référence peut être un séquentielle énumérateur
  • la plupart du temps, l'ordre des éléments dans la liste de référence est stable, c'est à dire de nouveaux éléments sont toujours ajouté au début ou à la fin, jamais dans le milieu; cependant, la suppression peut généralement se produire à n'importe quelle position

Alors, comment aurais-je généralement remédier à cette situation? Quel est le nom de l'algorithme, je devrais google pour?

Dans le passé, j'ai mis en œuvre de diverses façons (voir ci-dessous pour un exemple), mais il se sentait toujours comme il devrait être plus propre et plus efficace, en particulier une qui n'a pas besoin de deux itérations (un sur chaque liste).

Voici un exemple d'approche:

  1. Itérer sur la liste principale
  2. Examinez chaque élément dans la "liste d'esclave"
  3. Ajouter des éléments qui n'existent pas encore
  4. D'une certaine manière à garder une trace des éléments qui existent déjà dans les deux listes (par exemple par marquage ou de les garder encore une autre liste)
  5. Quand c'est fait, itérer sur la liste d'esclave et de supprimer tous les objets qui n'ont pas été marqués (voir 4.) claire et l'étiquette de tous les autres

Mise à jour 1 Merci à tous pour vos réponses! J'ai besoin d'un certain temps de regarder les liens.
[...] (texte déplacé au corps principal de la question)

Mise à jour 2 Restructered le moyen-paragraphe dans un (espérons-le) plus facilement parseable les listes à puces et intégré détails ajoutés plus tard dans la première mise à jour.

4voto

MSalters Points 74024

Les 2 solutions typiques sont: 1. Copie de la liste de référence à la liste de synchronisation. 2. Faire un O(N*N), de la comparaison entre tous les éléments des paires.

Vous avez exclu la smart options déjà: identité partagée, de tri et de notifications de changement.

Notez qu'il n'est pas pertinent de savoir si les listes peuvent être triées dans un significatif façon, ou même complètement. Par exemple, lorsque l'on compare les deux listes de chaînes, il serait idéal pour trier par ordre alphabétique. Mais la liste de comparaison serait encore plus efficace si vous souhaitez trier les listes par la chaîne de caractères de longueur! Si vous souhaitez toujours avoir pour objectif de faire une comparaison par paires de chaînes de même longueur, mais qui sera probablement un beaucoup plus petit nummber de paires.

3voto

Andrew Points 1187

Cela ressemble à l'ensemble de la réconciliation problème c'est à dire le problème de la synchronisation des données. Une question sur DONC été demandé à la ce: la mise en Œuvre de l'ensemble de la réconciliation de l'algorithme.

La plupart des références sur google sont à la technique du papier résumés.

2voto

RnR Points 1268

Souvent, la meilleure solution à ces problèmes est de ne pas résoudre directement.

SI vraiment vous ne pouvez pas utiliser un classement binaire consultable conteneur dans votre partie du code (comme un ensemble ou même un vecteur trié) puis...

Vous êtes très lié à la mémoire? Si non, alors que je venais de créer un dictionnaire (un std::set par exemple) contenant le contenu de l'une des listes et ensuite il suffit de faire une itération sur l'autre, je veux o synchronisation avec la première.

De cette façon, vous êtes en train de faire n*logn pour créer le dictionnaire (ou n*X pour une valeur de hachage dictionnaire en fonction de ce qui sera plus efficace) + m*logn opérations pour aller sur la deuxième liste et de le synchroniser (ou juste de la M*Y) - difficile à battre si vous avez vraiment utiliser les listes en premier lieu - il est également bon de vous le faire une seule fois et si vous en avez besoin et c'est beaucoup mieux que de garder les listes triées tout le temps qui serait une n^2 tâche pour chacun d'eux.

1voto

paxos1977 Points 25088

Dans le C++ STL l'algorithme est appelé set_union. Aussi, la mise en œuvre de l'algorithme est susceptible d'être beaucoup plus simple si vous ne le syndicat dans une 3ème liste.

1voto

Eric Nguyen Points 18126

Il ressemble à un homme nommé Michael Heyeck a une bonne, O(n), solution à ce problème. Découvrez ce billet de blog pour une explication et un peu de code.

Essentiellement, la solution de pistes à la fois le maître et l'esclave des listes en un seul passage, le suivi des indices dans chaque. Deux structures de données sont ensuite gérés: une liste d'insertions d'être relus sur la liste d'esclave, et une liste de suppressions.

Il semble simple et a aussi l'avantage de produire une preuve de minimalisme, qui Heyeck qui a été suivi d'un post ultérieur. L'extrait de code dans ce post, il est plus compact, ainsi:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x < len(a)) or (y < len(b)):
    if y >= len(b): d.append(x); x += 1
    elif x >= len(a): i.append((y, b[y])); y += 1
    elif a[x] < b[y]: d.append(x); x += 1
    elif a[x] > b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)

Encore une fois, de crédit à Michael Heyeck.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X