Как вы эффективно реализуете шаблон наблюдателя, если объект является огромным контейнером?

Question

Мы все знаем observer pattern: У вас есть тема, которая может уведомлять и обновлять список наблюдателей об изменениях состояния. Теперь предположим, что объект, который вы хотели бы наблюдать, представляет собой контейнер, и вы хотели бы наблюдать сам контейнер, то есть добавление и удаление элементов, а также содержащиеся элементы, то есть обновление состояния элементов контейнера.

Как реализовать механизм обновления так, чтобы он был быстрым в отношении вставки и удаления элементов при хранении огромного количества объектов в вашем контейнере? В частности,

• Вы бы использовали один и тот же контейнер в локальной копии наблюдателей?
• есть ли разумный выбор контейнера, который должны использовать наблюдатели? (Например, было бы быстрее, скажем, всегда использовать сбалансированные деревья, даже если вы наблюдаете связанный список?)
• Как вы быстро переводите итератор в наблюдаемый контейнер в итератор в контейнер наблюдателя? (Тривиально для массивов, трудно для связанных списков?)

Если ваш контейнер является связанным списком, например, вы можете вставлять элементы в постоянное время. Если m наблюдателям приходится перебирать список, содержащий n элементов, то обновление принимает O (n * m) ожидаемое время.

Если ваш контейнер является массивом, то изменение элемента занимает постоянное время, а обновление m наблюдателей принимает O (m), если вы передаете индекс элемента O (n * m), если наблюдатели должны проходить через массив.

Если это помогает, рассмотрим следующие примеры:

Пример 1. Вы пишете операционную систему. Тема, которую вы хотели бы наблюдать, - это файловая система и ее файлы. Ваши представления - это проводник файлов, индекс и другие приложения. Вы хотели бы обновить наблюдателей, когда файлы будут добавлены, удалены или изменены.

Пример 2. Вы пишете приложение адресной книги, которое должно иметь возможность обрабатывать город размером с Нью-Йорк. Тема, которую вы хотели бы наблюдать, - это контейнер ваших записей (человек с его адресом, номерами телефонов, электронной почтой ...). Ваши наблюдатели представляют собой несколько видов, которые должны обновляться автоматически при добавлении, удалении или изменении записи. (Можно было бы отобразить один вид, содержащий список людей, которые живут на 53-й и другие точки рисования на карте для каждого человека, чья фамилия - Doe).

Как вы обрабатываете случай, когда полное поддерево директорий удалено или что «53rd St» переименовано в «Dijkstra St»?

Answer 1

Как-то вы должны превратить контейнер в предмет.

Основная проблема заключается в том, чтобы найти эффективный способ уведомления об изменениях.В большинстве случаев, когда вы сталкиваетесь с этой проблемой, это , потому что вещь, которую вы хотите наблюдать, не предлагает эффективного механизма уведомления (вероятно, потому, что шаблон дизайна наблюдателя не был изобретен, когда они были написаны).

[EDIT] Поскольку вы просите об эффективном способе, общий ответ «это зависит». У шаблонов проектирования нет решения «одноразового использования». Это общие правила, как подойти к проблеме. Как вам нужно реализовать правила в конкретной ситуации - это то, что вы решаете, когда находитесь в ситуации.

Как правило, если ваши наблюдатели должны идентифицировать небольшие изменения (например, изменение атрибута или добавление элемента), уведомление должно содержать достаточно информации, что они могут сделать это эффективно. Поэтому, если у вас есть большой список и вставка, отправьте список и индекс нового элемента плюс «элемент как вставленный».

Что касается изменений атрибутов, то существует два решения. Один из них - добавить наблюдателя к каждому элементу в списке. Это может быть медленным и требует много оперативной памяти, но это означает, что вы можете добавить несколько типов в один список.

В качестве альтернативы вы можете «изменить элемент в службе списка». Это означает, что запрещено напрямую менять элементы, вы всегда должны использовать эту услугу. Затем служба может работать как объект и отправлять уведомления с элементом, старым и измененным значением и, возможно, с индексом в списке.

[EDIT2] Общее правило состоит в том, чтобы собрать как можно больше информации об изменении и передать это наблюдателям. Но это действительно зависит от вашей конкретной проблемы. Скажем, наблюдатель сидит на удаленной машине. В этом случае нет эффективного способа отправить весь список. Вы можете только отправить его «элемент X был вставлен» и надеяться, что этого достаточно. Если в контейнере нет возможности замечать изменения (например, новые веб-страницы на веб-сайте), контейнер должен снова и снова перемещаться по всему сайту, чтобы найти изменения, которые он может затем сказать наблюдателям эффективным образом.

Опять же, детали действительно зависят от конкретной ситуации. Google запускает тысячи пауков, которые посещают миллионы веб-страниц каждый час. Долгое время это было «эффективно» (как в «единственном пути»). Некоторое время назад был реализован протокол «sitemap», который позволяет администраторам превращать свои веб-сайты в темы, которые могут сообщать наблюдателю Google об изменениях.

Поэтому, если вы не можете дать более конкретный пример, что вам нужно сделать, я не могу дать вам более конкретного ответа. С шаблонами дизайна есть точка, где вам нужно сесть, взять настоящую проблему и включить свой мозг.

[EDIT3] Вот несколько примеров для использования шаблона наблюдателя:

• Многих структуры пользовательского интерфейса использовать этот шаблон для распространения события заинтересованных сторон. В Qt у вас есть центральное место, где все субъекты могут регистрировать свои сигналы (уведомления, которые они будут отправлять) и где наблюдатели могут прикрепляться к предметам. Это означает, что есть одно место, где все соединения управляются. Преимущество состоит в том, что вам не нужно добавлять эту структуру данных к каждому объекту. Кроме того, объекты извне (объекты, отличные от Qt) могут отправлять и получать сообщения. Поскольку все находится в одном месте, эту структуру данных можно легко оптимизировать. Недостатком является то, что эта структура может стать очень большой, поэтому отправка сообщения займет больше времени, когда задействовано больше участников (даже те, которые полностью не связаны).

• Google использует протокол sitemap, чтобы превращать веб-сайты в объекты, поскольку это намного эффективнее, чем перемещение всего сайта снова и снова, даже если вы запрашиваете только последнее время модификации URL (HTTP HEAD вместо HTTP GET) ,

• Файловые системы в Windows и Linux предлагают уведомления, чтобы сообщать приложениям о новых или удаленных файлах. Основная проблема здесь заключается в том, что должно произойти, когда файлы меняются, пока приложение не запускается. Скажем, у вас есть приложение, которое поддерживает контрольные суммы файлов в каталоге. Очевидно, что вы хотели бы узнать об изменениях, когда приложение было недоступно, но это означало бы, что служба уведомлений должна будет отслеживать последнее отправленное им изменение. Итак, здесь приложение должно прочитать все дерево при запуске, чтобы увидеть все, что могло бы пропустить, и ему нужно использовать шаблон наблюдателя для изменений, происходящих во время его запуска.

• Почтовый клиент является наблюдателем. Он сообщит почтовому серверу идентификатор последнего электронного письма, которое он видел, и сервер расскажет о каких-либо новых.

• Когда у вас много изменений атрибутов в сложной модели, это, как правило, единственный способ централизовать все изменения (заставить их проехать через одно место) и приложить туда наблюдателей (вместо того, чтобы прикреплять N наблюдателей к M отдельным объектам). В этой реализации наблюдатели могут сказать «меня интересуют любые изменения в любом месте» или «изменение поля X в любом предмете» или «любое изменение предмета Y» (последнее обычно удваивается как «изменение поля» X в субъекте Y "- наблюдатель просто игнорирует изменения в полях! = X).

Answer 2

Почему бы не использовать шаблон наблюдателя?

Тема должна информировать наблюдателя об интересных событиях. Затем наблюдатель отсылает его заинтересованным сторонам (подписчикам).

Характер предмета здесь не имеет никакого значения. (Если я не понял ваш вопрос неправильно).