Каков стандартный алгоритм синхронизации двух списков связанных объектов?

Question

Я почти уверен, что это должно быть в каком-то учебнике (или, скорее, во всех), но, похоже, я использую неправильные ключевые слова для его поиска ...: (

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

Жесткие характеристики всех случаев проблемы:

• реализация мастер-списка скрыта от меня; его интерфейс фиксирован
• элементы в двух списках несовместимы с присвоением
• У меня есть полный контроль над реализацией списка рабов
• Я не могу управлять порядком элементов в главном списке (т. Е. Он не сортируется)
• основной список либо вообще не предоставляет уведомления о добавленных или удаленных элементах, либо уведомление ненадежно, т. Е. Синхронизация может происходить только по требованию, а не в режиме реального времени
• просто очистить и перестроить список ведомых с нуля всякий раз, когда это необходимо, не вариант:
  • инициализация объектов-обёрток должна считаться дорогой
  • другие объекты будут содержать ссылки на оболочки

Дополнительные характеристики в некоторых случаях проблемы:

• элементы в основном списке могут быть идентифицированы только путем чтения их свойств, а не доступа к ним напрямую по индексу или адресу памяти:
  • после обновления основной список может вернуть совершенно новый набор экземпляров, даже если они все еще представляют ту же информацию
  • единственным интерфейсом для доступа к элементам в основном списке может быть последовательный перечислитель
• в большинстве случаев порядок элементов в главном списке стабилен, то есть новые элементы всегда добавляются либо в начале, либо в конце, а не в середине; однако удаление обычно может происходить в любой позиции

Так как бы я обычно занялся этим? Как называется алгоритм, по которому я должен гуглить?

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

Вот пример подхода:

1. Перебор основного списка
2. Поиск каждого элемента в «списке рабов»
3. Добавить элементы, которые еще не существуют
4. Каким-то образом отслеживайте элементы, которые уже существуют в обоих списках (например, помечая их или сохраняя еще один список)
5. Когда закончите, переберите список ведомых и удалите все объекты, которые не были помечены (см. 4.), и снова удалите тег из всех остальных

---

Обновление 1 Спасибо за все ваши ответы до сих пор! Мне понадобится некоторое время, чтобы просмотреть ссылки.
[...] (текст перенесен в основную часть вопроса)

Обновление 2 Перегруппировал средний абзац в (надеюсь) более легко разбираемые списки маркеров и включил детали, добавленные позже в первом обновлении.

Answer 1

Это похоже на проблему согласованной установки, то есть проблему синхронизации неупорядоченных данных. Был задан вопрос о SO: Реализация алгоритма сверки множества .

Большинство ссылок в Google относятся к рефератам технических статей.

Answer 2

Часто лучшее решение таких проблем - не решать их напрямую.

Если вы действительно не можете использовать отсортированный двоичный контейнер с возможностью поиска в вашей части кода (например, набор или даже отсортированный вектор), тогда ...

Вы очень сильно привязаны к памяти? Если нет, то я просто создаю словарь (например, std :: set), содержащий содержимое одного из списков, а затем просто перебираю второй, который я хочу синхронизировать с первым.

Таким образом, вы делаете n logn для создания словаря (или n X для хэш-словаря в зависимости от того, какой из них будет более эффективным) + m logn операций для перехода по второму списку и синхронизировать его (или просто M Y) - трудно победить, если вам действительно нужно использовать списки в первую очередь - также хорошо, что вы делаете это только один раз, когда и если вам это нужно, и это намного лучше, чем хранить списки сортировать все время, что было бы задачей ^ 2 для них обоих.

Answer 3

2 типичных решения: 1. Скопируйте основной список в список синхронизации. 2. Проведите сравнение O (N * N) между всеми парами элементов.

Вы уже исключили интеллектуальные параметры: общая идентификация, сортировка и уведомления об изменениях.

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

Answer 4

Похоже, у парня по имени Майкл Хейк есть хорошее O (n) решение этой проблемы. Проверьте это сообщение в блоге для объяснения и некоторого кода.

По сути, решение отслеживает как ведущие, так и ведомые списки за один проход, отслеживая индексы в каждом. Затем осуществляется управление двумя структурами данных: список вставок для воспроизведения в ведомом списке и список удалений.

Это выглядит просто, а также имеет преимущество доказательства минимализма, за которым Хайек следовал в последующих постах Фрагмент кода в этом посте также более компактен:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x < len(a)) or (y < len(b)):
    if y >= len(b): d.append(x); x += 1
    elif x >= len(a): i.append((y, b[y])); y += 1
    elif a[x] < b[y]: d.append(x); x += 1
    elif a[x] > b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)

Опять же, спасибо Майклу Хайеку.

Answer 5

В C ++ STL алгоритм называется set_union. Кроме того, реализация алгоритма, вероятно, будет намного проще, если объединить в третий список.

Answer 6

Вот Javascript-версия кода Python Майкла Хейека.

    var b= [1,3,8,12,16,19,22,24,26]; // new situation
    var a = [1,2,8,9,19,22,23,26]; // previous situation
    var result = sync_ordered_lists(a,b);
console.log(result);
    function sync_ordered_lists(a,b){
// by Michael Heyeck see http://www.mlsite.net/blog/?p=2250
// a is the subject list
// b is the target list
// x is the "current position" in the subject list
// y is the "current position" in the target list
// i is the list of inserts
// d is the list of deletes
        var x = 0; 
        var y = 0; 
        var i = []; 
        var d = []; 
        var acc = {}; // object containing inserts and deletes arrays
        while (x < a.length || y < b.length) {
            if (y >= b.length){
                d.push(x); 
                x++;
            } else if (x >= a.length){ 
                i.push([y, b[y]]); 
                y++;
            } else if (a[x] < b[y]){ 
                d.push(x); 
                x++;
            } else if (a[x] > b[y]){ 
                i.push([y, b[y]]); 
                y++;
            } else { 
                x++; y++;
            }
        }
        acc.inserts = i;
        acc.deletes = d;
        return acc;
    }

Answer 7

В прошлом у меня была такая проблема в одном проекте.

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

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

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

Answer 8

Очень грубый и чистый технический подход:

Наследовать из вашего класса List (извините, не знаю, на каком языке вы говорите). Переопределите методы добавления / удаления в вашем дочернем списке. Используйте свой класс вместо базового. Теперь вы можете отслеживать изменения с помощью собственных методов и синхронизировать списки в режиме онлайн.