浅谈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.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值，同样反应了时间复杂度的偏差情况。

运行我们的测试：

可以看到，自动的时间复杂度计算基本是准确的，可以在我们对算法进行测试时提供一个有效的参考。

以上就是浅谈c++性能测试工具之计算时间复杂度的详细内容，更多关于c++性能测试工具之计算时间复杂度的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++找出字符串中出现最多的字符和次数,时间复杂度小于O(n^2)

    已知字符串"aabbbcddddeeffffghijklmnopqrst"编程找出出现最多的字符和次数,要求时间复杂度小于O(n^2) /******************************************************** Copyright (C), 2016-2017, FileName: main9 Author: woniu201 Description:求字符串中出现次数最多的字符和次数 ******************************

  • C++实现的O(n)复杂度内查找第K大数算法示例

    本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法.分享给大家供大家参考,具体如下: 题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积. 从题目我们知道只有两种结果存在: 1)三个最大的正整数相乘: 2)一个最大的正整数和两个最小的负数相乘. 所以我们需要找出数组中最大的三个数的乘积m,然后与数组中最小的两个数相乘再与最大的数相乘的结果n,然后比较m,n,选出最大的数即为最终的结果. 参考代码:http://www.jb51.net/artic

  • 浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存

    LRU:Least Recently Used最近最少使用,当缓存容量不足时,先淘汰最近最少使用的数据.就像JVM垃圾回收一样,希望将存活的对象移动到内存的一端,然后清除其余空间. 缓存基本操作就是读.写.淘汰删除. 读操作时间复杂度为O(1)的那就是hash操作了,可以使用HashMap索引 key. 写操作时间复杂度为O(1),使用链表结构,在链表的一端插入节点,是可以完成O(1)操作,但是为了配合读,还要再次将节点放入HashMap中,put操作最优是O(1),最差是O(n). 不少童鞋就

  • Python算法中的时间复杂度问题

    在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度.顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量算法占用的内存空间. 本文将从时间复杂度的概念出发,结合实际代码示例分析算法的时间复杂度. 渐进时间复杂度 时间复杂度是算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个算运行时间是比较困难的,所以通常关注的是时间频度,即算法运行计算操作的次数,记为T(n),其中n称为问题的规模. 同样,因为n是一个变量,n发生变化时

  • 科学知识：时间复杂度计算方法

    一.定义 (1)如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的"时间复杂性".我们常用大O表示法表示时间复杂性,称之为大O记法. (2)一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法.常见的时间复杂度高低顺序如下: O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n

  • php 常用算法和时间复杂度

    按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3) 复制代码 代码如下: //二分查找O(log2n)function erfen($a,$l,$h,$f){    if($l >$h){ return false;}    $m = intval(($l+$h)/2);    if ($a[$m] == $f){        return $m;    }elseif ($f < $

  • PHP 巧用数组降低程序的时间复杂度

    关于作者 王丹丹 , IBM 中国系统与技术中心软件工程师,自从 2006 年加入 IBM,一直从事 Web 系统设计和开发工作,有五年 PHP 应用程序设计开发经验. 通常开发人员在写程序的时候,往往是把已经设计好或者构思好的运算逻辑,直接用编程语言翻译出来.程序能顺利编译通过,那是很令人高兴的事情.如果此时程序的运行时间还能接受,就会沉浸在写代码的成就感当中,常常在这个过程中忽略代码的优化.只有当程序运行速度受到影响时,才回过头去考虑优化的事情.本文主要是介绍在 PHP的编程中,如何巧用数组

  • Java算法之时间复杂度和空间复杂度的概念和计算

    Java算法之时间复杂度和空间复杂度的概念和计算

    一.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间. 在计算机发展的早期,计算机的存储容量很小.所以对空间复杂度很是在乎.但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度.所以我们如今已经不需要再特别关注一个算法的空间复杂度.因为现在的内存不像以前那么贵,所以经常听到过牺牲空间来换取时间的说法 二.时间复杂度 2.1

  • PHP 用数组降低程序的时间复杂度

    PHP 用数组降低程序的时间复杂度

    而随着设备硬件配置的不断提升,对中小型应用程序来说,对算法的空间复杂度的要求也宽松了不少.不过,在当今 Web2.0 时代,对应用程序的时间复杂度却有了更高的要求. 什么是算法的时间复杂度呢?概要来说,是指从算法中选取一个能代表算法的原操作,以原操作重复执行的次数作为算法的时间量度.影响时间复杂度的因素有两个:一是原操作的执行时间,二是原操作因控制结构引起的执行次数.要把算法的时间复杂度降下来,降低原操作的执行次数是较为容易的方法,也是主要方法.本文所讲述的方法,是通过巧用 PHP 的数组,降低

  • 浅谈c++性能测试工具之计算时间复杂度

    浅谈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 <

  • 浅谈c++性能测试工具google benchmark

    浅谈c++性能测试工具google benchmark

    一.测试对象 这次测试的对象是标准库的vector,我们将会在vs2019 16.10和Linux + GCC 11.1上进行测试.为了代码写着方便,我还会启用c++17支持. 这次的疑问来自于<A Tour of C++>这本书,最近在重新翻阅本书的时候发现书里第九章给出了一个很有意思的建议:尽量少用reserve方法. 我们都知道reserve会提前分配足够大的内存来容纳元素,这样在push_back时可以减少内存分配和元素移动的次数,从而提高性能.所以习惯上如果我们知道vector中存储

  • 浅谈webpack构建工具配置和常用插件总结

    webpack构建工具已经火了好几年,也是当下狠火狠方便的构建工具,我们没有理由不去学习.既然选择webpack就要跟着时代走,我们要追随大牛的步伐,大牛等等我. 一.webpack基础 在根目录使用npm init 命令创建package.json,创建过程中一路回车. 本地安装webpack命令:npm install webpack webpack-cli --save-dev 安装成功后写入package.js的devDependencies中,可以通过 npm node_modules

  • 浅谈JDK14性能管理工具之jmap和jhat

    浅谈JDK14性能管理工具之jmap和jhat

    简介 jmap(Java Memory Map)是JDK自带的工具,用来将某个java程序的内存中的信息打印或者输出到文件中,然后通过jhat(Java Heap Analysis Tool)工具对输出的文件进行分析,从而找到可能出现的问题. 接下来进入我们的jmap和jhat之旅吧. jmap jmap -clstats <pid>     to connect to running process and print class loader statistics jmap -finali

  • 浅谈iOS 关于小数精确计算（NSDecimalNumber）

    做了好一段时间的金融产品,对数字是要非常敏感,差个零点零几都不行,精确度是要非常重视的,将后台传给我的floatValue转成NSString,一直没发现问题,最近项目有关个人账户的资产显示,发现总是和web和android有点误差,百思不得其解,在Stack Overflow上面问了一下,发现了NSDecimalNumber这个API,这个类为OC程序提供定点算法功能,它被设计不会损失精度并且可预先设置凑整规则的10进制计算,它比浮点数更好去表达货币,作为代价,它的计算相对复杂,相对耗时. 举

  • 浅谈Xcode 开发工具 XCActionBar

    浅谈Xcode 开发工具 XCActionBar

    XCActionBar 是一个用于 Xcoded 的通用生产工具. 下载地址:https://github.com/pdcgomes/XCActionBar 基本命令: (1)「command+shift+8」或者双击「command」键可以打开「动作输入框窗口」 (2)「command+option+7」或者双击「alt」键可以执行「上次的动作」 编程时可用于双击或三击事件的按键分别为如下5个: (1)「alt」:NSAlternateKeyMask (2)「command」:NSComman

  • 浅谈python中的数字类型与处理工具

    浅谈python中的数字类型与处理工具

    python中的数字类型工具 python中为更高级的工作提供很多高级数字编程支持和对象,其中数字类型的完整工具包括: 1.整数与浮点型, 2.复数, 3.固定精度十进制数, 4.有理分数, 5.集合, 6.布尔类型 7.无穷的整数精度 8.各种数字内置函数及模块. 基本数字类型 python中提供了两种基本类型:整数(正整数金额负整数)和浮点数(注:带有小数部分的数字),其中python中我们可以使用多种进制的整数.并且整数可以用有无穷精度. 整数的表现形式以十进制数字字符串写法出现,浮点数带

  • 浅谈常用字符串与集合类转换的工具类

    在项目中,我们经常需要把接收到的字符串转换成对应的集合类保存,或者把集合类转换成字符串以方便传输,这个工具类中封装了几个常用的方法,对于这种转换需求十分方便. import java.util.Arrays; import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Properties; import java.u

  • 浅谈Android Studio 3.0 工具新特性的使用 Android Profiler 、Device File Explorer

    浅谈Android Studio 3.0 工具新特性的使用 Android Profiler 、Device File Explorer

    前言: 其实 studio3.0的工具大家也已经使用过一段时间了,自己呢,就是从bate版开始使用的,我觉得比较好用的几个地方.就几个,可能还没用到其他的精髓. 但我觉的这个两个功能对我是比较实用的.好那么下面就给大家介绍一下吧. 正文: 话不多说咱们直接上图吧.(个人比较喜欢看图说话) 第一个(Android Profiler)我要介绍的就是这个了.(先看一下效果"震撼一下") (图-1) (图-2) (图-3) (厉害不厉害,牛逼不牛逼)那么我们怎么来操作这个工具呢,来咱们接着看图

随机推荐