【C++算法】 卡常技巧

文章目录

• updata
• 学习引言
• 技巧 1——善用修饰符
• 技巧 2——输入输出
• • `read` 和 `write`
• 技巧 3——对于运算的优化
• 技巧 4——展开循环
• 技巧 5——对与循环的优化

updata

• 2024.03.31 发布此文章

学习引言

卡常，一种编程技巧，在对时间复杂度要求很高时，就可以用这种办法来节省时间。

今天，我们也来学习一下卡常。

技巧 1——善用修饰符

在定义变量前可以加上 register 修饰符，这样在使用时可以加快速度。

在自定义函数前则可以加上 inline，这样也可以加快速度。

技巧 2——输入输出

如果把输入输出速度按从快到慢排序的话，如下：

1. fread 和 fwrite；
2. read 和 write，此函数需自己编写，在下面会讲；
3. scanf 和 printf；
4. cin.tie 和 cout.tie；
5. cin 和 cout。

看到了吧，我们常用的 cin 和 cout 是最慢的，所以呢，在卡常的时候，一定不要用 cin 和 cout，并且，即始用了 .tie 加速后其实还是和 scanf 和 printf 相差很远。

read 和 write

此函数原理简单，众所周知，getcher 和 putcher 函数是非常快的，但只能输入（输出）单个字符，我们其实也可以用他们一位一位的进行输入（输出），代码如下（不能进行负数操作，负数操作其实很简单，只要加个判断就可以了）：

inline long long read() {
	register int x=0;register char c=getchar(),f=1;
	for(;c-48>>63||57-c>>63;c=getchar()) if(c==45)f=-1;
	for(;47-c>>63&&c-58>>63;c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
inline void write(register long long x) {
	if(x-0>>63) putchar(45),x=~x+1;
	if(9-x>>63) write(x/10);
	putchar(x%10^48);
}

技巧 3——对于运算的优化

众所周知，计算机电脑内部存储数据使用的是二进制，而位运算与二进制有直接联系，故系统处理位运算时在效率上有很大优势。但是，要注意，位运算优先级很低的哦！

俗话说：没有对比没有伤害。这里列出了程序执行各种运算所需的时间周期：

由此，我们也就看出了位运算的速度之快以及取模的速度之慢。所以，我们能用位运算其实就可以用位运算。

实际上，我们很多常见的操作都可以用位运算来算，这里统计在下：

1. 乘上一个 2 整数次幂，可以改用左移运算加速，格式为 原数字<<=幂，效率约增加 300 % 300\% 300%；
   x*=8 ⇒ \Rightarrow ⇒ x<<=3。
2. 除以一个 2 整数次幂，可以改用右移运算加速，格式为 原数字>>=幂，效率约增加 300 % 300\% 300%；
   x/=8 ⇒ \Rightarrow ⇒ x>>=3。
3. 判断一个数是否为奇/偶数，可用位运算加速，效率约增加 500 % 500\% 500%；
   x%2==0 ⇒ \Rightarrow ⇒ ~x&1；
   x%2==1 ⇒ \Rightarrow ⇒ x&1。
4. 判断一个两个数是否满足 x > y x>y x>y，可用位运算加速约 200 % 200\% 200%；
   x>y ⇒ \Rightarrow ⇒ y-x>>31（注：这里的 x , y x,y x,y 都是 int 型变量，若 x , y x,y x,y 为 long long 型变量则将 31 31 31 改为 63 63 63。
5. 快速求一个数的相反数，可用位运算加速约 400 % 400\% 400%;
   -x ⇒ \Rightarrow ⇒ ~x+1。
6. 快速求一个数的绝对值，可用位运算加速约 400 % 400\% 400%；
   x<0?-x:x ⇒ \Rightarrow ⇒ x^(~(x>>31)+1)+(x>>31)
7. 交换两数 x , y x,y x,y，可用位运算加速约 30 % 30\% 30%；
   swap(x,y) ⇒ \Rightarrow ⇒ x^=y^=x^=y。
8. 一个数取模另一个数，可用乘除法加速约 65 % 65\% 65%；
   x%=y ⇒ \Rightarrow ⇒ x-x/y*y。

技巧 4——展开循环

举个的例子，我们要对一个序列求和，我们一般这样写：

long long sum=0;
for(int i=1;i<=n;i++) sum+=a[i];

而加了循环展开一般会这样写：

long long sum0=0,sum1=0,sum2=0,sum3=0,sum4=0,sum5=0,sum6=0,sum7=0,i=1;
for(i=1;i+8<=n;i+=8) {
    sum0+=a[i];sum1+=a[i+1];sum2+=a[i+2];sum3+=a[i+3];
    sum4+=a[i+4];sum5+=a[i+5];sum6+=a[i+6];sum7+=a[i+7];
}
for(;i<=n;i++) sum0+=a[i];

那么可能就有人疑惑了，一个好端端的循环干嘛把它 癫子一般地 展开呢？

因为如果按照前一种的写法，每次进行循环 CPU 都要执行 n n n 次 i++，以及 n n n 次 sum+=a[i] 的操作。而一般来说 CPU 中是有多个运算器的，前一种写法相当于将所有的运算都抛给了一个运算器，其它运算器都在那儿睡大觉，这显然是一种资源浪费。使用循环展开就可以始 睡觉的 CPU 起床 CPU 并行，也就大大加快了程序运行的效率。

值得注意的一点是，循环展开不能展开太多，一般是展开 4 4 4~ 8 8 8 层，否则程序运行的效率反而会变慢 CPU 只有那么多，又不能分身。

还有一点就是循环展开一般要用到很多结构非常相似的代码，此时就可以考虑 #define func(i)。

事实证明循环展开效果比前几种卡常方式要好得多，一下子就少了 0.5 s 0.5s 0.5s：

for(int i=1;i<=k;++i) {
	register int tmp=0;
	for(register int j=i;j<=n;j+=5) {
		#define swp(j) if(a[j]>tmp&&j<=n) a[j]^=tmp^=a[j]^=tmp
		swp(j);swp(j+1);swp(j+2);swp(j+3);swp(j+4); 
	}
	a[i]=tmp;
}

当然我们还是不够满意，因为这边还有个 j<=n，每次展开都要判断一次，显然大大拖慢了程序运行的效率，此时你也可以进一步将 j<=n 展开，卡到最后的代码长这样：

for(register int i=1;i<=k;++i) {
	register int tmp(0),j(i);
	#define swp(j) (a[j]>tmp&&(a[j]^=tmp^=a[j]^=tmp))
	for(;j+5<=n;j+=5) {
		swp(j);swp(j+1);swp(j+2);swp(j+3);swp(j+4); 
	}
	(j<=n)?swp(j):0;(j+1<=n)?swp(j+1):0;(j+2<=n)?swp(j+2):0;(j+3<=n)?swp(j+3):0;(j+4<=n)?swp(j+4):0;
	a[i]=tmp;
}

技巧 5——对与循环的优化

有如下的程序：

for(int i=1;i<=k;i++) {
	int tmp=0;
	for(int j=i;j<=n;j++) {
		if(a[j]>tmp) a[j]^=tmp^=a[j]^=tmp;
	}
	a[i]=tmp;
}

据网上某些博主所说，将 i++ 改为 ++i 能提升程序效率，实测效果不明显， n = 50000 , k = 20000 n=50000,k=20000 n=50000,k=20000 的运行时间只提升了 0.01 s 0.01s 0.01s。还有就是将 int i=1 改为 int i(1) 也能加快程序运行效率，不过同样效果不太明显。