C/C++ - 高效比较两个列表并找到缺失元素的方法

Question

C/C++ - 高效比较两个列表并找到缺失元素的方法

6

我有两个数据列表L₁和L₂，它们均包含多个元素，每个元素都是一个独特的抽象数据类型（如structs）。这两个列表：

- 可以包含零到一百个（含）元素 - 不包含重复元素（每个元素都是唯一的） - 可能包含在另一个列表中的元素（即L₁和L₂可能完全不同，也可能相同） - 没有排序 - 在最底层使用std::vector<myStruct>容器存储

通常情况下，我期望定期向L₂添加新元素或者从其中删除元素。我想尽可能有效地（即使用最少比较次数）检测两个列表之间的差异：

- 如果条目在L₁中存在而在L₂中不存在，则执行一个操作：Handle_Missing_Element() - 如果条目在L₂中存在而在L₁中不存在，则执行另一个操作：Handle_New_Element() 完成上述检查后，将L₁设置为等于L₂，并且在将来的某个时间再次检查L₂。

如何找出这两个列表之间的差异？我可以想到两种方法：

1. 通过每种可能的元素组合来比较两个列表。可能的执行复杂度为O(n²)（可怕）。 2. 将两个列表排序并按元素顺序进行比较，该方法可能效率高一些。

bool found;
for i in 1 .. L2->length()
  found = false;
  for j in 1 .. L1->length()
    if (L1[j] == L2[i]
      // Found duplicate entry
      found = true;
    fi
  endfor
endfor

将列表排序，并逐个元素比较两个列表，直到找到差异。这似乎是几乎线性的时间复杂度。问题在于我需要对列表进行排序。在每次添加/移除后手动对底层向量进行排序是不切实际的。只有当可以强制 vector::push_back() 自动插入元素以保留列表排序时，这才是合理的。

在C++中是否有一种高效的简单方法来实现这个呢？我找到了类似的问题，但是我不仅需要找到两个集合的交集，或者使用只包含整数的集合进行这样的测试，可以使用与求和相关的技巧，因为我需要针对“新”和“缺失”的元素执行不同的操作。

谢谢。

- Cloud

3

在C语言中使用std::vector<myStruct>很困难。建议去掉"C"标签。 - chux - Reinstate Monica

1

那么，你的列表并不是真正的链表（如std::list），而实际上是数组（如std::vector）？ - AnT stands with Russia

1

@Beta 我没有比较函数。它只是一个 struct，而不是一个完全定义的 class。 - Cloud

@Beta 我会定期执行操作，因此事先无法知道进行了多少次添加/删除。 - Cloud

你可以利用链表构建一个“跳表”。我认为大多数好的搜索都依赖于某种排序表示。跳表是一种带有nlogn()搜索的高级链表。 - Matt

显示剩余4条评论

4个回答

4

在列表中每次添加/删除元素后手动对底层向量进行排序是不切实际的。只有当可以以某种方式强制vector::push_back()自动插入元素以保持列表的排序时，才有可能这样做。

您在谈论有序插入。在<algorithm>中有一些函数可以实现这个功能。您将使用std::vector::insert而不是使用std::vector::push_back，并调用std::lower_bound进行二进制搜索，以查找第一个不小于给定值的元素。

auto insert_pos = std::lower_bound( L2.begin(), L2.end(), value );
if( insert_pos == L2.end() || *insert_pos != value )
{
    L2.insert( insert_pos, value );
}

这使得每次插入的时间复杂度为O(logN)，但如果你在两次周期性检查之间进行的插入次数少于N次，这应该会有所改善。

压缩操作可能看起来像这样：

auto it1 = L1.begin();
auto it2 = L2.begin();

while( it1 != L1.end() && it2 != L2.end() )
{
    if( *it1 < *it2 ) {
        Handle_Missing( *it1++ );
    } else if( *it2 < *it1 ) {
        Handle_New( *it2++ );
    } else {
        it1++;
        it2++;
    }
}

while( it1 != L1.end() ) Handle_Missing( *it1++ );
while( it2 != L2.end() ) Handle_New( *it2++ );

- paddy

2

在向量中间插入需要 O(N) 的时间。 - stgatilov

1

实际上，对于任何小到相当令人不快的包含类型，向量插入都比列表更快。我认为如果OP能够说明他们为什么要维护这两个列表，那会有所帮助。我建议将操作提供给队列并立即执行它们，或者将所有内容存储在树中。 - paddy

1

@paddy 我正在跟踪音频/DSP系统中新连接/断开的麦克风，并需要告诉底层软件为新麦克风分配缓冲区，或清理和释放不再连接到系统的麦克风的缓冲区。我唯一能够唯一标识麦克风的方式是通过硬编码到硬件中的UUID。目前，我没有断开/连接事件处理功能，必须依靠轮询所有连接的音频设备（潜在的麦克风）。 - Cloud

1

听起来，你可能只需要将L1作为一个排序向量进行维护（使用有序插入），并完全摆脱L2。当枚举连接的设备UUID时，可以在L1中进行二进制搜索（使用std :: binary_search），然后将其推入“添加”或“删除”向量。枚举之后，遍历这些向量，调用适当的处理程序并更新L1。 - paddy

1

@simon 这是正确的，但内存布局不同。使用向量可以提高缓存本地性。我们很难知道 OP 有多频繁地进行轮询。我们所知道的是，这可能每秒发生数百次。此外，可以给向量提供适度的预留空间，以便在正常操作条件下永远不需要分配。当然，这可能会被视为过早优化。使用 set 可能是完全有效的解决方案。 - paddy

显示剩余2条评论

3

自动在插入时进行排序的容器是std::set。插入操作的时间复杂度为O(log n)，比较两个集合的时间复杂度为O(n)。由于所有元素都是唯一的，因此不需要使用std::multiset。

- Mark Ransom

2

对于两个数组中的每个元素，维护它在另一个数组中出现的次数。可以将这些数字存储在具有相同索引的单独数组中，也可以存储在使用的结构体中。

当将元素x插入L2时，必须检查它是否与L1中的所有元素相等。在每个等式中，增加元素x和y的计数器。

当从L2中删除元素x时，必须再次将其与L1中的所有元素进行比较。在每个与L1中的y相等的等式中，减少y的计数器。由于x被移除，因此x的计数器无关紧要。

当您想要查找非重复元素时，可以简单地迭代两个数组。计数器为零的元素是所需的元素。

总共，每次插入和删除需要额外进行O(|L1|)个操作，并且每次查找重复项需要O(|L1| + |L2|)个操作。如果您还维护所有计数器为零的元素列表，则后者可以减少到所寻找的非重复元素数量。

编辑：糟糕，由于每个列表中的唯一性，每个计数器似乎始终为0或1。

编辑2：正如Thane Plummer所写，您还可以使用哈希表。如果您为L1创建哈希表，则可以在插入和删除时以O(1)的时间完成所有比较。顺便说一句，由于您的L1是恒定的，因此您甚至可以为其创建完美哈希表以加快速度。

- stgatilov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thane Plummer · Accepted Answer

你能为列表项创建哈希值吗？如果可以的话，只需计算哈希值并检查另一个列表的哈希表。这样做很快捷，不需要排序，并防止出现“每种可能组合”的问题。如果你使用C++和STL，你可以使用map容器来保存每个列表。

为L1中的每个项创建一个哈希值，并使用map将其与列表项关联起来。
为L2创建类似的map，并在创建每个L2时检查它是否在L1 map中。
当向L2添加新元素时，计算其哈希值并检查它是否在L1哈希表中（如果使用STL maps，则使用map.find()）。如果没有，则执行Handle_New_Element()函数。
当从L2列表中减去元素且其哈希值不在L1哈希图中时，执行Handle_Missing_Element()函数。