两个 N^4 集合的快速交集

Question

我正在寻找一种算法，该算法返回两个给定的 N^4 列表/集合（更准确地说是 [|0;7|]^4）的交集（长度）。我不期望用特定的编程语言得到答案（我正在用 OCaml 来做，但由于这种语言不是很流行，我不期望用 Caml 编写答案......）。请注意，涉及大量预计算的解决方案（例如完全改变集合的结构）在我的例子中不是问题。

我尝试将 N^4 集视为经典整数集，然后使用内置集交集将它们相交（但这对于我的目的来说太慢了），并且我还尝试将它们视为 N^2 集以应用勒贝格快速 N^2 相交（这可能有效，但事实证明点不会在平面上非常随机地重新排列，从而使该算法效率相当低）。

Answer 1

尚不清楚您的绩效目标是什么。最多 4096 个元素的正常集合交集应该不会那么慢，至少对于通用集合上的交集来说是这样。通常，在我的计算机上使用 OCaml 标准集时，最坏的情况（将整个集与其自身相交）大约需要 70μs，而最好的情况（将两个空集相交）需要 6ns。特别是，仅计算 O(n) 中的长度并避免构建结果集似乎并不能提高最坏情况下的性能。

因此，我们正在研究通过将算法拟合到数据集来优化常数。由于您的集合最多有 4096 个元素，因此它们可以表示为长度为 4096/8 = 512 的字符串。 通过这种表示，两个集合的相交只需取两个字符串的逻辑

and

即可。我们可以通过动态计算长度来进一步优化：

 let inter x y =
    let r = ref 0 in
    for i = 0 to set_size - 1 do
      r := !r + popcount (Char.code x.[i] land Char.code y.[i])
    done;
    !r

这足以通过 popcount 的 OCaml 实现（计算字符中 1 位的数量）将计算时间减少到 200 ns。

更进一步是可能的，但那时我们需要利用更多的数据集结构，或者我们需要通过深入到 C 来使算法适合硬件，以便使用硬件

popcount

指令和矢量 SIMD 指令计算大批量字节上的逻辑 和 。

Answer 2

你应该通过将 4 元组转换为整数来获得免费的加速，所以我会继续这样做。只需简单地转换为八进制，每个组成部分都是一个单独的数字，应该可以做到并且相当快，因为它只是位移：

number = tuple[0] | tuple[1] << 3 | tuple[2] << 6 | tuple[3] << 9

关于交集，在大多数情况下，您将无法在两组中较小的一组中击败时间

O(n)

。如果您了解有关集合分布的任何信息，或者了解它们的独特性，我们也许能够提出一些启发式方法来加速实践中的交集。