c++ - 为什么插入相同数量的集合会根据不同的方法有不同的运行时间？

Question

我正在编写一个并行程序，将组合生成为 bool vector 形式。由于组合是使用线程生成的，因此我在每个线程完成其工作时将它们组合起来。

set<vector<bool>> Ci[T.size()];
//generate combinations in parallel and thread i add result in Ci[i]

start_time = omp_get_wtime();
set<vector<bool>> C;
for(int i=0;i<T.size();i++){
    cout << "i=" << i << "\t" << Ci[i].size() << endl;
    C.insert(Ci[i].begin(),Ci[i].end());//here combine them into a single set
}
end_time = omp_get_wtime();
total_time = end_time - start_time;
cout << " Total time:" <<total_time << endl;
cout <<  C.size();

线程总数 T.size() 会有所不同，但总组合(C 的大小)始终相同。例如，

Enter threads:10
i=0 1
i=1 144
i=2 4320
i=3 47040
i=4 229320
i=5 550368
i=6 672672
i=7 411840
i=8 115830
i=9 11440
Total time:36.641s
C's size :2042975

Enter threads:128
i=0 9
i=1 45
i=2 165
...
i=120   10
i=121   11
i=122   12
i=123   13
i=124   14
i=125   15
i=126   16
i=127   18
Total time:6.432s
C's size :2042975

我不明白的是，在这两种情况下，我都将相同数量的组合插入到 C 中。为什么所花费的时间不一样？

Answer 1

我们没有看到所有必要的信息，但我怀疑问题是由集大小分布不均引起的。插入的复杂度为 O(n log(m + n))，其中 n 是插入到 (C) 和 m 是插入集合的大小 (Ci[i])。

现在，考虑这两个集合共有 2^24 个元素。

情况 1:n=2^16，m=2^24-2^16

在这里，“big O”里面的术语变成了2^16 * log(2^24-2^16+2^16)，即2^16* 24。

情况 2:n=2^23，m=2^23

在这里，相同的术语是 2^23*24，比情况 1 多 2^7 倍。 p>

我的观点是，如果您“合并”具有相同元素总数 的两个集合，则运行时间可能在很大程度上取决于这些元素在它们之间的分布方式。

在您的第一个案例(10 个线程)中，集合大小的分布似乎更像案例 2(其中大多数具有相对较多的元素)。我们没有看到您的第二种情况(128 个线程)的完整数据，但是集合大小的分布似乎更加不均匀，因为显示的只有很少的元素。 (请注意，这可能表明您的并行计算负载平衡不佳。)