Comment pouvez-vous mettre en œuvre efficacement le modèle d'observateur si le sujet est un énorme conteneur?

Question

Nous savons tous que les : Vous avez un sujet qui est en mesure d'informer et mettre à jour une liste des observateurs de ses changements d'état. Maintenant, supposons que le sujet que vous souhaitez observer est un récipient, et vous souhaitez observer le conteneur lui-même, à savoir plus d'éléments et la suppression d'éléments, ainsi que les éléments contenus, à savoir les mises à jour d'état des éléments conteneurs.

Comment qualifieriez-vous mettre en œuvre le mécanisme de mise à jour de sorte qu'il est rapide par rapport à l'insertion des éléments et des suppressions lorsque vous stockez des quantités massives d'objets dans votre réservoir? En particulier,

• voulez-vous utiliser le même type de conteneur dans la copie locale des observateurs?
• est-il un choix judicieux de conteneurs que les observateurs devraient utiliser? (Par exemple, serait-il plus rapide, disons, utilisez toujours des arbres équilibrés, même si vous observez une liste chaînée?)
• comment voulez-vous traduire rapidement un itérateur dans le récipient observée dans un itérateur dans le récipient de l'observateur? (Trivial pour les tableaux, dur pour les listes chaînées?)

Si votre conteneur est une liste chaînée par exemple, vous pouvez insérer des éléments en temps constant. Si m observateurs doivent parcourir la liste contenant n éléments, puis la mise à jour prend O (n * m) le temps prévu.

Si votre conteneur est un tableau, puis en changeant un élément prend du temps constant et la mise à jour m observateurs prend O (m) si vous passez l'index de l'élément, O (n * m) si les observateurs doivent parcourir le tableau.

Si elle aide, prendre en compte les exemples suivants:

Exemple 1. Vous écrivez un système d'exploitation. Le sujet que vous souhaitez observer est le système de fichiers et ses fichiers. Votre opinion est un explorateur de fichiers, un indexeur et d'autres applications. Vous souhaitez mettre à jour les observateurs lorsque les fichiers sont ajoutés, supprimés ou modifiés.

Exemple 2. Vous écrivez une application de carnet d'adresses qui devrait être capable de gérer une ville de la taille de New York. Le sujet que vous souhaitez observer est le conteneur de vos dossiers (une personne avec son adresse, les numéros de téléphone, e-mail ...). Vos observateurs sont plusieurs points de vue, ce qui devrait mettre à jour automatiquement lorsque vous ajoutez, supprimez ou modifiez un enregistrement. (On pourrait l'image d'une vue contenant une liste de personnes qui vivent sur 53e et un autre des points de dessin sur une carte pour chaque personne dont le nom est Doe).

Comment gérez-vous le cas où un répertoire complet-sous-arbre est supprimé ou que « 53rd St » est renommé « Dijkstra St »?

Answer 1

D'une certaine façon, vous devez tourner le récipient dans un sujet.

Le principal problème est de trouver un moyen efficace de remarquer des changements. La plupart du temps lorsque vous rencontrez ce problème, il est parce que la chose que vous voulez observer n'offre pas un mécanisme de notification efficace (probablement parce que le modèle de conception d'observateur n'a pas été inventé quand ils chose a été écrit ).

[EDIT] Puisque vous demandez une manière efficace, la réponse générale est « ça dépend ». Les modèles de conception ne sont pas une solution "one-size-fits-all". Ce sont des règles générales la façon d'aborder un problème. Comment vous avez besoin de mettre en œuvre les règles dans une situation spécifique est quelque chose que vous résoudre quand vous êtes dans la situation.

En général, si vos observateurs doivent identifier les petits changements (à savoir un changement d'attribut ou l'ajout d'un élément), le message de notification doit contenir suffisamment d'informations qu'ils peuvent le faire efficacement. Donc, si vous avez une grande liste et un insert, envoyez la liste et l'index du nouvel élément plus « élément comme inséré ».

En ce qui concerne les changements d'attributs, il y a deux solutions. L'un est d'ajouter un observateur à chaque élément de la liste. Cela peut être lent et besoin de beaucoup de RAM, mais cela signifie que vous pouvez ajouter plusieurs types dans la même liste.

Vous pouvez avoir un « modifier l'article dans le service de liste ». Cela signifie qu'il est interdit de modifier les articles directement, vous devez toujours utiliser le service. Le service peut alors fonctionner comme un sujet et envoyer des notifications de l'article, la valeur ancienne et a changé et peut-être avec l'index dans la liste.

[EDIT2] La règle générale est de recueillir autant d'informations sur le changement possible et de transmettre cela aux observateurs. Mais cela dépend vraiment de votre problème. Disons que l'observateur est assis sur une machine distante. Dans ce cas, il n'y a aucun moyen efficace pour envoyer toute la liste. Vous ne pouvez l'envoyer « article X a été inséré » et nous espérons que ça suffit. Si le conteneur n'a aucun moyen de remarquer des changements (par exemple, de nouvelles pages Web sur un site Web), le conteneur doit traverser tout le site encore et encore pour trouver des changements qu'il peut ensuite dire aux observateurs d'une manière efficace.

Encore une fois, les détails dépendent vraiment de la situation spécifique. Google va milliers d'araignées web qui visitent des millions de pages web toutes les heures. Pendant longtemps, ce fut « efficace » (comme dans « la seule façon »). Il y a quelque temps, le protocole « plan du site » a été mis en œuvre qui permet aux administrateurs de transformer leurs sites Web des sujets qui peuvent dire l'observateur Google sur les changements.

Donc, sauf si vous pouvez donner un exemple plus précis ce que vous devez faire, je ne peux pas vous donner une réponse plus précise. Avec des modèles de conception, il y a un point où vous devez vous asseoir, prendre un vrai problème et allumez votre cerveau.

[EDIT3] Voici quelques exemples pour des utilisations du modèle d'observateur:

• De nombreux cadres de l'interface utilisateur utilisent ce modèle pour diffuser des événements aux parties intéressées. Dans Qt, vous avez un endroit central où tous les sujets peuvent enregistrer leurs signaux (ils envoient des notifications) et où les observateurs peuvent attacher à des sujets. Cela signifie qu'il ya un seul endroit où toutes les connexions sont gérées. L'avantage est que vous n'avez pas besoin d'ajouter cette structure de données à chaque objet. De plus, les objets provenant de l'extérieur (objets non-Qt) peuvent envoyer et recevoir des messages. Puisque tout est en un seul endroit, cette structure de données peut être optimisé facilement. L'inconvénient est que cette structure peut devenir très grand, donc envoyer un message prendra plus de temps quand il y a plus de parties concernées (même celles qui sont sans aucun rapport).

• Google utilise le protocole sitemap pour transformer les sites web des sujets puisque c'est beaucoup plus efficace que traverser encore et encore tout le site, même si vous demandez que la date de dernière modification d'une URL (HTTP HEAD au lieu de HTTP GET ).

• dans les notifications de systèmes de fichiers Windows et Linux offre à indiquent aux applications nouvelles ou delefichiers. ted Le principal problème est ici ce qui devrait se produire lorsque les fichiers changent alors qu'une application ne fonctionne pas. Disons que vous avez une application qui maintient de contrôle des fichiers dans un répertoire. De toute évidence, vous souhaitez connaître les changements lorsque l'application est en baisse mais cela signifierait le service de notification devrait garder une trace de la dernière modification qu'il a envoyé. Voici donc, l'application doit lire tout l'arbre dans au démarrage pour voir tout ce qu'il aurait pu manquer et il a besoin d'utiliser le modèle d'observation des changements qui se produisent pendant son exécution.

• Un client de messagerie est un observateur. Il indique au serveur de messagerie de l'ID du dernier e-mail qu'il a vu et le serveur lui dire au sujet de nouveaux.

• Quand vous avez beaucoup de changements d'attributs dans un modèle complexe, il est généralement le seul moyen de centraliser tous les changements (faire courir à travers un seul endroit) et fixer les observateurs là-bas (au lieu de fixer des observateurs N à M individuelle objets). Dans cette mise en œuvre, les observateurs peuvent dire: « Je suis intéressé par tout changement partout » ou « un changement du champ X dans un sujet » ou « tout changement dans le thème Y » (le dernier double habituellement comme un « changement de champ X dans le thème Y » -. l'observateur sera tout simplement ignorer les changements aux champs = X)

Answer 2

Pourquoi ne pas modèle d'observateur lui-même?

Le sujet doit informer l'observateur des événements intéressants. Ensuite, l'observateur doit l'expédier aux parties intéressées (abonnés).

La nature du sujet est d'une importance ici. (À moins d'avoir compris votre question mal).