Каков стандартный алгоритм для синхронизации двух списков связанных объектов?
Я вполне уверен, это должно быть в некотором учебнике (или более вероятно во всех них), но я, кажется, использую неправильные ключевые слова для поиска его... :(
Повторяющаяся задача, с которой я сталкиваюсь, в то время как программирование состоит в том, что я имею дело со списками объектов из других источников, которые я должен сохранить в синхронизации так или иначе. Обычно существует своего рода "основной список", например, возвратился некоторым внешним API и затем списком объектов, которые я создаю сам, каждый из которых соответствует объекту в основном списке (думают "обертки" или "адаптеры" - они обычно содержат расширенную информацию о внешних объектах, характерных для моего приложения, и/или они упрощают доступ к внешним объектам).
Твердые характеристики всех экземпляров проблемы:
- реализация основного списка скрыта от меня; его интерфейс фиксируется
- элементы в двух списках не совместимы с присвоением
- Я имею полный контроль над реализацией ведомого списка
- Я не могу управлять порядком элементов в основном списке (т.е. это не является поддающимся сортировке),
- основной список или не предоставляет уведомление о добавленных или удаленных элементах вообще, или уведомление ненадежно, т.е. синхронизация может только произойти по запросу, не живой
- просто очистка и восстановление ведомого списка с нуля каждый раз, когда это необходимо, не являются опцией:
- инициализацию интерфейсных объектов нужно считать дорогой
- другие объекты будут содержать ссылки на обертки
Дополнительные характеристики в некоторых случаях проблемы:
- элементы в основном списке могут только быть определены путем чтения их свойств вместо того, чтобы получить доступ к ним непосредственно индексом или адресом памяти:
- после обновления основной список мог бы возвратить абсолютно новый набор экземпляров даже при том, что они все еще представляют ту же информацию
- единственный интерфейс для доступа к элементам в основном списке мог бы быть последовательным перечислителем
- большую часть времени порядок элементов в основном списке стабилен, т.е. новые элементы всегда добавляются или вначале или в конце, никогда в середине; однако, удаление может обычно происходить в любом положении
Таким образом, как я обычно занимался бы этим? Каково название алгоритма, для которого я должен погуглить?
В прошлом я реализовал это различными способами (см. ниже для примера), но всегда было такое чувство, что должен быть более чистый и более эффективный путь, особенно тот, который не потребовал двух повторений (один по каждому списку).
Вот подход в качестве примера:
- Выполните итерации по основному списку
- Ищите каждый объект в "ведомом списке"
- Добавьте объекты, которые еще не существуют
- Так или иначе отслеживайте объекты, которые уже существуют в обоих списках (например, путем меток их или хранения еще одного списка)
- При выполнении выполните итерации по ведомому списку и удалите все объекты, которые не были отмечены (см. 4.) и ясный тег снова от всех других
Обновите 1 спасибо за все Ваши ответы до сих пор! Мне будет требоваться некоторое время для рассмотрения ссылок.
[...] (текст, перемещенный в основную часть вопроса)
Обновите 2 Restructered средний абзац в (надо надеяться), более легко parseable маркированные списки и включенные детали, добавленные позже в первом обновлении.
6 ответов
Это похоже на установленную проблему согласования, т. Е. На проблему синхронизации неупорядоченных данных. По этому поводу был задан вопрос по SO: Реализация алгоритма согласования множеств .
Большинство ссылок в Google относятся к рефератам из технических статей.
2 типичных решения: 1. Скопируйте главный список в список синхронизации. 2. Выполните O (N * N) сравнение между всеми парами элементов.
Вы уже исключили интеллектуальные параметры: общая идентификация, сортировка и уведомления об изменениях.
Обратите внимание, что не имеет значения, можно ли сортировать списки осмысленным способом или даже полностью. Например, при сравнении двух списков строк было бы идеально выполнить сортировку по алфавиту. Но сравнение списков было бы более эффективным, если бы вы отсортировали оба списка по длине строки ! Вам все равно придется провести полное попарное сравнение строк одинаковой длины, но это, вероятно, будет гораздо меньшее количество пар.
Часто лучшее решение таких проблем - не решать их напрямую.
ЕСЛИ вы действительно не можете использовать отсортированный двоичный контейнер с возможностью поиска в своей части кода (например, набор или даже отсортированный вектор). ..
Вы сильно ограничены в памяти? В противном случае я бы просто создал словарь (например, std :: set), содержащий содержимое одного из списков, а затем просто перебрал бы второй, который я хочу синхронизировать с первым.
Таким образом, вы ' повторное выполнение n logn для создания словаря (или n X для хэш-словаря в зависимости от того, какой из них будет более эффективным) + m logn операций, чтобы просмотреть второй список и синхронизировать его (или просто M Y) - трудно превзойти, если вам действительно нужно использовать списки в первую очередь - также хорошо, что вы делаете это только один раз, когда и если вам это нужно, и это '
В C ++ STL алгоритм называется set_union. Кроме того, реализация алгоритма, вероятно, будет намного проще, если вы выполните объединение в третий список.
Очень грубый и чисто технический подход:
Наследование от вашего класса List (извините, я не знаю, какой у вас язык). Переопределите методы добавления / удаления в классе дочернего списка. Используйте свой класс вместо базового. Теперь вы можете отслеживать изменения своими методами и синхронизировать списки в режиме онлайн.
Раньше у меня была такая проблема в одном проекте.
В этом проекте был один источник основных данных и несколько клиентов, которые обновляют данные независимо, и, в конце концов, все они должны иметь последний и унифицированный набор данных, который представляет собой их сумму.
Я создал что-то похожее на протокол SVN, в котором каждый раз, когда я хотел обновить основную базу данных (которая была доступна через веб-службу), я получал номер версии. Обновил мое локальное хранилище данных до этой ревизии, а затем зафиксировал объекты, которые не охвачены каким-либо номером ревизии, в базу данных.
Каждый клиент имеет возможность обновить свое локальное хранилище данных до последней версии.