在 C++ 中加速嵌套循环

Question

我有以下一段 C++ 代码。问题的规模是 N 和 M。在我的机器上运行代码大约需要两分钟。（在 g++ -O3 编译之后）。无论如何在同一台机器上进一步加速它？任何一种选择，选择更好的数据结构、库、GPU 或并行性等，都摆在桌面上。

void demo() {
    int N = 1000000;
    int M=3000;
    vector<vector<int> > res(M);
    for (int i =0; i <N;i++) {
       for (int j=1; j < M; j++){
           res[j].push_back(i);
       }
    }
}


int main() {
  demo();
  return 0;
}

附加信息：上面的第二个循环for (int j=1; j < M; j++)是实际问题的简化版本。实际上，对于（外循环的）每个 i，j 可以在不同的范围内，但迭代次数约为 3000。

Answer 1

使用编写此答案时显示的确切代码，您可以创建具有特定大小的内部向量一次，然后调用iota进行初始化。然后只需将此向量传递给外部向量构造函数即可将其用于每个元素。

然后您根本不需要任何显式循环，而是使用（高度优化的，希望是）标准库为您完成所有工作。

也许是这样的：

void demo()
{
    static int const N = 1000000;
    static int const M = 3000;

    std::vector<int> data(N);
    std::iota(begin(data), end(data), 0);

    std::vector<std::vector<int>> res(M, data);
}