C++ 性能骨灰级优化（推荐）

2022-10-08 16:23:03

文章目录

一、前言

  • 一款游戏上线分钱，它的奖金来源如下：
    奖 金 = 流 水 − 分 成 − 不 可 描 述 的 内 容 − 人 力 成 本 − 资 源 成 本 − 服 务 器 成 本 奖金 = 流水 - 分成 - 不可描述的内容 - 人力成本 - 资源成本 - 服务器成本 奖金=流水−分成−不可描述的内容−人力成本−资源成本−服务器成本
  • 前面几项我们做技术的都无法改变，但是服务器成本这块，我们是有责任和义务去减少的；
  • 所谓能省则省嘛，你的代码写的越高效，服务器执行效率越高，用到的服务器 CPU 核数越少、内存越少，就越省钱，那么今天就来讲讲怎么省钱吧~~
    （本文涉及的所有内容都不含有复杂算法，全部是简单易懂的内容，适合 C++ 零基础）
    C++ 性能骨灰级优化（推荐）

二、时间复杂度

1、定义

  • 在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O O O 符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

2、举例

  • 1）简单赋值语句（或表达式）的时间复杂度为： O ( 1 ) O(1) O(1)，如下：
	s = a[0];
  • 2）遍历一维数组的时间复杂度为： O ( n ) O(n) O(n)，如下：
	for(i = 0; i < n; ++i) {
		s += a[i];
	}
  • 3）遍历二维数组的时间复杂度为： O ( n 2 ) O(n^2) O(n2)，高维数组以此类推，如下：
	for(i = 0; i < n; ++i) {
		for(j = 0; j < n; ++j) {
			s += a[i][j];
		}
	}
  • 4）二分查找的时间复杂度为： O ( l o g n ) O(log_n) O(logn​)（下文说到的所有对数，都是以 2 2 2 为底）如下：
	l = 1, r = n;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(a[mid] <= v) {
			r = mid + 1;
		}else {
			l = mid + 1;
		}
	}
  • 5）斐波那契数列递归枚举的时间复杂度： O ( 2 n ) O(2^n) O(2n)，如下：
	int fib(unsigned int n) {
		if(n <= 1) {
			return n;
		}
		return fib(n-1) + fib(n-2);
	}
  • 6）深搜枚举全排列的时间复杂度： O ( n ! ) O(n!) O(n!)，如下：
int stk[MAXN], top, has[MAXN];

void dfs(int n, int depth) {
	int i;
	if (depth == n) {
		for (i = 0; i < n; ++i) {
			printf("%d", stk[i]);
		}
		puts("");
	}
	for (i = 0; i < n; ++i) {
		if (!has[i]) {
			has[i] = 1;
			stk[top++] = i+1;
			dfs(n, depth + 1);
			--top;
			has[i] = 0;
		}
	}
}
  • 7）各种情况嵌套以后形成的综合场景，比如 O ( n 2 n ) 、 O ( n l o g n ) 、 O ( n 2 l o g n ) O(n2^n)、O(nlog_n)、O(n^2log_n) O(n2n)、O(nlogn​)、O(n2logn​)，不再一一举例；

三、C++ 写法优化

1、查找时用键值对代替数组

1）哈希数组

【场景1】从长度为 n n n 的数组中查找某个数字是否存在

  • 利用枚举的方式，遍历所有元素进行判断，时间复杂度 O ( n ) O(n) O(n)，代码实现如下：
const int n = 100000;
void init() {
	for (int i = 0; i < n; ++i) {
		a[i] = 5 * i;
	}
}
bool find(int target) {
	for (int i = 0; i < n; ++i) {
		if (target == a[i]) {
			return true;
		}
	}
	return false;
}
  • 这个时间复杂度是会以乘法的形式累乘到调用方的时间复杂度上的，比如调用方调用 m m m 次，那么整体下来的时间复杂度就是 O ( m n ) O(mn) O(mn)，调用代码如下：
int countBy() {
	int cnt = 0, m = 100000;
	while(m--) {
		if (find(6857112) ) {  // 这里举了个最坏的例子，永远找不到的情况
			++cnt;
		}
	}
	return cnt;
}
  • 当 n = 100000 n = 100000 n=100000 时，调用 100000 100000 100000 次 f i n d find find 函数，最坏情况是一次都找不到，实测时间： 20313 m s 20313 ms 20313ms；
  • 所以是需要想办法优化的；

【优化1】利用哈希数组的索引来代替数组的遍历

  • 观察到数组里的数据都是整数，而且最大不会超过 500000 500000 500000，所以可以把数组的数据映射到一个最大为 500000 500000 500000 的哈希表中，查找的时候只需要利用下标索引，时间复杂度 O ( 1 ) O(1) O(1)，代码如下：
const int n = 100000;
void init() {
	memset(hashtbl, 0, sizeof(hashtbl));
	for (int i = 0; i < n; ++i) {
		hashtbl[ 5 * i ] = 1;
	}
}
bool find(int target) {
	return hashtbl[target];
}
  • 当 n = 100000 n = 100000 n=100000 时，调用 100000 100000 100000 次 f i n d find find 函数，实测时间： 0 m s 0ms 0ms；
  • 但是需要注意数组下标越界的问题，一旦越界就会导致程序崩溃或者让程序进入不确定性，安全性比较低；

2）map

【场景2】从长度为 n n n 的数组中查找某个字符串是否存在

  • 时间复杂度： O ( n ) O(n) O(n)
  • 实现代码类似【场景1】，不再累述；

【优化2】利用 STL 的 map 来代替数组的遍历

  • 观察到数组里的数据不是数字，无法直接映射到数组中，所以我们借助 S T L STL STL 的 m a p map map，查找的时间复杂度 O ( l o g n ) O(log_n) O(logn​)，代码如下：
const int n = 100000;
map<string, bool> maphash;

void init() {
	maphash.clear();
	for (int i = 0; i < n; ++i) {
		maphash[ str[i] ] = 1;
	}
}
bool find(string target) {
	return maphash.find(target) != maphash.end();
}
  • S T L STL STL 的 m a p map map 底层实现是红黑树，在进行查找的时候涉及的常数会比较大，再加上 k e y key key 是字符串，计算哈希函数的时间也要算上，所以实际的时间复杂度是 O ( C l o g n ) O(Clog_n) O(Clogn​)；
  • 当 n = 100000 n = 100000 n=100000 时，调用 100000 100000 100000 次 f i n d find find 函数，实测时间： 563 m s 563ms 563ms；

3）unordered_map

【优化3】利用 STL 的 unordered_map 来代替数组的遍历

  • u n o r d e r e d _ m a p unordered\_map unordered_map 的用法和 m a p map map 基本一致，代码不再累述；
  • u n o r d e r e d _ m a p unordered\_map unordered_map 底层实现是哈希表，同样如果 k e y key key 是字符串，也有常数运算在，总体来说效率优于 m a p map map，时间复杂度 O ( C ) O(C) O(C)；
  • 当 n = 100000 n = 100000 n=100000 时，调用 100000 100000 100000 次 f i n d find find 函数，实测时间： 157 m s 157ms 157ms；

4）效率排行总结

  • 效率排行： 哈 希 数 组 > u n o r d e r e d _ m a p > m a p > 数 组 哈希数组 > unordered\_map > map > 数组 哈希数组>unordered_map>map>数组；
  • 普适性排行： 数 组 > u n o r d e r e d _ m a p = = m a p > 哈 希 数 组 数组 > unordered\_map == map > 哈希数组 数组>unordered_map==map>哈希数组；
  • 安全性： u n o r d e r e d _ m a p = = m a p > 数 组 > 哈 希 数 组 unordered\_map == map > 数组 > 哈希数组 unordered_map==map>数组>哈希数组；

【思考题1】

  • 1）以下代码时间复杂度是多少？
  • 2）请想办法把它优化到 O ( n + m ) O(n+m) O(n+m)；
	int sum = 0;
    for (int i = 0; i < n; ++i) {
        for(int j = 0; j < m; j++) {
            if(A[i] == B[j]) {
                sum += (A[i] + B[j]);
            }
        }
    }

2、关注常数优化

  • 项目大了，写的人多了，尤其是各种交叉调用的逻辑，用别人接口的时候也关注下别人实现的时间复杂度，很多逻辑其实都是乘法逻辑，一层一层叠上来，数据量大了就很恐怖了。
  • 当然，提供接口的人也要多想想调用方会以什么方式来调用，如果什么都不考虑就写出 O ( n ) O(n) O(n) 或者 O ( n 2 ) O(n^2) O(n2) 时间复杂度的代码，这种情况下如果调用方对任何其中一个接口用法不正确，实现者至少也得负一部分责任。
  • 当外层循环大量嵌套的时候，内层的一个简单的逻辑可能会被调用千百万次，这时候一些基础接口已经到了无法优化的地步，就只能考虑常数优化了；

1）位运算

【场景3】计算某个玩家的属性的时候，有一步运算是除上2的幂取除数和余数

  • 基础四则运算中当属除法最为耗时，将除法单独提取出来，实现如下：
const int n = 3000000;
const int m = 30;

int doCount() {
	int s = 0, cnt = n;
	int pow2[MAXP] = { 1 };
	for (int i = 1; i < m; ++i) {
		pow2[i] = pow2[i - 1] * 2;
	}
	while (cnt --) {
		for (int i = 0; i < m; ++i) {
			s += rand() / pow2[i];
			s += (rand() % pow2[i]);
		}
	}
	return s;
}
  • 这个函数的时间复杂度 O ( n m ) O(nm) O(nm)，但是内层循环的 除法 和 取余 操作占据了大量时间，实测时间： 3406 m s 3406 ms 3406ms；
  • 这里有两个优化的点：
  • 1）对 2 的幂的除法可以用右移对应位数进行优化；
  • 2）对 2 的幂取余数可以用位与 2的幂减1 进行优化；

【优化4】利用位运算进行常数优化

const int n = 3000000;
const int m = 30;

int doCount() {
	int s = 0, cnt = n;
	int pow2[MAXP] = { 1 };
	for (int i = 1; i < m; ++i) {
		pow2[i] = pow2[i - 1] * 2;
	}
	while (cnt --) {
		for (int i = 0; i < m; ++i) {
			s += rand() >> i;
			s += rand() & (pow2[i]-1);
		}
	}
	return s;
}
  • 时间复杂度还是 O ( n m ) O(nm) O(nm)，但是将除法和取余替换成位运算后，实测时间： 2706 m s 2706 ms 2706ms；

【思考题2】

  • 利用位运算将以下代码缩减到 1 1 1 行；
int get(int x) {
	int c = 0;
	while (x % 2 == 0) {
		c++;
		x /= 2;
	}
	return (1 << c);
}

2）避免重复运算

【场景4】循环内部大量调用同一个函数，参数也相同

  • 实现代码如下：
    for (i = 0; i < n; ++i) {
        for(j = 0; j < m; j++) {
            int v = Cal(MAX_COUNT);
            A[i][j] = v * i + j;
        }
    }
  • 这里 C a l Cal Cal 函数的时间复杂度假设为 X X X，那么整个运算过程的时间复杂度就是 O ( n m X ) O(nmX) O(nmX)；
  • 观察发现， C a l Cal Cal 函数的计算和 i i i、 j j j 无关，所以可以提到循环外面来，修改后如下：

【优化5】改变运算顺序避免重复运算

    int v = Cal(MAX_COUNT);
    for (i = 0; i < n; ++i) {
        for(j = 0; j < m; j++) {
            A[i][j] = v * i + j;
        }
    }
  • 修改完后的时间复杂度为： O ( n m + X ) O(nm + X) O(nm+X)；

【思考题3】

  • 简化代码使之更加高效；
    for (i = 0; i < n; ++i) {
        for(j = 0; j < m; j++) {
            A[i][j] = Cal(i) + Del(j);
        }
    }

3）加法代替乘法

  • 乘法运算的效率低于加法运算，原因很好解释：你可以随便拿两个三位数在纸上试一下，乘法的运算步骤会比加法的运算步骤复杂得多；
  • 假设一个十进制数字位数为 n n n 位，加法的时间复杂度为 O ( n ) O(n) O(n)，乘法则是 O ( n 2 ) O(n^2) O(n2) 的；

【优化6】如果可行尽量用加法代替乘法

  • 还是以上面的例子为例，我们发现 A [ i ] [ j ] A[i][j] A[i][j] 满足某种规律；
    A [ i ] [ j ] = { j i = 0 A [ i − 1 ] [ j ] + v 0 < i < n A[i][j] = \begin{cases} j & i=0\\ A[i-1][j] + v & 0<i<n\\ \end{cases} A[i][j]={jA[i−1][j]+v​i=00<i<n​
  • 那么我们可以通过递推的方式将乘法改成加法，实现代码如下：
    int v = Cal(MAX_COUNT);
    for (i = 0; i < n; ++i) {
        for(j = 0; j < m; j++) {
        	if(!i) {
        		A[i][j] = j;
        	}else {
            	A[i][j] = (A[i-1][j] + v);
            }
        }
    }

【思考题4】

  • 不用乘法和除法求解组合数，组合数定义如下：
    C n m = n ! m ! ( n − m ) ! C_n^m = \frac {n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​

4）再次优化取模

【场景5】需要对一批数据进行求和取模

  • 取模满足 模’+’ 运算，所以可以边加边取模，实现代码如下：
int doSumMod() {
	int s = 0;
	for (int i = 0; i < n; ++i) {
		s = (s + val[i]) % MOD;
	}
	return s;
}
  • 当 n = 100000000 n = 100000000 n=100000000 时，该代码的运行实测时间为： 891 m s 891 ms 891ms；

【优化7】不必要时不进行取模运算

  • 取模运算当被取模数小于模时，不需要进行取模，所以上面的写法可以改成如下:
int doSumMod() {
	int s = 0;
	for (int i = 0; i < n; ++i) {
		s += val[i];
		if (s >= MOD) s %= MOD;
	}
	return s;
}
  • 当 n = 100000000 n = 100000000 n=100000000 时，该代码的运行实测时间为： 187 m s 187 ms 187ms；

【思考题5】

  • 取模时出现负数该如何处理？
	ans = -520 % 1314;  //???

5）尽量少用 #define

【场景6】求两个数字中的大者

  • 为了把代码写在一行里，你可能会想这么写：
	#define MAX(a,b) ((a)>(b)?(a):(b))
  • 因为 # d e f i n e \#define #define 是宏替换，所以这里的 a a a 或者 b b b 会计算两次，想象下如下的调用：
	MAX(for(int i = 0; i <100000; ++i) s += i, for(int i = 0; i <100000; ++i) s += i);
  • 你可能会说：谁会写出这样的代码？？？
  • 然而，项目大了，什么代码都会有，你永远无法预料调用你代码的人的水平是怎么样的；

【优化8】宁以 const 或者 函数代替 #define

  • 老老实实写函数吧：
int Max(int a, int b){
	return a > b ? a : b;
}
  • 如果觉得普适性不强，想要支持 c h a r 、 s h o r t 、 f l o a t 、 d o u b l e char、short、float、double char、short、float、double，就搞个模板：
template <class T>
T Max(T a, T b){
	return a > b ? a : b;
}

【思考题6】

  • 如下宏定义求的是一个数的绝对值，它的问题在哪里？
	#define ABS(x) x<0?-x:x

6）循环终止条件

【场景7】循环的终止条件是一个表达式的时候

  • f o r for for 循环的终止条件是一个表达式的时候，每次循环都会判断条件是否满足，也就是每次循环都会进行一次表达式的计算，所以应该尽量简化表达式的计算方式，举个简单的例子如下：
int For() {
	int s = 0;
	for (int i = 0; i*i < n; ++i) {
		for (int j = 0; j*j < n; ++j) {
			for (int k = 0; k*k < n; ++k) {
				// TODO
			}
		}
	}
	return s;
}
  • 为了把注意力集中在这个条件判断上，我跑了个空的三层循环，即运算消耗都在循环终止条件的表达式上了，那么当 n = 1000000 n = 1000000 n=1000000 时，实测的时间消耗为： 2125 m s 2125 ms 2125ms；

【优化9】尽量最大限度的简化循环终止条件的逻辑运算

  • 这段代码的终止条件基本都是平方运算，由于：
    i ∗ i < n   等 价 于   i < n i*i < n \ 等价于 \ i < \sqrt n i∗i<n 等价于 i<n ​
  • 我们可以把表达式进行一个转换，实现代码如下：
int For2() {
	int s = 0;
	int v = sqrt(n + 1e-8);
	for (int i = 0; i < v; ++i) {
		for (int j = 0; j < v; ++j) {
			for (int k = 0; k < v; ++k) {
				// TODO
			}
		}
	}
	return s;
}
  • 简化循环终止条件的运算以后，当 n = 1000000 n = 1000000 n=1000000 时，实测耗时： 1453 m s 1453 ms 1453ms

【思考题7】

  • 对以下代码的循环终止条件进行优化；
	for(i = 0; i < vec.size(); i++) {
		// TODO
	}

3、分而治之

1）二分查找

【场景8】给定一个数，在一个有序数组中查找比它大的最小的数，不存在输出 -1

  • 对于数组中进行数据查找的问题，本文一开始就已经提到了一些解决方案；不过这个问题比较特殊，给定的数组本身是一个有序数组，对于数组元素个数为 n n n 的情况，可以利用二分查找在 O ( l o g n ) O(log_n) O(logn​) 的时间内进行求解；

【优化10】利用二分查找优化有序数组的查找效率

#define MAXA 10
int bin[MAXA] = { 1, 2, 4, 6, 8, 9, 11, 88, 520, 1314 };
int BinarySearch(int val) {
	int l = 0, r = MAXA - 1;
	int m, ans = -1;
	while (l <= r) {
		m = (l + r) >> 1;
		if (bin[m] > val) {
			ans = bin[m];
			r = m - 1;
		}
		else {
			l = m + 1;
		}
	}
	return ans;
}

【思考题8】

  • 如果要在一个有序数组中查找比它小的最大的数，上面的代码要怎么改？

2）二分快速幂

【场景9】计算 a b m o d    c （ a , b < 2 64 ） a^b \mod c（a,b<2^{64}） abmodc（a,b<264） ，一般用在加解密算法（例如 RSA ）中

  • 在这个问题上，又是乘方运算，又是取模运算，本身就已经很耗时了，再加上 a ， b a，b a，b 的数据范围，如果仅仅是枚举遍历求解，以目前计算机的水平，肯定无法在规定时间内求解的；

【优化11】利用递归二分的性质将线性时间复杂度转换成对数时间复杂度

  • 次幂运算是最满足二分递归性质的，因为它满足如下公式：
    a b m o d    c = { 1 m o d    c b 为 0 a ( a ( b − 1 ) / 2 ) 2 m o d    c b 为 奇 数 ( a b / 2 ) 2 m o d    c b 为 正 偶 数 a^b \mod c = \begin {cases} 1 \mod c & b 为 0 \\ a(a^{(b-1)/2})^2 \mod c & b为奇数\\ (a^{b/2})^2 \mod c & b为正偶数\\ \end{cases} abmodc=⎩⎪⎨⎪⎧​1modca(a(b−1)/2)2modc(ab/2)2modc​b为0b为奇数b为正偶数​
    所以可以利用递归把本来 O ( b ) O(b) O(b) 的时间复杂度的问题转化成 O ( l o g b ) O(log_b) O(logb​)，具体实现可以参考以下文章：
    夜深人静写算法（十九）- 快速幂

4、了解 STL 的真实效率

1）vector 的插入

  • S T L STL STL 的 v e c t o r vector vector 意为动态数组，弥补了 C++ 原生不支持动态数组的缺陷；
  • 但是它的效率实在不敢恭维，所以有时候如果不是很必要的情况下，能不用尽量不用；
  • 测试一个 v e c t o r vector vector 的插入效率代码如下：
const int MAXDC = 100;
void DataCollect() {
	vector <int> v;
	for (int i = 0; i < MAXDC; ++i) {
		v.push_back(i);
	}
}
  • 对以上函数调用 100000 100000 100000 次，实测时间为： 3469 m s 3469 ms 3469ms；
  • v e c t o r vector vector 的内存分配策略采用的是倍增法，会预先申请一块内存，每次插入一个元素会对当前剩余内存进行一个预见检测，如果超出这个预分配内存，会对现有内存进行倍增，并且拷贝原有内存数据到新的内存上去，所以这里面会有一些申请堆空间、构造函数、内存拷贝函数的调用等等，不免会有许多常数时间调用，具体规则参见如下文章：STL vector 扩容策略

【优化12】对 vector 进行内存预分配

  • 如果确定 vector 的数据一定至少有 n n n 个，那么我们可以利用 r e s e r v e reserve reserve 函数预先分配 n n n 个元素的内存出来，这样起码会减少很多内存重分配的次数，具体实现代码如下：
const int MAXDC = 100;
void DataCollect() {
	vector <int> v;
	v.reserve(MAXDC);
	for (int i = 0; i < MAXDC; ++i) {
		v.push_back(i);
	}
}
  • 同样，对以上函数调用 100000 100000 100000 次，实测时间为： 1437 m s 1437 ms 1437ms，效率提升了不少；

【优化13】小数组尽量不用 vector

  • 我们发现上面涉及的数组往往比较小，如果直接用一个固定长度为 100 100 100 的数组也能够满足需求，那就尝试用数组来实现一下，实现代码如下：
const int MAXDC = 100;
void DataCollect() {
	int stk[MAXDC], top = 0;
	for (int i = 0; i < MAXDC; ++i) {
		stk[top++] = i;
	}
}
  • 同样，对以上函数调用 100000 100000 100000 次，惊人的发现，实测时间为： 31 m s 31 ms 31ms；
  • 所以可以看出，如果数据量比较小，并且频繁重复调用同一个数组的数据插入时，不建议用 v e c t o r vector vector；
  • 但是需要注意的是，如果用数组，一定要确保数组下标在安全范围内，否则有可能引起进程的崩溃；

2）queue 的插入和取出

  • S T L STL STL 的队列 q u e u e queue queue 实现了 ( F I F O ) (FIFO) (FIFO) 先进先出 的数据结构；
  • 内存分配策略基本上和 v e c t o r vector vector 是一致的，所以也会面临内存重分配和数据拷贝；
  • 基于效率考虑，不建议直接用 S T L STL STL 的 q u e u e queue queue，可以自己实现一个支持扩容的队列；

【思考题9】

  • 1）以下代码有哪些问题？
  • 2）如何优化？
	string s;
	for(i = 0; i < n; ++i) {
		s += "K";
	}

5、了解底层调用

1）慎用三角函数

  • 三角函数的计算用的是 C o r d i c Cordic Cordic 算法，整体来说是一个迭代，一些位移 和 加减法，所以如果一些常用，精度要求不高的，能够用常量代替的可以尽量用常量，比如 ： 3.1415927 3.1415927 3.1415927 代替 a c o s ( − 1.0 ) acos(-1.0) acos(−1.0)；
const int MAXPI = 100000000;
double CalcCircle() {
	double s = 0;
	for (int i = 0; i < MAXPI; ++i) {
		s += acos(-1.0) * i * i;
	}
	return s;
}
  • 以上代码实测时间： 1532 m s 1532 ms 1532ms；

【优化14】精度允许的情况尽量用常量代替三角函数

const int MAXPI = 100000000;
double CalcCircle() {
	double s = 0;
	const double PI = 3.1415927;
	for (int i = 0; i < MAXPI; ++i) {
		s += PI * i * i;
	}
	return s;
}
  • 以上代码实测时间： 672 m s 672 ms 672ms；

【思考题10】

  • 浮点数计算的时候是有精度损失的，那么如何判断两个浮点数是否相等；

2）类型转换

【场景10】静态类型转换 和 动态类型转换 的时耗性

  • s t a t i c _ c a s t static\_cast static_cast 和 d y n a m i c _ c a s t dynamic\_cast dynamic_cast 实测下来效率差距不大；
const int MAXT = 100000000;
void StaticCast_Test() {
	Inher *p = new Inher();
	for (int i = 0; i < MAXT; ++i){
		Base *pkBase = static_cast<Base*>(p);
	}
}
void Dynamic_Test() {
	Inher *p = new Inher();
	for (int i = 0; i < MAXT; ++i){
		Base *pkBase = dynamic_cast<Base*>(p);
	}
}
  • 当调用 10000000 10000000 10000000 时，均为 16 m s 16 ms 16ms 左右；

6、记忆化

1）记忆化搜索

  • 记忆化搜索是动态规划（并不属于搜索范畴）的一种，思路就是将已经计算过的内容记录下来，避免下次遇到的时候重复计算，比较经典的就是递归版本的斐波那契数列的计算；

【场景11】斐波那契数列的计算

  • 来看非记忆化版本的代码：
	long long fib(unsigned int n) {
		if(n <= 1) {
			return n;
		}
		return fib(n-1) + fib(n-2);
	}
  • 虽然代码很短，但是这个函数的实现采用了递归，参考深度优先搜索，每次往下递归相当于扩展了两个二叉树的子节点，所以算法的时间复杂度是 O ( 2 n ) O(2^n) O(2n) 的，如下图所示：
n n-1 n-2 n-2 n-3 n-3 n-4 n-3 n-4 n-4 n-5 n-4 n-5 n-5 n-6

【优化15】记忆化搜索将指数级时间复杂度转变为多项式级时间复杂度

  • 来看下经过记忆化优化以后的递归版本的斐波那契数列计算：
	void init() {
		memset(f, -1, sizeof(f));
	}
	
	long long fib(unsigned int n) {
		if(n <= 1) {
			return n;
		}
		if(f[n] != -1) {
			return f[n];
		}
		return f[n] = fib(n-1) + fib(n-2);
	}
  • 利用一个静态数组来记录斐波那契数列第n项的值，并且初始化为 -1 表示没有计算过，一旦计算出来就给它赋值，下次再访问的时候直接返回已经计算出来的值即可；
  • 均摊时间复杂度 O ( n ) O(n) O(n)；
  • 当然，还有比较常用的记忆化搜索，如区间动态规划、状态压缩，如果对动态规划感兴趣，可以参考这篇文章：夜深人静写算法（二）- 动态规划

2）预处理

  • 记忆化 和 预处理 是两个截然相反的过程，预处理指的是在你需要某些运算信息的时候，它早就已经计算好了，而不是等到需要的时候再去重新计算，还是以斐波那契数列为例：
	f[0] = 0, f[1] = 1;
	for(int i = 2; i < MAXN; ++i) {
		f[i]  = f[i-1] + f[i-2];
	}
  • 这个时间复杂度很明确，是 O ( n ) O(n) O(n) 的，并且在接下来每次询问中，都是O(1)的；
    【优化16】预处理能够处理所有可预见范围内的计算
  • 但是预处理需要确保一个事情，就是所有的询问必须保证数据范围在预处理的数据范围内，否则就起不到预处理的作用了；

3）前缀和

【场景12】计算斐波那契数列的第L项到第R项的和（L<=R）

  • 朴素做法就是每次将 0 − R 0 - R 0−R 项的和都计算出来，然后累加，时间复杂度 O ( R ) O(R) O(R)，代码实现如下：
	f[0] = 0, f[1] = 1;
	for(int i = 2; i <= R; ++i) {
		f[i]  = f[i-1] + f[i-2];
	}
	s = 0;
	for(int i = L; i <= R; ++i) {
		s += f[i];
	}
  • 这个时候，如果请求的数量很多，这里其实伴随着很多冗余计算，所以这里有个技巧叫做：前缀和；

【优化17】预处理数组前缀和可以做到询问时O(1)

  • 1）利用预处理记录下所有斐波那契数列的前缀和，存储在 sum 数组，时间复杂度 O ( n ) O(n) O(n)；
	sum[0] = 0;
	for(int i = 1; i < MAXN; ++i) {
		sum[i]  = sum[i-1] + f[i];
	}
  • 2）询问时通过两个前缀和相减获得所求值，时间复杂度 O ( 1 ) O(1) O(1)；
	NumberType getFib(NumberType L, NumberType R) {
		return sum[R] - sum[L-1];
	}
  • 这种情况适用于询问量非常大的情况；

【思考题11】

  • 给定一个 100 × 100 × 100 100 \times 100 \times 100 100×100×100 的三维数组，然后是 100000 100000 100000 次询问；
  • 每次询问问的是 ( x l , y l , z l ) − ( x r , y r , z r ) (x_l,y_l,z_l)-(x_r,y_r,z_r) (xl​,yl​,zl​)−(xr​,yr​,zr​) 这个子立方数组的和，如何最高效的求解；
  • 时间复杂度是多少；

四、优化总结回顾

【优化1】利用哈希数组的索引来代替数组的遍历
【优化2】利用 S T L STL STL 的 m a p map map 来代替数组的遍历
【优化3】利用 S T L STL STL 的 u n o r d e r e d _ m a p unordered\_map unordered_map 来代替数组的遍历
【优化4】利用位运算进行常数优化
【优化5】改变运算顺序避免重复运算
【优化6】如果可行尽量用加法代替乘法
【优化7】不必要时不进行取模运算
【优化8】宁以 c o n s t const const 或者 函数代替 # d e f i n e \#define #define
【优化9】尽量最大限度的简化循环终止条件的逻辑运算
【优化10】利用二分查找优化有序数组的查找效率
【优化11】利用递归二分的性质将线性时间复杂度转换成对数时间复杂度
【优化12】对 vector 进行内存预分配
【优化13】小数组尽量不用 v e c t o r vector vector
【优化14】精度允许的情况尽量用常量代替三角函数
【优化15】记忆化搜索将指数级时间复杂度转变为多项式级时间复杂度
【优化16】预处理能够处理所有可预见范围内的计算
【优化17】预处理数组前缀和可以做到询问时 O ( 1 ) O(1) O(1)

五、思考题答案

字数太多描述不下了，答案见下期吧

上一篇：#前端学习笔记#day11动画 小米


下一篇：Wcf 文件上传下载