3

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

  • 数组项的类型只是整数或类整数类型。
  • 大量时间（大约 30~40%？），一个或两个数组可能为空。
  • 数组通常非常小——通常是 1~3 个项目，我预计不会超过 10 个。
  • 交集函数会被非常频繁地调用。
  • 我不关心平台相关的解决方案 - 我正在研究 x86/windows/C++

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

4

4 回答 4

3

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

如果您有两个排序数组，则交集为 O(n+m)。你说 sort-then-intersect 是“蛮力”，但你不能更快地做到这一点。

当然，如果数组是按顺序存储的，那么正如您所说的经常调用交叉点，您会获得更多收益。

相交本身可以用 SSE 完成。

于 2013-02-05T07:39:08.163 回答
3

这是一个潜在的优化：检查两个数组的最大元素是否 <=32（或 64，甚至可能是 16）。如果是这样，则填充该大小的两个位图（类型uint32_t等）并使用二进制 AND 相交，&. 如果不是，请诉诸排序。

或者，不用排序，而是使用由于 Briggs 和 Torczon 的高效整数集表示，它允许线性时间与 O( m + n ) 构造相交并且 O(min( m , n )) 相交。这应该比具有比排序更好边界的哈希表快得多。

于 2013-02-05T07:42:29.170 回答
1

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

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

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

假设你的散列和你的散列查找是 O(1)，这将是 O(n + m)。

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

于 2013-02-05T07:33:46.047 回答
1

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

可能还有其他算法会执行得更快，但是这些算法的开销对于每个数组 3-4 个项目来说可能太大了。

于 2013-02-05T07:39:40.310 回答