c++ - 计算 N 组交集的快速算法

Question

我有 n 个集合 A0,A2,...An-1 持有集合 E 的项目。

我将配置 C 定义为由 n 位组成的整数，因此 C 的值介于 0 和 2^n-1 之间。现在，我定义以下内容:

(C)   an item e of E is in configuration C 
       <=> for each bit b of C, if b==1 then e is in Ab, else e is not in Ab

例如，对于 n=3，配置 C=011 对应于 A0 和 A1 中但不在 A2 中的 E 项(NOT 很重要)

C[bitmap] 是集合中具有该存在/不存在模式的元素的计数。 C[001] 是A0 中不在任何其他集合中的元素数。

---

另一种可能的定义是:

(V)   an item e of E is in configuration V 
       <=> for each bit b of V, if b==1 then e is in Ab

例如，对于 n=3，(V) 配置 V=011 对应于 A0 和 A1 中的 E 项

V[bitmap] 是所选集合的交集的计数。(即位图所在的所有集合中有多少元素的计数true.) V[001] 是 A0 中元素的数量。 V[011] 是 A0 和 A1 中的元素数，无论它们是否也在 A2 中。

---

下图中，第一张图为集合A0、A1、A2的项目，第二张图为(C)配置的大小，第三张图为(V)配置的大小。

我还可以用两个 vector 之一表示配置:

C[001]= 5       V[001]=14
C[010]=10       V[010]=22
C[100]=11       V[100]=24
C[011]= 2       V[011]= 6
C[101]= 3       V[101]= 7
C[110]= 6       V[110]=10
C[111]= 4       V[111]= 4

我想要的是编写一个 C/C++ 函数，尽可能高效地将 C 转换为 V。一种天真的方法可能是以下显然在 O(4^n) 中的“transfo”函数:

#include <vector>
#include <cstdio>

using namespace std;

vector<size_t> transfo (const vector<size_t>& C)
{
    vector<size_t> V (C.size());

    for (size_t i=0; i<C.size(); i++)
    {
        V[i] = 0;

        for (size_t j=0; j<C.size(); j++)
        {
            if ((j&i)==i)  { V[i] += C[j]; }
        }
    }

    return V;
} 


int main()
{
    vector<size_t> C = { 
        /* 000 */  0,
        /* 001 */  5,
        /* 010 */ 10,
        /* 011 */  2,
        /* 100 */ 11,
        /* 101 */  3,
        /* 110 */  6,
        /* 111 */  4
    };

    vector<size_t> V = transfo (C);

    for (size_t i=1; i<V.size(); i++)  {  printf ("[%2ld]  C=%2ld   V=%2ld\n", i, C[i], V[i]);  }
}

我的问题是:是否有比将 vector C 转换为 vector V 的朴素算法更有效的算法？这种“好”算法的复杂度是多少？

请注意，我可能对任何 SIMD 解决方案感兴趣。

Answer 1

嗯，您正在尝试计算 2ⁿ 值，因此您不能比 O(2ⁿ) 做得更好。

天真的方法从观察到 V[X] 是通过固定 X 中的所有 1 位并迭代 0 位所在的所有可能值而获得的。例如，

V[010] = C[010] + C[011] + C[110] + C[111]

但这种方法对 V 的每个元素执行 O(2ⁿ) 次加法，产生的总复杂度为 O(4ⁿ)。

这是一个复杂度为 O(n × 2ⁿ) 的算法。我也很好奇 O(2ⁿ) 算法是否存在。

令 n = 4。让我们考虑一下 V 与 C 的完整表格。下表中的每一行对应一个 V 值，该值是通过将标有 * 的列相加计算得出的。 * 符号的布局可以很容易地从朴素的方法推导出来。

    |0000|0001|0010|0011|0100|0101|0110|0111||1000|1001|1010|1011|1100|1101|1110|1111
0000| *  | *  | *  | *  | *  | *  | *  | *  || *  | *  | *  | *  | *  | *  | *  | *  
0001|    | *  |    | *  |    | *  |    | *  ||    | *  |    | *  |    | *  |    | *  
0010|    |    | *  | *  |    |    | *  | *  ||    |    | *  | *  |    |    | *  | *  
0011|    |    |    | *  |    |    |    | *  ||    |    |    | *  |    |    |    | *  
0100|    |    |    |    | *  | *  | *  | *  ||    |    |    |    | *  | *  | *  | *  
0101|    |    |    |    |    | *  |    | *  ||    |    |    |    |    | *  |    | *  
0110|    |    |    |    |    |    | *  | *  ||    |    |    |    |    |    | *  | *  
0111|    |    |    |    |    |    |    | *  ||    |    |    |    |    |    |    | *  
-------------------------------------------------------------------------------------
1000|    |    |    |    |    |    |    |    || *  | *  | *  | *  | *  | *  | *  | *  
1001|    |    |    |    |    |    |    |    ||    | *  |    | *  |    | *  |    | *  
1010|    |    |    |    |    |    |    |    ||    |    | *  | *  |    |    | *  | *  
1011|    |    |    |    |    |    |    |    ||    |    |    | *  |    |    |    | *  
1100|    |    |    |    |    |    |    |    ||    |    |    |    | *  | *  | *  | *  
1101|    |    |    |    |    |    |    |    ||    |    |    |    |    | *  |    | *  
1110|    |    |    |    |    |    |    |    ||    |    |    |    |    |    | *  | *  
1111|    |    |    |    |    |    |    |    ||    |    |    |    |    |    |    | *  

请注意，左上角、右上角和右下角包含相同的布局。因此，我们可以批量执行一些计算，如下所示:

1. 计算表格的下半部分(右下角)。
2. 将值添加到上半部分。
3. 计算左上角。

如果我们让 q = 2ⁿ，则递归复杂度为

T(q) = 2T(q/2) + O(q)

使用 Master Theorem 求解到

T(q) = O(q log q)

或者，就n而言，

T(n) = O(n × 2ⁿ)