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

Ответ 1

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

Большинство ссылок на google на технические рефераты.

Ответ 2

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

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

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

Ответ 3

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

ЕСЛИ вы действительно не можете использовать сортированный бинарный контейнер для поиска в своей части кода (например, набор или даже отсортированный вектор), затем...

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

Таким образом, вы создаете nlogn для создания словаря (или nX для хеш-словаря, в зависимости от того, что будет более эффективным) + операции mlogn, чтобы переходить во второй список и синхронизировать его (или просто MY) - трудно выполнить если вам действительно нужно использовать списки в первую очередь - также хорошо, что вы делаете это только один раз, когда и если вам это нужно, и это лучше, чем сохранение списков, отсортированных все время, что было бы задачей 2 для обоих из них.

Ответ 4

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

Ответ 5

Похоже, что этот парень по имени Майкл Хейк имеет хорошее, 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)

Снова, кредит Майклу Хейку.

Ответ 6

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

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

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

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

Ответ 7

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

    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;
    }

Ответ 8

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

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