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

假设我有三个整数向量：


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 cloud计算机，n1-standard-4（4个vCPU，15 GB内存）..运行以上代码时，CPU利用率仅为27％。

最佳答案

使用线程是一种可能的解决方案。

但是主要问题是：您要解决什么问题？

如果我对它的理解正确，那么您正在计算vect1中某个元素在mainVect中出现的次数。由于您不需要知道位置，因此可以重新排列mainVect（的副本）。

我的方法是：


排序mainVect
将mainVect转换为包含“键”和出现次数的表
排序vect1并创建一个间接向量。迭代此间接向量会按升序给出“键”
现在您可以“合并”


此方法的复杂度为O（n log n）