c++성능 테스트 도구 의 계산 시간 복잡 도

google benchmark 는 이미 우리 에 게 유사 한 기능 을 제공 하 였 으 며,사용 은 상당히 간단 하 다.
구체 적 인 설명 은 뒤에 있 습 니 다.우 리 는 먼저 몇 가지 예 를 살 펴 보 겠 습 니 다.우 리 는 몇 가지 시간 복잡 도 를 만 들 기 위해 각각 O(n),O(logn),O(n^n)의 테스트 사례 를 만 들 었 습 니 다.

//               ，        
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); //                ，         
        }
    }
    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();

어떻게 파 라 메 터 를 전달 하고 대량 테스트 를 생 성 하 는 지 우 리 는 지난 편 에서 이미 소개 하 였 으 며,여 기 는 더 이상 반복 되 지 않 습 니 다.
주목 해 야 할 것 은 새로 생 긴 state.SetComplexity N 과 Complexity 다.
먼저 state.SetComplexityN 이 고 매개 변 수 는 64 비트 정수 로 알고리즘 이 전체적으로 처리 해 야 할 데이터 총량 을 나타 낸다.benchmark 는 이 수치 에 따라 운행 시간 과 state 의 교체 횟수 에 따라 뒤의 예측*평균 시간 복잡 도 를 계산 합 니 다.
Complexity 는 같은 그룹의 여러 테스트 사례 에 따라 비교적 연 결 된*평균 시간 복잡 도와 평균 각 근 값 을 계산 하여 state.SetComplexity N 과 함께 사용 해 야 합 니 다.
Complexity 는 또 하나의 매개 변 수 를 받 아들 일 수 있 습 니 다.함수 나 benchmark:BigO 매 거 진 은 benchmark 이 테스트 사례 의 시간 복잡 도 를 알려 주 는 역할 을 합 니 다.기본 값 은 benchmark::oAuto 입 니 다.테스트 에서 시간 복잡 도 를 자동 으로 계산 해 줍 니 다.비교적 복잡 한 알고리즘 에 대해 우 리 는 예상 한 시간 을 복잡 도 에 따라 이 방법 을 전달 할 수 있다.예 를 들 어 두 번 째 테스트 사례 에 대해 우 리 는 이렇게 쓸 수 있다.

static void bench_LogN(benchmark::State& state)
{
    //          ，  
}
BENCHMARK(bench_LogN)->RangeMultiplier(10)->Range(10, 1000000)->Complexity(benchmark::oLogN);

정확 한 힌트 를 선택 한 후 테스트 결과 에 거의 영향 을 주지 않 으 며 편차 값 을 제외 하고 결 과 를 더욱 정확하게 낮 출 수 있다.
Complexity 는 시간 복잡 도 를 계산 할 때 복잡 도의 계 수 를 유지 하기 때문에 우리 가 제시 한 시간 복잡 도 전의 계수 가 너무 크다 는 것 을 발견 하면 우리 의 예상 에 비교적 큰 편차 가 발생 한 것 을 의미 하 는 동시에 RMS 값 도 계산 하여 시간 복잡 도의 편차 상황 을 똑 같이 반영 한다.
테스트 실행:

이 를 통 해 알 수 있 듯 이 자동 적 인 시간 복잡 도 계산 은 기본적으로 정확 하고 우리 가 알고리즘 을 테스트 할 때 효과 적 인 참 고 를 제공 할 수 있다.
이상 은 c++성능 테스트 도구 의 계산 시간 복잡 도 에 대한 상세 한 내용 입 니 다.c+성능 테스트 도구 의 계산 시간 복잡 도 에 관 한 자 료 는 다른 관련 글 에 주목 하 십시오!