快捷導(dǎo)航

淺談c++性能測(cè)試工具之計(jì)算時(shí)間復(fù)雜度

更新時(shí)間：2021年06月03日 11:48:46 作者：apocelipes

有時(shí)候除了測(cè)量算法的具體性能指數(shù)，我們也會(huì)希望測(cè)試出算法的時(shí)間復(fù)雜度，以便我們對(duì)待測(cè)試的算法的性能有一個(gè)更加直觀的了解。本文將介紹c++性能測(cè)試工具之計(jì)算時(shí)間復(fù)雜度。

google benchmark已經(jīng)為我們提供了類似的功能，而且使用相當(dāng)簡單。

具體的解釋在后面，我們先來看幾個(gè)例子，我們?nèi)藶橹圃鞄讉€(gè)時(shí)間復(fù)雜度分別為O(n), O(logn), O(n^n)的測(cè)試用例：

// 這里都是為了演示而寫成的代碼，沒有什么實(shí)際意義
static void bench_N(benchmark::State& state)
{
    int n = 0;
    for ([[maybe_unused]] auto _ : state) {
        for (int i = 0; i < state.range(0); ++i) {
            benchmark::DoNotOptimize(n += 2); // 這個(gè)函數(shù)防止編譯器將表達(dá)式優(yōu)化，會(huì)略微降低一些性能
        }
    }
    state.SetComplexityN(state.range(0));
}
BENCHMARK(bench_N)->RangeMultiplier(10)->Range(10, 1000000)->Complexity();

static void bench_LogN(benchmark::State& state)
{
    int n = 0;
    for ([[maybe_unused]] auto _ : state) {
        for (int i = 1; i < state.range(0); i *= 2) {
            benchmark::DoNotOptimize(n += 2);
        }
    }
    state.SetComplexityN(state.range(0));
}
BENCHMARK(bench_LogN)->RangeMultiplier(10)->Range(10, 1000000)->Complexity();

static void bench_Square(benchmark::State& state)
{
    int n = 0;
    auto len = state.range(0);
    for ([[maybe_unused]] auto _ : state) {
        for (int64_t i = 1; i < len*len; ++i) {
            benchmark::DoNotOptimize(n += 2);
        }
    }
    state.SetComplexityN(len);
}
BENCHMARK(bench_Square)->RangeMultiplier(10)->Range(10, 100000)->Complexity();

如何傳遞參數(shù)和生成批量測(cè)試我們?cè)谏弦黄呀?jīng)介紹過了，這里不再重復(fù)。

需要關(guān)注的是新出現(xiàn)的state.SetComplexityN和Complexity。

首先是state.SetComplexityN，參數(shù)是一個(gè)64位整數(shù)，用來表示算法總體需要處理的數(shù)據(jù)總量。benchmark會(huì)根據(jù)這個(gè)數(shù)值，再加上運(yùn)行耗時(shí)以及state的迭代次數(shù)計(jì)算出一個(gè)用于后面預(yù)估*均時(shí)間復(fù)雜度的值。

Complexity會(huì)根據(jù)同一組的多個(gè)測(cè)試用例計(jì)算出一個(gè)較接*的*均時(shí)間復(fù)雜度和一個(gè)均方根值，需要和state.SetComplexityN配合使用。

Complexity還有一個(gè)參數(shù)，可以接受一個(gè)函數(shù)或是benchmark::BigO枚舉，它的作用是提示benchmark該測(cè)試用例的時(shí)間復(fù)雜度，默認(rèn)值為benchmark::oAuto，測(cè)試中會(huì)自動(dòng)幫我們計(jì)算出時(shí)間復(fù)雜度。對(duì)于較為復(fù)雜的算法，而我們又有預(yù)期的時(shí)間按復(fù)雜度，這時(shí)我們就可以將其傳給這個(gè)方法，比如對(duì)于第二個(gè)測(cè)試用例，我們還可以這樣寫：

static void bench_LogN(benchmark::State& state)
{
    // 中間部分與前面一樣，略過
}
BENCHMARK(bench_LogN)->RangeMultiplier(10)->Range(10, 1000000)->Complexity(benchmark::oLogN);

在選擇正確的提示后對(duì)測(cè)試結(jié)果幾乎沒有影響，除了偏差值可以降得更低，使結(jié)果更準(zhǔn)確。

Complexity在計(jì)算時(shí)間復(fù)雜度時(shí)會(huì)保留復(fù)雜度的系數(shù)，因此，如果我們發(fā)現(xiàn)給出的提示的時(shí)間復(fù)雜度前的系數(shù)過大的話，就意味著我們的預(yù)估發(fā)生了較大的偏差，同時(shí)它還會(huì)計(jì)算出RMS值，同樣反應(yīng)了時(shí)間復(fù)雜度的偏差情況。

運(yùn)行我們的測(cè)試：