c++ - 如何使用 `omp parallel` 或其他方式并行化 for 循环？

Question

假设我有三个整数 vector :

• 大小为 800 万个元素的 mainVect
• 大小为 150 万个元素的 vect1
• 大小为 150 万个元素的 vect2

我想运行下面的代码:

int i,j;
for ( i = 0; i < vect1.size(); i++)
{
    for ( j = 0; j < mainVect.size(); j++)
    {
        if (vect1[i] == mainVect[j])
        {
            vect2[i]++;             
        }
    }
}

花了很长时间还没有完成...如何加快运行速度，我有多处理器。作为尝试，我在前面的代码之前添加了以下句子(我读到它是并行运行的)

#pragma omp parallel for private(i, j) shared( mainVect, vect1, vect2)

但是还是慢...

如果我把 for 循环分成 4 个部分；例如，如何让这些 for 循环同时运行，例如

for ( i = 0; i < vect1.size()/4; i++)
{

}

for ( i = vect1.size()/4; i < vect1.size()/2; i++)
{

}
.... and so on

或任何其他方法...

附言: Windows google 云机器，n1-standard-4(4 个 vCPU，15 GB 内存).. 运行上述代码时 CPU 利用率仅为 27%。

Answer 1

800 万个整数不会占用太多空间。您可以使用 unordered_map 或其他一些高效的关联容器。

unordered_map<int, int> umap;
for (int v : mainVect) {
    umap[v]++;
}
for (int i = 0; i < vect1.size(); ++i) {
    if (umap.count(vect1[i])) {
        vect2[i] += umap[vect1[i]];
    }
}

这需要线性时间来填充非常快的 vect2。