如何确定两个数据列表中的差异

Question

这是 CS 人员运用理论的练习。

假设您有 2 个装有元素的容器。 文件夹、URL、文件、字符串，这真的不重要。

计算添加和删除的AN算法是什么？

注意：如果有多种方法可以解决此问题，请为每个答案发布一个，以便进行分析和投票。

编辑：所有答案都可以用 4 个容器解决问题。 可以只使用前2个吗？

Answer 1

假设您有两个唯一项目列表，并且顺序并不重要，您可以将它们视为集合而不是列表

如果您考虑维恩图，其中列表 A 为一个圆圈，列表 B 为另一个圆圈，则这两者的交集就是常量池。

从 A 和 B 中删除该交集中的所有元素，A 中剩下的所有元素都被删除，而 B 中剩下的所有元素都被添加。

因此，迭代 A 查找 B 中的每个项目。如果找到它，请将其从 A 和 B 中删除

然后 A 是已删除的内容的列表，B 是

我认为添加的内容的列表......

[编辑] 好吧，有了新的“仅 2 个容器”限制，同样的情况仍然成立：

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

那么您就不会构建新列表，也不会销毁旧列表......但与前面的示例一样，它会花费更长的时间，您可以循环遍历较短的列表并从较长的列表中删除元素。 这里你需要做两个列表

我认为我的第一个解决方案没有使用 4 个容器，它只是破坏了两个;-)

Answer 2

我已经有一段时间没有这样做了，但我相信算法是这样的......

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

关于右列表与左列表的关系，删除包含删除的项目和添加 现在包含新项目。

Answer 3

缺失信息：如何定义添加/删除？ 例如，如果列表（A 和 B）显示服务器 A 和服务器 B 上的相同目录，则说明是同步的。 如果我现在等待 10 天，再次生成列表并进行比较，我如何判断某些内容是否已被删除？ 我不能。 我只能告诉服务器 A 上有文件在服务器 B 上找不到，和/或反之亦然。 无论是因为文件已添加到服务器 A（因此在 B 上找不到该文件）还是因为文件已在服务器 B 上删除（因此在 B 上不再找到该文件），我无法仅通过文件名列表来确定某些内容。

对于我建议的解决方案，我将假设您有一个名为 OLD 的列表和一个名为 NEW 的列表。 在旧版中找到但在新版中未找到的所有内容均已被删除。 已添加在新设备上找到但在旧设备上未找到的所有内容（例如，同一服务器上同一目录的内容，但列表是在不同日期创建的）。

此外，我假设没有重复项。 这意味着任一列表中的每个项目在以下意义上都是唯一的：如果我将此项目与列表中的任何其他项目进行比较（无论此比较如何工作），我总是可以说该项目更小 或大于我与之比较的那个，但永远不会相等。 例如，在处理字符串时，我可以按字典顺序比较它们，并且相同的字符串永远不会在列表中出现两次。

在这种情况下，最简单的（但不一定是最佳解决方案）是：

1. 对旧列表进行排序。 例如，如果列表由字符串组成，则按字母顺序对它们进行排序。 排序是必要的，因为这意味着我可以使用二分搜索来快速找到列表中的对象，假设它确实存在于那里（或者快速确定它根本不存在于列表中）。 如果列表未排序，则查找对象的复杂度为 O(n)（我需要查看列表中的每个项目）。 如果列表已排序，复杂度仅为 O(log n)，因为每次尝试匹配列表中的项目后，我总是可以排除列表中 50% 不匹配的项目。 即使列表有 100 个项目，找到一个项目（或检测到该项目不在列表中）最多需要 7 次测试（或者是 8 次？无论如何，远少于 100 次）。 新列表不必排序。

2. 现在我们执行列表消除。 对于 NEW 列表中的每个项目，尝试在 OLD 列表中找到该项目（使用二分搜索）。 如果找到该项目，请从旧列表中删除该项目，并同时将其从新列表中删除。 这也意味着消除过程越深入，列表就越小，因此查找将变得越来越快。 由于从列表中删除项目不会影响列表的正确排序顺序，因此在消除阶段无需使用旧列表。

3. 在消除结束时，两个列表可能都是空的，在这种情况下它们是相等的。 如果它们不为空，则旧列表中仍然存在的所有项目都是新列表中缺少的项目（否则我们已删除它们），因此这些是已删除的项目。 仍在新列表中的所有项目都是不在旧列表中的项目（同样，我们已经删除了它们），因此这些是添加的项目。

Answer 4

乔说的话。 而且，如果列表太大而无法放入内存，请使用外部文件排序实用程序或合并排序。

Answer 5

列表中的对象是否“唯一”？ 在这种情况下，我将首先构建两个映射（哈希映射），然后扫描列表并查找映射中的每个对象。

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

对于 Ruby 和 Java 可怕的元语言混合感到抱歉 :-P

最后 removedElements 将包含属于 list1 的元素，但不属于 list2，并且 addedElements 将包含属于list2的元素。

整个操作的成本是 O(4*N)，因为映射/字典中的查找可以被认为是恒定的。 另一方面，线性/二元搜索列表中的每个元素将实现 O(N^2)。

编辑：再考虑一下将最后一个检查移到第二个循环中，您可以删除其中一个循环...但这很丑陋...:)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}