Wie setzen Sie effizient die Beobachter-Muster, wenn das Thema ein großer Behälter ist?

Question

Wir alle wissen, dass die Beobachter Muster : Sie haben ein Thema in der Lage ist zu benachrichtigen, und aktualisieren einer Liste der Beobachter seiner Zustandsänderungen. Nehmen wir nun an, dass das Thema, das Sie möchten ist ein Container beobachten, und Sie möchten, dass der Behälter selbst, das heißt Element Hinzufügen und Löschen von Elementen beobachten, und auch die darin enthaltenen Elemente, das heißt Zustand Updates der Containerelemente.

Wie werden Sie den Update-Mechanismus implementieren, so dass es in Bezug auf Elementeinführungs und Löschungen schnell ist, wenn Sie große Mengen von Objekten in Ihrem Container lagern? Insbesondere

• Möchten Sie die gleiche Art von Behälter in der lokalen Kopie der Beobachter verwenden?
• gibt es eine kluge Wahl des Behälters, der die Beobachter verwenden sollten? (Zum Beispiel wäre es schneller sein, sagen wir, immer ausgeglichene Bäume verwenden, auch wenn Sie eine verknüpfte Liste beobachten?)
• Wie übersetzen Sie schnell einen Iterator in den beobachteten Behälter in einen Iterator in den Behälter des Betrachters? (Trivial für Arrays, hart für verkettete Listen?)

Wenn Ihr Behälter eine verkettete Liste ist zum Beispiel, dann können Sie Elemente in konstanten Zeiteinsatz. Wenn m Beobachter durch die Liste zu durchlaufen haben n Elemente enthält, dann die Aktualisierung dauert O (n * m) erwartete Zeit.

Wenn Ihr Behälter ein Array ist, dann nimmt ein Element ändert konstante Zeit, und Beobachter m Aktualisierung dauert O (m), wenn Sie der Index des Elements übergeben, O (n * m), wenn Beobachter haben durch das Array zu durchlaufen.

Wenn es hilft, die folgenden Beispiele:

Beispiel 1. Sie schreiben ein Betriebssystem. Das Thema, das Sie möchten beobachten ist das Dateisystem und seine Dateien. Ihre Ansichten sind eine Datei-Explorer, ein Indexer und andere Anwendungen. Sie mögen die Beobachter aktualisieren, wenn Dateien hinzugefügt, gelöscht oder geändert werden.

Beispiel 2. Sie sind eine Adressbuch-Anwendung zu schreiben in der Lage sein sollte, eine Stadt der Größe von New York zu behandeln. Das Thema, das Sie möchten beobachten ist der Behälter Ihrer Aufzeichnungen (eine Person mit seiner Adresse, Telefonnummern, E-Mail ...). Ihre Beobachter sind mehrere Ansichten, die automatisch sollte aktualisiert werden, wenn Sie hinzufügen, löschen oder einen Datensatz ändern. (Man könnte Bild eine Ansicht, welche eine Liste von Personen enthalten, die auf der 53. leben und eine andere Zeichnung Punkte auf einer Karte für jede Person, deren Nachname ist Doe).

Wie beurteilen Sie den Fall behandeln, die eine vollständige Verzeichnis-Unterstruktur gelöscht wird oder, dass „53rd St“ wird umbenannt in „Dijkstra St“?

Answer 1

Irgendwie müssen Sie den Behälter in ein Thema drehen.

Das Hauptproblem hier ist eine effiziente Art und Weise zu bemerken Veränderungen zu finden. Die meiste Zeit, wenn Sie in dieses Problem, es ist weil das, was Sie beobachten wollen nicht einen effizienten Benachrichtigungsmechanismus (wahrscheinlich anbieten, weil das Beobachter-Entwurfsmuster nicht erfunden wurde, als sie, was geschrieben wurde, ).

[EDIT] Sie sind für eine effiziente Art und Weise fragen, die allgemeine Antwort ist „es kommt“. Design-Muster haben keine "one-size-fits-all" -Lösung. Sie sind allgemeine Regeln, wie ein Problem zu nähern. Wie müssen Sie die Regeln in einer bestimmten Situation zu implementieren, ist etwas, das Sie lösen, wenn Sie in der Lage sind.

Im Allgemeinen, wenn Ihre Beobachter kleine Veränderungen identifizieren müssen (das heißt ein Attribut ändern oder das Hinzufügen eines Elements), sollte die Benachrichtigung genügend Informationen enthalten, dass sie dies effizient tun. Also, wenn Sie eine große Liste und einen Einsatz haben, senden Sie die Liste und den Index des neuen Elements plus „Artikel wie eingefügt“.

Wie bei Attributänderungen gibt es zwei Lösungen. Eine davon ist ein Beobachter auf jedes Element in der Liste hinzuzufügen. Dies kann langsam sein und viel RAM benötigen, aber es bedeutet, dass Sie verschiedene Arten in der gleichen Liste hinzufügen können.

Alternativ können Sie auch ein „ändern Element in der Liste Dienst“. Das bedeutet, dass es verboten Gegenstände direkt zu ändern, müssen Sie immer den Service nutzen. Der Dienst kann dann als Thema arbeitet und sendet Benachrichtigungen mit dem Punkt, den alten und die geändertenen Wert und möglicherweise mit dem Index in der Liste.

[EDIT 2] Die allgemeine Regel ist, so viele Informationen über die Änderung wie möglich zu sammeln und die Beobachter übergeben. Aber es hängt wirklich von Ihrem spezifischen Problem. Lassen Sie uns sagen, dass der Beobachter auf einem entfernten Rechner sitzt. In diesem Fall gibt es keine effiziente Art und Weise sie die gesamte Liste zu senden. Sie können es nur senden „Element X wurde eingefügt“ und hofft, das ist genug. Wenn der Behälter keine Möglichkeit zu bemerken Veränderungen hat (zum Beispiel neue Web-Seiten auf einer Website), hat der Behälter die ganze Seite immer wieder zu durchlaufen Veränderungen zu finden, die es dann die Beobachter auf effiziente Art und Weise erzählen.

Auch hier wirklich die Details von der jeweiligen Situation ab. Google läuft tausend von Web-Spider, die Millionen von Webseiten pro Stunde besuchen. Für eine lange Zeit war dies „effizient“ (wie in „dem einzigen Weg“). Vor einiger Zeit das „Sitemap“ Protokoll wurde implementiert, die Administratoren ihre Websites in Themen drehen kann, die die Google-Beobachter über Änderungen berichten.

Also, wenn Sie ein konkretes Beispiel geben können, was Sie tun müssen, kann ich nicht geben Sie eine bestimmte Antwort. Mit Design-Muster gibt es einen Punkt, wo man sich hinsetzen müssen, ein echtes Problem nehmen und schalten Sie Ihr Gehirn.

[EDIT3] Hier sind ein paar Beispiele für die Verwendungen der Beobachter-Muster:

• Viele UI-Frameworks verwenden dieses Muster Ereignisse an Interessenten zu verbreiten. In Qt haben Sie einen zentralen Ort, an dem alle Fächer ihre Signale registrieren können (Benachrichtigungen werden sie senden) und dem Beobachter an Patienten anbringen. Das heißt, es ist eine einzige Stelle, wo alle Verbindungen verwaltet werden. Der Vorteil ist, dass Sie diese Datenstruktur nicht zu jedem Objekt hinzufügen müssen. Auch Objekte von außen (nicht-Qt-Objekten) können Nachrichten senden und empfangen. Da alles an einem Ort ist, kann diese Datenstruktur leicht optimiert werden. Der Nachteil ist, dass diese Struktur sehr groß werden kann, so dass eine Nachricht senden, wird mehr Zeit in Anspruch nehmen, wenn es mehr Parteien beteiligt (auch solche, die völlig unabhängig sind).

• Google verwendet das Sitemap-Protokoll Web-Sites in Themen zu drehen, da das ist viel effizienter als die ganze Seite immer wieder durchlaufen, auch wenn Sie nur den Zeitpunkt der letzten Änderung einer URL (HTTP HEAD anstelle von HTTP-GET-Anfrage ).

• Dateisysteme unter Windows und Linux bieten Benachrichtigungen Anwendungen über neue zu erzählen oder deleted-Dateien. Das Hauptproblem hier ist, was passieren soll, wenn Dateien ändern, während eine Anwendung nicht ausgeführt. Sagen Sie eine App haben, die Prüfsummen von Dateien in einem Verzeichnis unterhält. Offensichtlich möchten Sie über Änderungen wissen, wann die App war nach unten, aber das würde bedeuten, der Benachrichtigungsdienst müßte Spur der letzten Änderung hält es gesendet. Also hier hat der App den ganzen Baum in beim Start zu lesen, etwas zu sehen, daß es vielleicht verpaßt hat, und es muss die Beobachter-Muster für Änderungen verwenden, geschehen, während es ausgeführt wird.

• Ein Mail-Client ist ein Beobachter. Es wird der Mailserver die ID der letzten E-Mail sagen, es gesehen hat, und der Server wird es über alle neuen erzählen.

• Wenn Sie viele Attributänderungen in einem komplexen Modell haben, ist es in der Regel die einzige Möglichkeit, um alle Änderungen zu zentralisieren (sie durch einen einzigen Ort laufen zu lassen) und die Beobachter dort befestigen (statt N Beobachter M Einzel des Anbringens Objekte). In dieser Implementierung können die Beobachter sagen: „Ich habe Interesse an einer Änderung überall“ oder „eine Änderung des Feld X in einem beliebigen Fach“ oder „jede Änderung Thema Y“ (die letzten verdoppelt in der Regel als „Feldänderung X in Thema Y“-. Beobachter einfach Änderungen an Feldern ignorieren = X)

Answer 2

Warum nicht Beobachter Muster selbst?

Das Thema muss den Betrachter über die interessanten Ereignisse informieren. Dann wird der Beobachter entsenden es an Interessenten (Abonnenten).

Die Natur des Themas ist nicht von Bedeutung hier. (Es sei denn, ich verstand Ihre Frage falsch).