如何并行化此 C++ 代码以尽可能减少运行时间？

Question

我正在尝试尽可能减少这段代码的运行时间。我从来没有用C++做过并行化。我非常感谢您帮助解决这个问题。我可以在 64 位 Windows 计算机上的 VSCode 或 CodeLite 上运行代码。

#include <math.h>
#include <cmath>
#include <stdio.h>

int main()
{
    const unsigned long long int MAXVAL = 100000;
    unsigned long long int a;
    for (a = 1; a <= MAXVAL; a++)
    {
        unsigned long long int b;
        for (b = a + 1; b <= MAXVAL; b++)
        {
            unsigned long long int c;
            for (c = b + 1; c <= MAXVAL; c++)
                {
                    unsigned long long int d = MAXVAL - a - b - c;
                    if ( a*a + b*b + c*c == d*d )
                        {
                            printf("a=%lld, b=%lld, c=%lld, d=%lld\n",a,b,c,d);
                        }
                }

        }
    }
    return 0;
}

Answer 1

为了并行化代码，提取一个函数并为最外循环生成不同的线程，限制更小，例如for 2 个线程（您也可以在 for 循环中生成线程并将它们添加到列表中）：

const unsigned long long int MAXVAL = 100000;
void Calc(long int aStart, aEnd){
    unsigned long long int a;
    for (a = 1; a <= aEnd; a++)
    {
        unsigned long long int b;
        for (b = a + 1; b <= MAXVAL; b++)
        {
            unsigned long long int c;
            for (c = b + 1; c <= MAXVAL; c++)
                {
                    unsigned long long int d = MAXVAL - a - b - c;
                    if ( a*a + b*b + c*c == d*d )
                        {
                            printf("a=%lld, b=%lld, c=%lld, d=%lld\n",a,b,c,d);
                        }
                }

        }
    }
}

int main(int argc, char* argv[]){
    int step = MAXVAL/2;
    long int begin = 1;
    long int end = begin + step;
    std::thread t1(Calc, begin, end);
    begin = end;
    end = begin + step;
    std::thread t2(Calc, begin, end);
    t1.join();
    t2.join();
}

但是如果你想要最快的结果，你可以做一些优化。

• a*a

  和

  b*b

  计算非常频繁，计算一次并重复使用结果。

• d = MAXVAL - a - b - c;

  a*a + b*b + c*c == d*d

  可以表示为二次方程，可以求解和解析。因此，如果结果 (

  c

  ) 是整数或不是整数，整个内部循环可以用检查来替换。