如何测试两种算法并判定孰快？C++基准测试计时方法问询

嘿，这个问题我太有共鸣了！每次纠结选哪个实现方案的时候，复杂度分析经常卡壳——要么复杂度完全一样，要么输入规模小到常数因子直接主导性能，这时候基准测试真的是最靠谱的判断方式。我来给你好好讲讲怎么用C++做准确的计时，帮你选出更优的方案～

确实，当两个算法的时间复杂度相同（比如都是O(n)），或者输入数据规模很小的时候，常数因子会成为性能的关键。这些因子包括内存访问的局部性、指令流水线的效率、分支预测的友好度、甚至是编译器对代码的优化程度，这些都没法单纯通过复杂度分析看出来，必须跑实际测试才能知道。

下面给你分享几种常用的计时手段，从标准库到传统方法都有，按需取用：

1. 用C++11的<chrono>库（首推！跨平台+高精度） #

这是C++标准库提供的现代计时方式，精度高还跨平台，完全不需要依赖第三方库。直接上代码示例：

#include <iostream>
#include <chrono>
#include <vector>

// 你要测试的方案1
void schemeA(std::vector<int>& data) {
    for (size_t i = 0; i < data.size(); ++i) {
        data[i] = data[i] * 3 + 1;
    }
}

// 你要测试的方案2
void schemeB(std::vector<int>& data) {
    for (auto& num : data) {
        num = num * 3 + 1;
    }
}

int main() {
    // 构造贴近实际的测试数据
    std::vector<int> test_data(1000000, 5);
    // 复制一份数据，保证两个方案的输入完全一致
    auto data_copy = test_data;

    // 测试方案A
    auto start = std::chrono::high_resolution_clock::now();
    schemeA(test_data);
    auto end = std::chrono::high_resolution_clock::now();
    auto durationA = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "方案A 运行时间: " << durationA.count() << " 微秒\n";

    // 测试方案B
    start = std::chrono::high_resolution_clock::now();
    schemeB(data_copy);
    end = std::chrono::high_resolution_clock::now();
    auto durationB = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "方案B 运行时间: " << durationB.count() << " 微秒\n";

    return 0;
}

• 要点解释：
  • high_resolution_clock是当前系统能提供的精度最高的时钟，适合微秒甚至纳秒级的测试。
  • duration_cast可以把时间差转换成你需要的单位：microseconds（微秒）、milliseconds（毫秒）、nanoseconds（纳秒）都可以。
  • 一定要给两个测试方案完全相同的输入，比如上面用data_copy复制了一份数据，避免因为数据状态不同影响结果。

2. 重复测试取平均值，避免偶然误差 #

单次测试很容易受系统调度影响（比如突然有后台进程占用CPU），所以最好多跑几次取平均值，结果更可靠：

int main() {
    const int test_rounds = 1000; // 重复测试1000次
    std::vector<int> test_data(1000000, 5);

    // 测试方案A的平均时间
    std::chrono::microseconds total_durationA(0);
    for (int i = 0; i < test_rounds; ++i) {
        std::vector<int> temp = test_data; // 每次重置数据
        auto start = std::chrono::high_resolution_clock::now();
        schemeA(temp);
        auto end = std::chrono::high_resolution_clock::now();
        total_durationA += std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    }
    std::cout << "方案A 平均运行时间: " << total_durationA.count() / test_rounds << " 微秒\n";

    // 同样测试方案B...
    return 0;
}

如果你的函数运行时间特别短（比如几微秒），可以把测试次数加到几万次，这样平均值会更稳定。

3. 传统的clock()函数（兼容旧版本C++） #

如果你还在使用C++11之前的版本，可以用clock()函数，不过它的精度不如<chrono>：

#include <iostream>
#include <vector>
#include <time.h>

void schemeA(std::vector<int>& data) {
    // ... 实现同上
}

int main() {
    std::vector<int> test_data(1000000, 5);
    clock_t start = clock();
    schemeA(test_data);
    clock_t end = clock();
    double duration = static_cast<double>(end - start) / CLOCKS_PER_SEC;
    std::cout << "方案A 运行时间: " << duration << " 秒\n";
    return 0;
}

注意：clock()返回的是CPU时间（程序占用CPU的时间），不是墙上时间（实际流逝的时间），适合单线程程序的测试。

• 用生产环境的编译选项：测试时一定要开启和实际部署一样的优化（比如-O2或-O3），Debug模式下的代码没有优化，运行时间和Release模式完全不是一回事！而且要确保测试函数不会被编译器优化掉——如果你的函数没有副作用（比如只是计算不输出结果），可以把结果存到全局变量或者打印一部分，防止编译器把整个函数删掉。
• 测试数据要贴近实际：不要用全0、全1这种极端数据，尽量用和你业务场景中类似的数据，因为不同数据会影响分支预测、缓存命中率，进而影响性能。
• 隔离测试环境：测试的时候尽量关闭浏览器、视频播放器这些占用CPU的程序，避免系统干扰。
• 对比要绝对公平：两个测试方案的输入数据、编译选项、机器环境必须完全一致，这样对比出来的结果才有意义。

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