浅谈c++性能测试工具之计算时间复杂度
作者:apocelipes 发布时间:2023-07-09 12:40:05
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.SetComplexityN和Complexity。
首先是state.SetComplexityN,参数是一个64位整数,用来表示算法总体需要处理的数据总量。benchmark会根据这个数值,再加上运行耗时以及state的迭代次数计算出一个用于后面预估*均时间复杂度的值。
Complexity会根据同一组的多个测试用例计算出一个较接*的*均时间复杂度和一个均方根值,需要和state.SetComplexityN配合使用。
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值,同样反应了时间复杂度的偏差情况。
运行我们的测试:
可以看到,自动的时间复杂度计算基本是准确的,可以在我们对算法进行测试时提供一个有效的参考。
来源:https://www.cnblogs.com/apocelipes/p/11108483.html
猜你喜欢
- 前言之前我们提到了 CustomPaint er 的 Paint 可以使用渐变(GradientShader)来填充绘制的图形,本篇我们来介
- 一般而言,Android 应用在请求数据时都是以 Get 或 Post 等方式向远程服务器发起请求,那你有没有想过其实我们也可以在 Andr
- 本文实例讲述了C#启动进程的几种常用方法。分享给大家供大家参考。具体如下:1.启动子进程,不等待子进程结束private void simp
- ImageCacheconst int _kDefaultSize = 1000;const int _kDefaultSizeBytes
- 您已经看到很多包含视频内容的应用程序,比如带有视频教程的食谱应用程序、电影应用程序和体育相关的应用程序。您是否想知道如何将视频内容添加到您的
- 1、右值1.1 简介首先区分一下左右值:左值是指存储在内存中、有明确存储地址(可取地址)的数据;右值是指可以提供数据值的数据(不可取地址)如
- 目录多选和单选的不同之处实现方式界面变更代码实现总结多选和单选的不同之处单选的时候,选中一个就可以直接把结果返回,因此本身底部弹窗无需状态管
- 前言通过此篇文章,你将了解到:Flutter windows和Android桌面应用屏幕适配的解决方案;屏幕适配的相关知识和原理;flutt
- 本文实例为大家分享了Unity实现场景漫游相机的具体代码,供大家参考,具体内容如下前言拿到场景后总喜欢在场景里面玩一段时间,那这个脚本就是你
- 一、写在前面数据结构中的队列应该是比较熟悉的了,就是先进先出,因为有序故得名队列,就如同排队嘛,在对尾插入新的节点,在对首删除节点.jdk集
- MediaQuery通常情况下,不会直接将MediaQuery当作一个控件,而是使用MediaQuery.of获取当前设备的信息,用法如下:
- 先上图下拉刷新跟原生开发一样,下拉刷新在flutter里提供的有组件实现 RefreshIndicator一直不明白为啥组件中都提供下拉刷新
- 最近“全网域(Web Scale)”一词被炒得火热,人们也正在通过扩展他们的应用程序架构来使他们的系统变得更加“全网域”。但是究竟什么是全网
- 在使用springMVC框架构建web应用,客户端常会请求字符串、整型、json等格式的数据,通常使用@ResponseBody注解使 co
- 一、百度百科Sentinel 是面向分布式服务架构的高可用流量防护组件,主要以流量为切入点,从限流、流量整形、熔断降级、系统负载保护、热点防
- BitArray的基础可以看菜鸟编程BitArray 类管理一个紧凑型的位值数组,它使用布尔值来表示,其中 true 表示位是开启的(1),
- 介绍Spring Cache是一个框架,实现了基于注解的缓存功能,只需要简单地加一个注解,就能实现缓存功能。Spring Cache提供了一
- 因为mybatis好使,所以几乎需要操作数据库的时候,我都会使用mybatis,而且在一个正式的项目中,同时存在BS和CS的程序,都使用的M
- 1、取得控制台应用程序的根目录方法方法1、Environment.CurrentDirectory 取得或设置当前工作目录的完整限定路径方法
- 实现方案:我们直接参考实例代码:private String pattern = "((http|ftp