两个相关对象列表同步的标准算法是什么？

Question

我相信这一定在某种教科书中（或更可能是所有教科书中），但我似乎使用了错误的关键词来搜索它... :(

编程时我经常面临的一个任务是处理来自不同来源的对象列表，我需要以某种方式将它们保持同步。通常有一些“主列表”，例如由一些外部API返回，然后我自己创建的对象列表，每个对象对应于主列表中的一个对象(类似"包装器"或"适配器"，它们通常包含特定于我的应用程序的外部对象的扩展信息和/或简化访问外部对象)。

问题实例的硬性特征：

• 我无法访问主列表的实现；其接口是固定的
• 两个列表中的元素不能进行赋值
• 我完全控制从列表的实现
• 我无法控制主列表中元素的顺序(即不可排序)
• 主列表要么根本不提供有关添加或删除元素的通知，要么通知不可靠，即同步只能按需发生，而非实时发生
• 简单地清除并重建从头开始所需的从列表不是选项:
  • 初始化包装器对象应被视为昂贵的
  • 其他对象将持有对包装器的引用

问题实例的其他特点：

• 主列表中的元素只能通过读取其属性而不是直接通过索引或内存地址访问来标识：
  • 刷新后，主列表可能返回一组全新的实例，尽管它们仍然表示相同的信息
  • 访问主列表中元素的唯一接口可能是一个连续的枚举器
• 大多数情况下，主列表中元素的顺序是稳定的，即新元素总是添加在开头或结尾，永远不会在中间添加；但是，删除通常可以发生在任何位置

那么我通常如何解决这个问题呢？我应该搜索什么算法的名称？

过去我曾以多种方式实现过这个问题（请参见下面的示例），但总觉得应该有一种更清洁和高效的方式，特别是不需要两次迭代（每个列表一次）。

下面是一个示例方法：

1. 迭代主列表
2. 在“从属列表”中查找每个项
3. 添加尚不存在的项
4. 以某种方式跟踪已经存在于两个列表中的项目（例如通过标记它们或保持另一个列表）
5. 完成后，迭代从属列表并删除所有未被标记的对象（请参见4.），然后再次从所有其他对象中清除标记

---

更新1 感谢大家迄今为止的回复！我需要一些时间来查看链接。
[...] （文本移动到问题正文中）

更新2 将中间段落重构为（希望）更易于解析的项目列表，并包含在第一个更新后添加的详细信息中。

- Oliver Giesen

---

如果主列表没有通知您已更改，我不认为您可以以其他方式完成此操作... - Skilldrick

“标准算法”肯定是在合并之前保持列表排序。如果没有这样做，我认为你必须做类似于你在此处描述的事情。 - mqp

尝试在谷歌上搜索“数据协调算法”。 - oz10

Answer 1

两种典型的解决方案是： 1. 将主列表复制到同步列表中。 2. 对所有元素对进行O(N*N)比较。

你已经排除了智能选项：共享标识、排序和更改通知。

请注意，列表是否可以以有意义的方式排序或完全排序并不重要。例如，当比较两个字符串列表时，按字母顺序排序会很理想。但是，如果您按字符串长度对两个列表进行排序，则列表比较仍将更有效率！您仍然需要对相同长度的字符串进行完全的成对比较，但这可能是更小的一组对。

- MSalters

---

你说的共享身份是什么意思？我在谷歌上找不到任何相关的参考资料。 - Étienne

@ÉtienneReinstateMonica：在这里，“identity”指的是一个对象的地址，或者任何能够准确标识一个对象的类似属性。特别地，当且仅当两个对象表达式解析为相同的identity/address时，它们才表示相同的对象。在这个上下文中，“shared”意味着这两个对象列表使用相同的identity属性来表示列表上的对象。 - MSalters

Answer 2

这看起来像是集合协调问题，即同步无序数据的问题。有一个关于此问题的SO问答：Implementation of set reconciliation algorithm。

谷歌上大多数参考资料都是技术论文摘要。

- Andrew

---

我认为OP想要同步列表，而不是集合。保留顺序将需要不同的解决方案。 - Eric Nguyen

Answer 3

似乎有一个叫Michael Heyeck的人已经提出了一个好的O(n)解决方案来解决这个问题。请查看该博客文章，以获取解释和一些代码。

本质上，该解决方案在单次通过中跟踪主列表和从列表，并跟踪各自的索引。然后管理两个数据结构：要在从列表上重放的插入列表和删除列表。

看起来很简单，并且有最小化证明的好处，Heyeck在随后的文章中进行了跟进。本文中的代码片段也更加紧凑：

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)

再次向Michael Heyeck致敬。

- Eric Nguyen

---

问题说明主列表未排序，因此这是一个不同的问题。 - nschum

除非我误解了，OP只是说他的主列表无法进行排序。也就是说，它仍然是一个有序列表——只是OP无法控制排序方式。据我所知，Heyeck的解决方案符合这些限制条件。 - Eric Nguyen

Answer 4

通常解决这些问题的最好方法是不直接解决它们。

如果你的代码段中真的不能使用排序的二进制可搜索容器（例如set或排序的vector），那么...

你内存非常受限吗？如果不是，我会创建一个字典（例如std::set），其中包含其中一个列表的内容，然后只需迭代要与第一个同步的第二个列表。

这样，你需要nlogn来创建字典（或nX用于哈希字典，具体取决于哪种更有效）+mlogn操作以遍历第二个列表并将其与第一个同步（或只需MY）。如果你确实必须在代码中使用列表，则很难超越该方法。而且，它只需要在需要时执行一次，比始终保持列表排序要好得多，后者对于它们都是n ^ 2的任务。

- RnR

Answer 5

在C++ STL中，算法被称为set_union。此外，如果您将联合操作执行到第三个列表中，则实现该算法可能会更简单。

- oz10

---

这很可能只是执行OP描述的算法。此外，OP正在寻找一个与语言无关的解决方案，即：一种算法解决方案。 - Ben S

@Ben S：提问者说他们在谷歌上找不到算法...并询问要搜索的名称。我的回答是提供给提问者缩小搜索范围的起点。 - oz10

Answer 6

这是Michael Heyek的Python代码的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;
    }

- Mike Tommasi

---

抱歉，但这完全不符合问题：首先，我的列表既不是有序的，也不是类型兼容的。 - Oliver Giesen

Answer 7

我曾经在一个项目中遇到过这样的问题。

那个项目有一个主数据源和几个客户端，它们独立地更新数据，最终所有客户端都必须拥有最新和统一的数据集，这些数据是它们的总和。

我的做法类似于 SVN 协议，在每次想要更新主数据库（通过 Web 服务访问）时，我获取了修订号。将本地数据存储更新到该修订号，然后将未被任何修订号覆盖的实体提交到数据库。

每个客户端都可以将其本地数据存储更新到最新的修订版。

- Karim Agha

Answer 8

非常暴力和纯技术的方法：

从您的List类继承（抱歉，不知道您的语言是什么）。在您的子列表类中覆盖add/remove方法。使用您的类代替基础类。现在，您可以使用自己的方法跟踪更改并在线同步列表。

- Alexey Kalmykov

---

主列表仅可通过第三方 Web 服务进行访问，调用更改主列表的代码不可更改。 - Étienne