Come è possibile realizzare in modo efficiente il pattern Observer, se il soggetto è un enorme contenitore?

Question

Sappiamo tutti gli href="http://en.wikipedia.org/wiki/Observer_pattern" modello : Si dispone di un soggetto che è in grado di comunicare e aggiornare l'elenco degli osservatori dei suoi cambiamenti di stato. Supponiamo ora che il soggetto che si desidera osservare è un contenitore, e si desidera osservare il contenitore stesso, vale a dire elemento aggiunta e la cancellazione di elementi, e anche gli elementi contenuti, vale a dire gli aggiornamenti di stato degli elementi contenitori.

In che modo si implementa il meccanismo di aggiornamento in modo che sia veloce rispetto all'inserimento ed eliminazioni elemento quando si memorizzano grandi quantità di oggetti nel contenitore? In particolare,

• farebbe si utilizza lo stesso tipo di contenitore nella copia locale degli osservatori?
• c'è una scelta intelligente di contenitore che gli osservatori dovrebbero usare? (Per esempio, sarebbe più veloce, per esempio, utilizzare sempre gli alberi bilanciati, anche se si sta osservando una lista concatenata?)
• come si fa a tradurre rapidamente un iteratore nel contenitore osservata in un iteratore nel contenitore dell'osservatore? (Trivial per gli array, difficile per le liste collegate?)

Se il contenitore è una lista collegata per esempio, allora è possibile inserire elementi in tempo costante. Se m osservatori devono scorrere l'elenco contenente n elementi, quindi l'aggiornamento prende O (n * m) previsto tempo.

Se il contenitore è un array, quindi la modifica di un elemento richiede tempo costante, e l'aggiornamento m osservatori prende O (m) se si passa l'indice dell'elemento, O (n * m) se gli osservatori devono scorrere la matrice.

Se aiuta, prendere in considerazione i seguenti esempi:

Esempio 1. Si sta scrivendo un sistema operativo. Il soggetto che si desidera osservare è il filesystem ei relativi file. Le vostre opinioni sono un esploratore di file, un indicizzatore, e altre applicazioni. Desiderate aggiornare gli osservatori quando vengono aggiunti, cancellati o modificati file.

Esempio 2. Si sta scrivendo un'applicazione rubrica che dovrebbe essere in grado di gestire una città delle dimensioni di New York. Il soggetto che si desidera osservare è il contenitore dei tuoi record (una persona con il suo indirizzo, numeri di telefono, e-mail ...). I suoi osservatori sono diverse viste, che dovrebbe aggiornare automaticamente quando si aggiungere, eliminare o modificare un record. (Si potrebbe immagine una vista contenente un elenco di persone che vivono sul 53 ° e un altro disegno puntini su una mappa per ogni persona il cui cognome è Doe).

Come si fa a gestire il caso che una completa directory sottostruttura viene eliminato o che "53rd St" viene rinominato in "Dijkstra St"?

Answer 1

In qualche modo, è necessario attivare il contenitore in un soggetto.

Il problema principale è quello di trovare un modo efficace per notare cambiamenti. La maggior parte del tempo in cui si esegue in questo problema, è perché la cosa che si desidera osservare non offre un meccanismo di notifica efficiente (probabilmente perché il modello di progettazione osservatore non è stato inventato quando cosa è stato scritto ).

[EDIT] Dal momento che si chiede un modo efficiente, la risposta generale è "dipende". I design pattern non hanno un "-one-size-fits" soluzione. Sono regole generali come affrontare un problema. Come è necessario implementare le regole in una situazione specifica è una cosa che si risolve quando si è nella situazione.

In generale, se i vostri osservatori devono identificare piccoli cambiamenti (cioè un cambiamento di attributo o l'aggiunta di un elemento), il messaggio di notifica deve contenere informazioni sufficienti che si può fare questo in modo efficace. Quindi, se avete una grande lista e un inserto, inviare la lista e l'indice del nuovo elemento plus "voce come sono stati inseriti".

Come per modifiche di attributo, ci sono due soluzioni. Uno è quello di aggiungere un osservatore ad ogni elemento della lista. Questo può essere lento e hanno bisogno di un sacco di RAM, ma significa che è possibile aggiungere diversi tipi nella stessa lista.

In alternativa, si può avere una "voce di modificare in servizio lista". Ciò significa che è proibito modificare direttamente gli elementi, si deve sempre utilizzare il servizio. Il servizio può quindi funzionare come un soggetto e inviare notifiche con la voce, il valore storico e cambiato e, eventualmente, con l'indice nella lista.

[EDIT2] La regola generale è quello di raccogliere quante più informazioni circa il cambiamento possibile e passare che agli osservatori. Ma in realtà dipende il vostro problema specifico. Diciamo che l'osservatore è seduto su una macchina remota. In questo caso, non c'è modo efficace per inviarlo l'intera lista. È possibile inviare solo "punto X è stato inserito" e sperare che sia abbastanza. Se il contenitore non ha modo di notare cambiamenti (ad esempio, nuove pagine web su un sito web), il contenitore deve percorrere ancora e ancora l'intero sito per trovare le modifiche che si può poi dire gli osservatori in modo efficiente.

Anche in questo caso, i dettagli in realtà dipendono dalla situazione specifica. Google gestisce migliaia di ragni web che visitate dai milioni di pagine web ogni ora. Per lungo tempo, questo era "efficiente" (come in "l'unica via"). Qualche tempo fa, il protocollo "sitemap" è stato implementato che consente agli amministratori di trasformare i loro siti web in soggetti che possono dire l'osservatore Google le modifiche apportate.

Quindi, a meno che non si può dare un esempio più specifico che cosa dovete fare, non posso dare una risposta più specifica. Con i modelli di design, c'è un punto in cui è necessario sedersi, prendere un problema reale e accendere il cervello.

[Edit3] Ecco un paio di esempi per utilizzi del pattern Observer:

• Molti framework di interfaccia utente utilizzare questo modello per diffondere eventi alle parti interessate. In Qt, si dispone di un punto centrale dove tutti i soggetti possono registrare i segnali (notifiche che ti invierà) e dove gli osservatori possono allegare a soggetti. Ciò significa che c'è un luogo unico nel quale vengono gestite tutte le connessioni. Il vantaggio è che non c'è bisogno di aggiungere questa struttura dati di ogni oggetto. Inoltre, gli oggetti da (oggetti non Qt) al di fuori possono inviare e ricevere messaggi. Poiché tutto è in un unico luogo, questa struttura di dati può essere ottimizzato facilmente. Lo svantaggio è che questa struttura può diventare molto grande, quindi l'invio di un messaggio richiederà più tempo quando ci sono più soggetti coinvolti (anche quelli che sono completamente estranei).

• Google utilizza il protocollo sitemap per trasformare i siti web in soggetti dal momento che è molto più efficiente di attraversamento nuovo e di nuovo l'intero sito, anche se solo si richiede l'ultima ora di modifica di una testa URL (HTTP al posto di HTTP GET ).

• I file system di Windows e Linux notifiche offrono per raccontare le applicazioni su nuove o delefile di TED. Il problema principale è quello che dovrebbe accadere quando i file cambiano mentre un'applicazione non viene eseguito. Diciamo che avete un app che mantiene checksum dei file in una directory. Ovviamente, si desidera sapere modifiche quando l'applicazione è stata verso il basso, ma ciò significherebbe il servizio di notifica avrebbe dovuto tenere traccia dell'ultima modifica ha inviato. Quindi, ecco, l'applicazione deve leggere l'intero albero in fase di avvio per vedere qualcosa che potrebbe avere perso e ha bisogno di utilizzare il modello di osservatore per cambiamenti che avvengono durante l'esecuzione.

• Un client di posta elettronica è un osservatore. Vi dirà il server di posta l'ID della ultima e-mail che ha visto e il server vi dirà che su eventuali nuovi.

• Quando si dispone di un sacco di cambiamenti degli attributi in un modello complesso, di solito è l'unico modo per centralizzare tutte le modifiche (farli correre attraverso un unico posto) e fissare gli osservatori lì (invece di attaccare N osservatori a M individuale oggetti). In questa implementazione, gli osservatori possono dire "Mi interessa alcun cambiamento da nessuna parte" o "un cambiamento del campo X in ogni soggetto" o "ogni cambiamento nel soggetto Y" (l'ultimo di solito raddoppia come un "cambio di campo X nel soggetto Y" -. l'osservatore sarà semplicemente ignorare le modifiche ai campi = X)

Answer 2

Perché non osservatore schema si?

Il soggetto deve informare l'osservatore sugli eventi interessanti. Poi l'osservatore spedisce a parti interessate (iscritti).

La natura del soggetto non è di alcun significato qui. (A meno che non ho capito la tua domanda sbagliata).