¿Cómo se implementa de manera eficiente el patrón de observador si el sujeto es un recipiente grande?

Question

Todos sabemos los href="http://en.wikipedia.org/wiki/Observer_pattern" : Tiene un sujeto que es capaz de notificar y actualizar una lista de observadores de sus cambios de estado. Supongamos ahora que el sujeto que desea observar es un contenedor, y que le gustaría observar el propio envase, es decir, además de elemento y la eliminación de elementos, y también los elementos contenidos, es decir, actualizaciones de estado de los elementos contenedores.

¿Cómo se implementa el mecanismo de actualización de modo que es rápido con respecto al elemento de inserción y supresiones al almacenar grandes cantidades de objetos en el contenedor? En particular,

• ¿verdad utilizar el mismo tipo de contenedor en la copia local de los observadores?
• ¿hay una opción inteligente del recipiente que los observadores deben usar? (Por ejemplo, ¿sería más rápido a, por ejemplo, usar siempre árboles equilibrados, incluso si usted está observando una lista enlazada?)
• ¿Cómo se traduce rápidamente en un iterador en el recipiente observada en un iterador en el recipiente del observador? (Trivial para las matrices, difícil para listas enlazadas?)

Si el contenedor es una lista enlazada por ejemplo, entonces se puede insertar elementos en tiempo constante. Si m observadores tienen que iterar a través de la lista que contiene n elementos, entonces la actualización toma O (n * m) que se espera el tiempo.

Si el contenedor es una matriz, a continuación, cambiar un elemento de toma constante de tiempo, y la actualización de m observadores toma O (m) si se pasa el índice del elemento, O (n * m) si los observadores tienen que recorrer a través de la matriz.

Si ayuda, considere los siguientes ejemplos:

Ejemplo 1. Usted está escribiendo un sistema operativo. El tema que le gustaría observar es el sistema de archivos y sus archivos. Sus puntos de vista son un explorador de archivos, un indexador, y otras aplicaciones. ¿Le gustaría actualizar los observadores cuando se añaden archivos, eliminar o modificar.

Ejemplo 2. Usted está escribiendo una aplicación de libreta de direcciones que debe ser capaz de manejar una ciudad del tamaño de Nueva York. El tema que le gustaría observar es el contenedor de sus registros (una persona con su dirección, números de teléfono, correo electrónico ...). Sus observadores son varios puntos de vista, lo que debería actualizar automáticamente al agregar, eliminar o modificar un registro. (Uno podría imagen una vista que contiene una lista de las personas que viven en la 53ª y otros puntos de dibujo en un mapa para cada persona de apellido Doe).

¿Cómo se maneja el caso de que se elimina un completo directorio o sub-árbol que "53rd St" se cambia a "Dijkstra St"?

Answer 1

De alguna manera, debe girar el recipiente en un sujeto.

El problema principal aquí es encontrar una forma eficaz de notar cambios. La mayoría de las veces cuando se encuentra con este problema, que es ya lo que desea observar no ofrece un mecanismo de notificación eficiente (probablemente debido a que el patrón de diseño observador no fue inventado cuando lo fue escrito ).

[EDIT] Puesto que usted pida una manera eficiente, la respuesta general es "depende". Los patrones de diseño no tienen un "todo lo que uno de talla única" solución. Son reglas generales cómo abordar un problema. ¿Cómo es necesario implementar las reglas en una situación específica es algo que a resolver cuando se está en la situación.

En general, si los observadores necesitan identificar pequeños cambios (es decir, un cambio de atributo o la adición de un elemento), el mensaje de notificación debe contener suficiente información que pueden hacer esto de manera eficiente. Así que si usted tiene una gran lista y un inserto, enviar la lista y el índice del elemento nuevo plus "como elemento insertado".

En cuanto a los cambios de atributos, hay dos soluciones. Una de ellas es añadir un observador para cada elemento de la lista. Esto puede ser lento y necesita una gran cantidad de memoria RAM, pero esto significa que usted puede agregar varios tipos en la misma lista.

Como alternativa, puede tener un "modificar elemento en la lista de servicios". Esto significa que está prohibido cambiar artículos directamente, debe utilizar siempre el servicio. El servicio puede entonces funcionar como sujeto y enviar notificaciones con el artículo, la edad y el valor cambiado y, posiblemente, con el índice en la lista.

[Edit2] La regla general es recoger la mayor cantidad de información sobre el cambio posible y pasar eso a los observadores. Pero realmente depende de su problema específico. Digamos que el observador está sentado en una máquina remota. En este caso, no hay manera eficiente para enviar toda la lista. Sólo se puede enviar "elemento X se insertó" y espero que eso es suficiente. Si el recipiente no tiene manera de notar cambios (por ejemplo, las nuevas páginas web en un sitio web), el contenedor tiene que atravesar todo el sitio una y otra vez para encontrar cambios que luego puede decir a los observadores de una manera eficiente.

Una vez más, los detalles dependen en realidad de la situación específica. Google lleva a cabo miles de arañas web que visitan millones de páginas web cada hora. Durante mucho tiempo, esto era "eficiente" (como en "el único camino"). Hace un tiempo, el protocolo "mapa del sitio" se implementó el cual permite a los administradores a su vez sus sitios web en los sujetos que pueden contar el observador Google acerca de los cambios.

Así que a menos que usted puede dar un ejemplo más específico de lo que tiene que hacer, no puedo dar una respuesta más concreta. Con los patrones de diseño, hay un punto en el que tiene que sentarse, tomar un problema real y encender el cerebro.

[Edit3] Aquí hay un par de ejemplos para usos del patrón de observador:

• Muchos marcos de interfaz de usuario utilizar este modelo para difundir eventos a los interesados. En Qt, que tiene un punto central donde todos los sujetos pueden registrar sus señales (notificaciones van a enviar observadores) y donde se puede unir a los sujetos. Esto significa que hay un solo lugar donde se gestionan todas las conexiones. La ventaja es que no es necesario añadir esta estructura de datos para cada objeto. Además, los objetos de (objetos no Qt) exterior pueden enviar y recibir mensajes. Ya que todo está en un solo lugar, esta estructura de datos se puede optimizar fácilmente. El inconveniente es que esta estructura puede llegar a ser muy grande, por lo que el envío de un mensaje tomará más tiempo cuando hay más partes involucradas (incluso los que son completamente ajenos).

• Google utiliza el protocolo de mapa de sitio para convertir los sitios web en los sujetos ya que es mucho más eficiente que atraviesa todo el sitio una y otra vez, incluso si sólo se solicita la última fecha de modificación de una cabeza URL (HTTP en lugar de HTTP GET ).

• Los sistemas de archivos en Windows y Linux notificaciones de ofertas para contar sobre aplicaciones nuevas o DELEarchivos de TED. El principal problema aquí es lo que debe suceder cuando los archivos cambian mientras que una aplicación no se ejecuta. Digamos que tienes una aplicación que mantiene las sumas de comprobación de archivos en un directorio. Obviamente, desea saber sobre los cambios cuando la aplicación se redujo, pero eso significaría que el servicio de notificación tendría que seguir la pista del último cambio que envió. Así que aquí, la aplicación tiene que leer todo el árbol durante el inicio para ver cualquier cosa que podría haber pasado por alto y tiene que utilizar el patrón de observador de los cambios que ocurren mientras se ejecuta.

• Un cliente de correo es un observador. Se le dirá al servidor de correo del ID del último correo electrónico que ha visto y el servidor le dirá que sobre ninguno nuevo.

• Cuando usted tiene un montón de cambios de atributos en un modelo complejo, por lo general es la única forma de centralizar todos los cambios (hacer que funcionan a través de un solo lugar) y adjuntar los observadores allí (en lugar de asociar N observadores a M individuo objetos). En esta implementación, los observadores pueden decir "Me interesa cualquier cambio en cualquier lugar" o "un cambio del campo X en cualquier materia" o "cualquier cambio de tema Y" (el último por lo general funciona como un "cambio de campo X en sujetos Y" -. el observador simplemente ignorar los cambios en los campos = X)

Answer 2

¿Por qué no patrón de observador en sí?

El sujeto tiene que informar al observador acerca de los eventos interesantes. A continuación, el observador deberá enviar a las partes interesadas (usuarios registrados).

La naturaleza del asunto no es de importancia aquí. (A menos que entendí su pregunta equivocada).