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

Question

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

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

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

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

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

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

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

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

Как вы поступите в случае удаления всего поддерева каталога или переименования «53-й улицы» в «Дийкстра-стрит»?

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

Почему бы не сам шаблон наблюдателя?

Субъекту необходимо сообщить наблюдателю об интересных событиях.Затем наблюдатель рассылает его заинтересованным лицам (абонентам).

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