两个未排序的小数组的交集算法

Question

3

我正在寻找一种算法，用于在特定条件下交叉两个小的、未排序的数组。

暴力/排序和交集的解决方案都不是那么糟糕，但我认为它们不够快。是否有更优化的解决方案？

- summerlight

1

场景中的“足够快”是多少？ - Ameen

从 if (a.empty || b.empty) return emptySet; 开始进行排序和交集操作。此外，如果只有一个元素，您可以直接在另一个数组中查找该元素。 - Bernhard Barker

一个非常重要的问题是：这样不同的集合可能有多少个？（这在很大程度上取决于集合中的值）如果有少量不同的值，那么你就有一个非常好的解决方案。 - Michael

Ameen // 我预计每秒会有数百万次调用，并且不应占用大量运行时间。（<0.1%？） - summerlight

Michael // 我预计两个数组彼此之间存在相关性，但目前还没有任何统计数据。 - summerlight

排序是计算机科学历史上最经过优化的操作之一。不要害怕排序。 - salezica

4个回答

3

这里有一个可能的优化方案：检查两个数组是否都具有max element <=32（或64，甚至16）。如果是，则填充两个该大小的位图（类型为uint32_t等），并使用二进制AND & 进行交集。如果不是，则采用排序方法。

或者，可以使用Briggs和Torczon提出的高效整数集表示法（详见此处），允许O（m + n）构造和O（min（m，n））交集的线性时间相交，而无需排序。这比使用哈希表更快，并且具有更好的边界。

- Fred Foo

1

为了确定两个集合的交集，您必须至少检查所有元素一次，这意味着最优解的类产生O（n + m），其中n是一个集合中的元素数量，m是另一个集合中的元素数量。

您可以通过使用哈希表来实现。鉴于您的项目是整数类型，您可以指望找到快速的哈希函数。一个简单的算法如下：

- 迭代第一个集合并将所有元素添加到哈希表中 - 迭代第二个集合，对于每个元素，检查它是否存在于哈希表中，如果存在，则将其添加到交集集合中或仅打印它。

假设您的哈希和哈希查找都是O（1），那么这将是O（n + m）。

鉴于您知道集合经常为空，您可以通过首先检查其中一个集合是否为空来进行优化。如果是这样，只需返回一个空集合。当然，前提是您知道计数并且可以在不迭代集合的情况下计算它。如果确实是这种情况，您可以进一步优化，始终首先读取和哈希较小的集合，以确保您的哈希表内存使用量将是两者中较小的那个。

- Ameen

另一个优化是，一旦您的交集集合达到两个集合中较小的大小，就可以停止检查。 - Ameen

感谢您的回答。我认为如果输入大小更大（100〜），使用哈希表会是一个很好的解决方案，但在我的情况下使用哈希表似乎太昂贵了，特别是在C++中（动态分配并不便宜）。 - summerlight

1

如果你期望每秒处理数百万次调用，那么你肯定不应该使用哈希表，我同意这一点。原问题中缺少了这个信息。 - Ameen

除了“快速退出”（如果集合为空等），考虑到您不希望超过10个元素，我会编写一个暴力方法。如果您在编译器中使用-O3及以上选项，则应该获得循环展开，这应该会带来显着的性能提升（只要集合的所有元素都适合一个缓存行，您就应该获得出色的性能）。 - Ameen

1

好的，由于您的数组很小，使用插入排序将是对这两个数组进行排序的最快方法，C++ STL也在数组小于16项时使用插入排序。然后，您可以使用这两个数组上的迭代器来比较和交叉数组。

可能还有其他算法可以更快地执行，但是对于每个数组3-4项的开销可能会太大。

- muhoweb

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

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

- Will · Accepted Answer

作为原始类型的数组，且长度足够短以适应缓存行，因此快速实现将专注于比较的战术机制而不是大O复杂度，例如避免使用哈希表，因为这通常涉及哈希和间接引用，并且总是涉及大量管理开销。

如果您有两个已排序的数组，则交集为O(n+m)。您说排序后再求交集是“暴力”，但您无法更快地完成它。

当然，如果数组已经按顺序存储，则可以进一步提高效率，因为您说您经常调用交集。

交集本身可以使用SSE完成。