如何并行化该C++代码以最大限度缩短运行时间？

一、优先做算法优化（核心提速手段） #

原代码是三重循环，时间复杂度为(O(n^{3))，当`MAXVAL=100000`时，循环次数约为(1.6×10}{14})次，完全无法在合理时间内跑完。通过数学推导可将循环降为二重循环，复杂度降至(O(n^2))：

数学推导 #

已知条件：

• (a < b < c < d)
• (a + b + c + d = MAXVAL)
• (a² + b² + c² = d²)

将(d = MAXVAL - a - b - c)代入平方等式，展开并整理后可得：
[c = \frac{\frac{MAXVAL²}{2} - MAXVAL(a + b) + ab}{MAXVAL - a - b}]

只需遍历a和b，计算c后验证以下条件即可：

1. 分母(MAXVAL - a - b > 0)（保证c为正）
2. 分子能被分母整除（保证c是整数）
3. (c > b)且(MAXVAL - a - b - c > 0)（保证d > c，符合顺序要求）

优化后的串行代码 #

#include <stdio.h>

int main()
{
    const unsigned long long int MAXVAL = 100000;
    // MAXVAL必须为偶数，否则推导式中分子非整数，无解
    if (MAXVAL % 2 != 0) {
        printf("MAXVAL必须是偶数，否则无解\n");
        return 0;
    }
    const unsigned long long MAX_SQUARE_HALF = (MAXVAL * MAXVAL) / 2;

    // 缩小a的循环范围：a < b < c < d → 4a < MAXVAL
    for (unsigned long long a = 1; a < MAXVAL / 4; ++a) {
        // 缩小b的循环范围：b < c < d → 3b < MAXVAL - a
        for (unsigned long long b = a + 1; b < (MAXVAL - a)/3; ++b) {
            unsigned long long denominator = MAXVAL - a - b;
            if (denominator <= b) continue;

            unsigned long long numerator = MAX_SQUARE_HALF - MAXVAL * (a + b) + a * b;
            if (numerator <= 0 || numerator % denominator != 0) continue;

            unsigned long long c = numerator / denominator;
            if (c <= b) continue;

            unsigned long long d = MAXVAL - a - b - c;
            if (d <= c) continue;

            // 验证原等式，避免推导疏漏
            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;
}

二、并行化实现（基于优化后的代码） #

优化后的二重循环可通过OpenMP并行化，这是适合新手的轻量并行框架，Windows下VSCode和CodeLite均支持。

1. 代码修改（添加OpenMP指令） #

引入OpenMP头文件，给外层循环添加并行指令，同时处理线程安全的输出：

#include <stdio.h>
#include <omp.h> // 引入OpenMP头文件

int main()
{
    const unsigned long long int MAXVAL = 100000;
    if (MAXVAL % 2 != 0) {
        printf("MAXVAL必须是偶数，否则无解\n");
        return 0;
    }
    const unsigned long long MAX_SQUARE_HALF = (MAXVAL * MAXVAL) / 2;

    // 并行化外层循环，动态分配任务避免负载不均
    #pragma omp parallel for schedule(dynamic)
    for (unsigned long long a = 1; a < MAXVAL / 4; ++a) {
        for (unsigned long long b = a + 1; b < (MAXVAL - a)/3; ++b) {
            unsigned long long denominator = MAXVAL - a - b;
            if (denominator <= b) continue;

            unsigned long long numerator = MAX_SQUARE_HALF - MAXVAL * (a + b) + a * b;
            if (numerator <= 0 || numerator % denominator != 0) continue;

            unsigned long long c = numerator / denominator;
            if (c <= b) continue;

            unsigned long long d = MAXVAL - a - b - c;
            if (d <= c) continue;

            if (a*a + b*b + c*c == d*d) {
                // 临界区保证printf线程安全，避免输出混乱
                #pragma omp critical
                printf("a=%lld, b=%lld, c=%lld, d=%lld\n", a, b, c, d);
            }
        }
    }
    return 0;
}

2. 编辑器配置 #

VSCode配置

1. 安装支持OpenMP的MinGW-w64编译器。
2. 在.vscode/tasks.json的编译参数中添加-fopenmp：

   {
       "tasks": [
           {
               "type": "cppbuild",
               "label": "C/C++: g++.exe 生成活动文件",
               "command": "C:\\mingw64\\bin\\g++.exe",
               "args": [
                   "-fdiagnostics-color=always",
                   "-g",
                   "${file}",
                   "-o",
                   "${fileDirname}\\${fileBasenameNoExtension}.exe",
                   "-fopenmp" // 添加OpenMP编译参数
               ],
               "options": {"cwd": "${fileDirname}"},
               "problemMatcher": ["$gcc"],
               "group": {"kind": "build", "isDefault": true},
               "detail": "编译器: C:\\mingw64\\bin\\g++.exe"
           }
       ],
       "version": "2.0.0"
   }
   

CodeLite配置

1. 打开项目设置，进入“编译器”选项。
2. 在“编译选项”和“链接选项”中均添加-fopenmp参数。

三、额外优化建议 #

• 预计算MAX_SQUARE_HALF，避免循环内重复计算MAXVAL*MAXVAL。
• 若仅需统计结果数量而非输出，用#pragma omp atomic替代临界区计数，效率更高。

内容的提问来源于stack exchange，提问作者Rebel