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

Question

我很确定这必须在某种教科书中(或者更有可能在所有这些教科书中)但我似乎使用了错误的关键词来搜索它...... :(

我在编程时遇到的一个反复出现的任务是我正在处理来自不同来源的对象列表,我需要以某种方式保持同步.通常有一些"主列表",例如由一些外部API返回,然后是我自己创建的对象列表,每个对象都与主列表中的对象相对应(想想"包装"或"适配器" - 它们通常包含扩展信息关于特定于我的应用程序的外部对象和/或它们简化了对外部对象的访问.

所有问题实例的硬特征:

• 主列表的实现对我来说是隐藏的; 它的界面是固定的
• 两个列表中的元素不是赋值兼容的
• 我完全可以控制从属列表的实现
• 我无法控制主列表中元素的顺序(即它不可排序)
• 主列表要么根本不提供有关添加或删除元素的通知,要么通知不可靠,即同步只能按需发生,而不是直播
• 只需在需要时从头开始清除和重建从属列表不是一个选项:
  • 初始化包装器对象应该被认为是昂贵的
  • 其他对象将保存对包装器的引用

在某些情况下的其他特征:

• 主列表中的元素只能通过读取其属性来识别,而不是通过索引或内存地址直接访问它们:
  • 刷新后,主列表可能会返回一组全新的实例,即使它们仍然代表相同的信息
  • 访问主列表中元素的唯一接口可能是顺序枚举器
• 大多数情况下,主列表中元素的顺序是稳定的,即新元素总是在开头或结尾添加,而不是在中间; 但是,删除通常可以在任何位置进行

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

在过去,我已经以各种方式实现了这一点(参见下面的示例),但总觉得应该有更清洁,更有效的方式,尤其是不需要两次迭代的方法(每个列表一个).

这是一个示例方法:

1. 迭代主列表
2. 查找"从属列表"中的每个项目
3. 添加尚不存在的项目
4. 以某种方式跟踪两个列表中已存在的项目(例如,通过标记它们或保留另一个列表)
5. 完成后,迭代从属列表并删除所有未标记的对象(请参阅4.)并再次清除所有其他对象

---

更新1 感谢您的所有回复!我需要一些时间来查看链接.
[...] (文字移至问题主体)

更新2 将中间段重构为(希望)更易于解析的项目符号列表,并在第一次更新中添加后续添加的详细信息.

Answer 1

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

您已经排除了智能选项：共享身份、排序和更改通知。

请注意，列表是否可以以有意义的方式进行排序甚至完全排序并不相关。例如，在比较两个字符串列表时，最好按字母顺序排序。但是如果您按字符串长度对两个列表进行排序，列表比较仍然会更有效！您仍然需要对相同长度的字符串进行完整的成对比较，但这可能会少得多。

Answer 2

这看起来像集合协调问题，即同步无序数据的问题。有人就此提出了关于SO的问题：Implementation of set reconciliationalgorithm。

谷歌上的大部分参考文献都是技术论文摘要。

Answer 3

在 C++ STL 中，该算法称为 set_union。此外，如果您将并集合并到第三个列表中，则实现该算法可能会简单得多。