Como você implementar de forma eficiente o padrão de observador se o sujeito é um enorme recipiente?

Question

Nós todos sabemos que o observador padrão : Você tem um assunto que é capaz de notificar e atualizar a lista de observadores de suas alterações de estado. Agora, suponha que o assunto que você gostaria de observar é um recipiente, e você gostaria de observar o próprio recipiente, ou seja, elemento de adição e eliminação de elementos, e também os elementos contidos, ou seja, atualizações de estado dos elementos do recipiente.

Como você poderia implementar o mecanismo de atualização de modo que ele é rápido em relação ao elemento de inserção e eliminações quando você armazenar grandes quantidades de objetos em seu recipiente? Em particular,

• você usaria o mesmo tipo de recipiente na cópia local dos observadores?
• Existe uma escolha inteligente do recipiente que os observadores devem usar? (Por exemplo, seria mais rápido para, digamos, use sempre árvores equilibrado, mesmo se você está observando uma lista ligada?)
• como você rapidamente traduzir um iterador para o recipiente observado em um iterador para o recipiente do observador? (Trivial para arrays, difícil para listas ligadas?)

Se o seu recipiente é uma lista ligada, por exemplo, então você pode inserir elementos em tempo constante. Se m observadores têm de percorrer a lista contendo n elementos, então a atualização leva O (n * m) tempo esperado.

Se o recipiente for uma matriz, em seguida, alterando um elemento leva tempo constante e atualização m observadores leva O (m) se você passar o índice do elemento, O (n * m) se os observadores têm de percorrer a matriz.

Se ajudar, considere os seguintes exemplos:

Exemplo 1. Você está escrevendo um sistema operacional. O assunto que você gostaria de observar é o sistema de arquivos e seus arquivos. A sua opinião é um explorador de arquivos, um indexador, e outras aplicações. Você gostaria de atualizar os observadores quando os arquivos são adicionados, eliminados ou modificados.

Exemplo 2. Você está escrevendo um aplicativo livro de endereços que deve ser capaz de lidar com uma cidade do tamanho de Nova York. O assunto que você gostaria de observar é o recipiente de seus registros (uma pessoa com seu endereço, números de telefone, e-mail ...). Seus observadores vários pontos de vista, que deve atualizar automaticamente quando você adicionar, excluir ou modificar um registro. (Pode-se uma imagem vista contendo uma lista de pessoas que vivem com 53 e outro desenho pontos em um mapa para cada pessoa cujo sobrenome é Silva).

Como você lida com o caso em que um diretório de sub completa é excluída ou que "53rd St" é renomeado para "Dijkstra St"?

Answer 1

De alguma forma, você deve rodar o recipiente em um assunto.

O principal problema aqui é encontrar uma maneira eficiente de mudanças Aviso. Na maioria das vezes quando você executar para esse problema, é , porque a coisa que você deseja observar não oferece um mecanismo de notificação eficientes (provavelmente porque o padrão de design do observador não foi inventada quando coisa foi escrito ).

[EDIT] Desde que você pedir uma maneira eficiente, a resposta geral é "depende". padrões de projeto não tem um "one-size-fits-all" solução. Eles são regras gerais como abordar um problema. Como você precisa para implementar as regras em uma situação específica é algo que você resolver quando você está na situação.

Geralmente, se seus observadores precisa identificar pequenas alterações (isto é, uma mudança atributo ou adicionar um elemento), a mensagem de notificação deve conter informações suficientes para que eles podem fazer isso de forma eficiente. Então se você tem uma lista grande e uma inserção, enviar a lista e o índice do novo elemento plus "item como inserida".

Quanto a alterações de atributo, há duas soluções. Um deles é para adicionar um observador para cada elemento da lista. Isso pode ser lento e precisa de muita RAM, mas isso significa que você pode adicionar vários tipos na mesma lista.

Como alternativa, você pode ter um "item Modificar no serviço de lista". Isto significa que é proibido itens alteram diretamente, você deve sempre usar o serviço. O serviço pode então trabalhar como um assunto e enviar notificações com o item, o valor antigo e alterado e, possivelmente, com o índice na lista.

[EDIT2] A regra geral é coletar o máximo de informações sobre a mudança possível e passar isso para os observadores. Mas isso realmente depende do seu problema específico. Vamos dizer que o observador está sentado em uma máquina remota. Neste caso, não há nenhuma maneira eficiente para enviar toda a lista. Você só pode enviá-lo "inciso X foi inserido" e espero que isso seja suficiente. Se o recipiente não tem como mudanças observação (por exemplo, novas páginas da web em um site), o recipiente tem de percorrer todo o site novamente e novamente para encontrar alterações que pode, então, dizer aos observadores de uma maneira eficiente.

Mais uma vez, os detalhes realmente depender da situação específica. Google é executado milhares de aranhas que visitam milhões de páginas web a cada hora. Durante muito tempo, esta foi "eficiente" (como em "o único caminho"). Um tempo atrás, o protocolo "Mapa do Site" foi implementado que permite que os administradores para transformar seus sites em assuntos que podem dizer o observador Google sobre as alterações.

Então, se você pode dar um exemplo mais específico o que você precisa fazer, eu não posso lhe dar uma resposta mais específica. Com padrões de projeto, há um ponto em que você precisa para se sentar, tomar um problema real e ligar o cérebro.

[EDIT3] Aqui estão alguns exemplos de usos do observador padrão:

• Muitos frameworks de UI usar este padrão para eventos espalhou para partes interessadas. Em Qt, você tem um ponto central onde todos os assuntos podem registrar seus sinais (notificações eles vão enviar) e onde os observadores pode anexar a indivíduos. Isto significa que há um único lugar onde todas as conexões são geridos. A vantagem é que você não precisa adicionar este estrutura de dados para cada objeto. Além disso, objetos de fora (não-Qt objetos) pode enviar e receber mensagens. Uma vez que tudo está em um único lugar, esta estrutura de dados pode ser otimizado facilmente. A desvantagem é que esta estrutura pode se tornar muito grande, então o envio de uma mensagem irá levar mais tempo quando há mais partes envolvidas (mesmo aqueles que são completamente alheios).

• O Google usa o protocolo Sitemap para transformar sites em disciplinas já que é muito mais eficiente do que atravessar todo o site novamente e novamente, mesmo se você só solicitar a última modificação de um URL (HTTP cabeça em vez de HTTP GET ).

• Os sistemas de arquivos em Windows e Linux oferecem notificações para contar aplicações sobre novo ou DELEarquivos ted. O principal problema aqui é o que deve acontecer quando os arquivos alterar enquanto um aplicativo não é executado. Digamos que você tenha um aplicativo que mantém somas de verificação de arquivos em um diretório. Obviamente, você gostaria de saber sobre as mudanças quando o aplicativo foi para baixo, mas isso significaria que o serviço de notificação teria que acompanhar a última alteração que enviou. Então, aqui, o aplicativo tem que ler toda a árvore em no arranque para ver qualquer coisa que poderia ter perdido e precisa usar o observador padrão para mudanças acontecendo enquanto ele é executado.

• Um cliente de email é um observador. Vai dizer o servidor de correio a identificação do último e-mail que tem visto e o servidor irá dizer-lhe sobre quaisquer novos.

• Quando você tem muitas mudanças de atributos em um modelo complexo, é geralmente a única forma de centralizar todas as alterações (fazê-los funcionar através de um único lugar) e anexar os observadores lá (em vez de anexar observadores N para M indivíduo objetos). Nesta implementação, os observadores podem dizer: "Eu estou interessado em qualquer lugar mudança" ou "uma mudança do campo X em qualquer assunto" ou "qualquer mudança de assunto Y" (o último normalmente funciona como uma "mudança de campo X no assunto Y" - o observador irá simplesmente ignorar alterações nos campos = X)

!.

Answer 2

Por que não observador padrão em si?

O assunto precisa informar o observador sobre os eventos interessantes. Em seguida, o observador deve despachar-lo para as partes interessadas (assinantes).

A natureza do assunto não é de qualquer significado aqui. (A menos que eu entendi a sua pergunta errada).