c++ - 为什么循环中耗时与迭代次数不成正比

Question

我写了下面的代码

#define TimeCode(Code) \
{\
    clock_t t1 = clock();\
    Code \
    clock_t t2 = clock();\
    double elapsed = (t2 - t1) * 1.0 / CLOCKS_PER_SEC;\
    std::cout << "Elapsed time " << elapsed << " sec" << std::endl; \
}

void loop(int nz)
{
    for (int i = 0; i < 5400; i++)
    {
        for (int j = 0; j < 5400; j++)
            for (int k = 0; k < nz; k++)
                ;
    }
}

int main(int argc, char* argv[])
{

    TimeCode(loop(17);)
    TimeCode(loop(34);)
    TimeCode(loop(649);)

    return 0;
}

我用 g++ -o main main.cpp 编译了它。结果是

Elapsed time 0.85579 sec
Elapsed time 3.14095 sec
Elapsed time 53.7562 sec

那为什么运行时间与循环大小不成正比呢？

Answer 1

由于你的循环结构，它不能严格成比例:对于 loop(n)，你执行:

• i 的一次初始化，5400 次增量和 i 的比较
• j 的 5400 次初始化，j 的 5400*5400 次增量和比较
• k 的 5400*5400 初始化，k 的 5400*5400*n 增量和比较

这是 29 165 401 次固定初始化，29 165 400 次固定增量和比较，以及 29 160 000 * n 次迭代和比较。所以你无法获得比例时间。

如果你想要更成比例的东西，你应该让k循环在外面:

void loop(int nz)
{
    for (int k = 0; k < nz; k++)
        for (int i = 0; i < 5400; i++)
            for (int j = 0; j < 5400; j++)
                ;
}

我建议你切换到 chrono high resolution clock :

#define TimeCode(Code, n) \
{\
    high_resolution_clock::time_point t1 = high_resolution_clock::now();\
    Code (n);\
    high_resolution_clock::time_point t2 = high_resolution_clock::now();\
    double elapsed = duration_cast<milliseconds>(t2 - t1).count();\
    std::cout << "Elapsed time " << elapsed << " ms -> " << elapsed/n << std::endl; \
}

通过这两项更改，在我的 PC 上，在所有三种情况下，每次迭代的时间都在 72 到 73 毫秒之间。

三个结果之间测量的微小差异小于时钟分辨率不准确(在 Windows 平台上为 +/-15 毫秒)。考虑到这一点(但不准确取决于平台)，我将宏中的输出行更改为:

std::cout << "Elapsed time " << elapsed << " ms -> " << elapsed/n << " inaccuracy:" <<(elapsed-15)/n<<" - "<<(elapsed+15)/n<<std::endl; \

这里是最终结果: