C++ 性能骨灰级优化(推荐)

文章目录

一、前言

  • 一款游戏上线分钱,它的奖金来源如下:
    奖 金 = 流 水 − 分 成 − 不 可 描 述 的 内 容 − 人 力 成 本 − 资 源 成 本 − 服 务 器 成 本 奖金 = 流水 - 分成 - 不可描述的内容 - 人力成本 - 资源成本 - 服务器成本 奖金=流水−分成−不可描述的内容−人力成本−资源成本−服务器成本
  • 前面几项我们做技术的都无法改变,但是服务器成本这块,我们是有责任和义务去减少的;
  • 所谓能省则省嘛,你的代码写的越高效,服务器执行效率越高,用到的服务器 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 文件上传下载