性能优化-函数性能度量及分析工具

xhcoding

问题

度量下面累加程序的性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <vector>
#include <random>
#include <limits>

using namespace std;

int64_t Accumulate(vector<int64_t>& arr)
{
    int64_t sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];
    }
    return sum;
}

vector<int64_t> RandGenerator(int n)
{
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> distrib(numeric_limits<int32_t>::min(), numeric_limits<int32_t>::max());

    vector<int64_t> ans(n);
    for (int i = 0; i < ans.size(); i++) {
        ans[i] = distrib(gen);
    }
    return ans;
}

int main(int argc, char* argv[]) {

    auto arr = RandGenerator(1'000'000'000);

    auto sum = Accumulate(arr);


    return 0;
}

程序运行时间

最直观的度量方法就是程序运行的时间，可以使用 C++ 标准库 <chrono> 中的 high_resolution_clock 来测量。

阅读全文

函数的机器级表示

xhcoding

概念

函数提高了一种封装代码的方式，它可以被多次调用，调用完成后会返回调用点，可选的它可以接收多个参数，返回一个值。

运行时栈

栈是后进先出的数据结构，系统在程序运行时会分配一块内存区域以栈的方式管理，这块内存区域就叫运行时栈或栈内存空间。

阅读全文

字节序之大小端

xhcoding

内存以字节为单位保存信息，每个字节都有一个编号，这个编号就是内存地址。

一个 int a = 0x12345678 变量占用 4 个字节，而变量的地址为变量 a 在内存中的最低地址，比如 &a 为 0x100 时，说明 a 在内存中的位置为 0x100 0x101 0x102 0x103 。

阅读全文

枚举算法技巧

xhcoding

枚举算法即遍历已有的集合，判断哪些元素符合要求，最终求解问题。

例如 LeetCode 第一题，两数之和：

1
2
3
4
5
6
7

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

示例 1：

  输入：nums = [2,7,11,15], target = 9
  输出：[0,1]
  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

暴力枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return { 0, 0 };
    }
};

时间复杂度：\(O(N^2)\) ，空间复杂度：\(O(1)\)

阅读全文

C++ 奇异的递归模板 CRTP

xhcoding

CRTP (The Curiously Recurring Template Pattern) 是 C++ 模板中的一种习惯用法：子类继承时将自己作为基类的模板参数。

一般形式：

1
2
3
4
5
6
7
8

template <typename T>
class Base {

};

class Derived: public Base<Derived> {

};

这样就能在基类访问子类的成员变量及函数。

阅读全文