【算法】NOIP 简单的代码优化和编程技巧 ——B_Z_B_Y

前言

卡常数操作并不是想象的那么简单 ComeIntoPower dalao 的建议让我知道了这里的深度 ~~(实在做不来还是学算法吧 QAQ~~~~~

适当的优化可以帮你只能想出暴力的算法多 A 几个点，但是最终嘛

算法的学习和研究最有效 QwQ

内容

1. 读入优化

2. 宏定义

3. 选用的数据类型

4. 语句与运算优化

5. 手写数据结构

6. 对拍

One . 读入优化

这个基本都知道吧，我也就不细讲了

读入基于 fread，这里实现的只能读入字符和整形，至于输出+stack，基于 putchar 就好了，反正输出量又不是很大 ~~(只是我懒，不愿写~~

我先说一下关于位运算什么想多了，你把 s*10 写成位运算只会让你的程序更慢，因为同样在 g++ 把程序编译之后的代码，后者比前者还多了 1 条语句。

并且乘法的位运算和直接 `*`速度是一样的 (在汇编里均为等价….），而且如果

void swap(int &x,int &y){
    int temp = x;
    x = y;
    y = temp;
}
// 写成
void swap(int &x,int &y){
    x ^= y;
    y ^= x;
    x ^= y;
}
// 会变慢的 QAQ 原理也和上述类似 
// 所以从此 swap 再也没有 ^ 了  23333

当然位运算在除法里还是很有用的，对 2 的幂的运算，以及判断奇偶的时候

const int Size=1<<25|1;
inline char getch(){
    static char buf[Size],*p1=buf,*p2=buf;
    return p1==p2 && (p2 = (p1=buf) + fread(buf,1,Size,stdin),p1 == p2) ? EOF : *p1++;
}
int read(){
    int s=0,f=1;
    char c=getch();
    while(!isdigit(c) || c == '-') {if(c=='-') f=-1; c=getch();}
    while(isdigit(c)) {s=s*10+(c-48);c=getch();}
    return s*f;
}
// c 函数的 isdigit() 判断和你手写的汇编指令其实是一样 。QwQ
// 另外 把 s*10 写成 (s<<1)+(s<<3) 的同学请自重吧 23333
void write(int x){
    static int sta[36];
    int top=0;
    if(x < 0) {
        putchar('-');
        x=-x;
    }
    do{
        sta[top++]=x%10;
        x/=10;
    }while(x);
    while(top) putchar(sta[--top]+48);

}

Second . 宏定义

宏定义是个啥？ ——————— 也就是 define

#define 是个好东西啊 OUO, 不仅可以替换变量名使你的代码更短，还可以定义函数 ~~（实则就相当于直接替换）~~，还有奇特的用法，那么

不过请注意 define 的本质是替换所以如果宏的参数出现 ++x 或者 x++ 之类的请另外加语句除去，否则 x 在宏里会重复计算，导致你调试到死也不知道为什么答案不对

#define fors(i,a,b) for(int i=(a);i=(b);--i)
#define mem(x,val) (memset((x),(val),sizeof (x)))

#define min(x,y) ((x) &lt; (y) ? (x) : (y))
#define max(x,y) ((x) &lt; (y) ? (y) : (x))
#define abs(x) ((x) &lt; 0 ? -(x) : (x)) 
#define swap(x,y,tmp) ((tmp)=(x),(x)=(y),(y)=(tmp))
//注意使用的时候在前面多定义一个 temp

#define forvit(i) for(vector :: iterator it=(i).begin();it!=(i).end();++it) 
#define v *it
//注意定义之后，如果定义了一个 v 的变量会 Error，因为已经被 v 替换成了*it

#define link(x , y) x##y //神奇的拼接，可以将两个 int 拼在一起
#define Tostring(x) #x
//例如 x=24,y=16 ;int a = link(x,y);  a=2416
//但注意不要超出 int 的范围;
//或者你可以使用 long long 这样就有 18 位数字了 ll-inf ~=9e18;
// Tostring 就相当于 给 x 加上一个""号 但是如果 x 是个变量的话，那就不行,
// a=12; cout&lt;&lt;Tostring(a)&lt; a 直接输出了变量名，好像没什么用啊 2333 QAQ 如果有 dalao 发现了这玩意的技巧请告诉我 QwQ


#define pr(...) printf(__VA_ARGS__);


//__VA_ARGS__相当于一个可变参数宏 (无关重点
// 主要是 可以这么用 pr("QVQ %d\n" , 1231); 就当作 printf 啦

#define I_O(x) freopen(""#x".in","r",stdin);freopen(""#x".out","w",stdout);
// 用于读入文件 ， 使用时注意"的位置 ， I_O（文件名）不用加后缀 2333

#define Debug(...) fprintf(stderr,__VA_ARGS__)
// Debug 就是用来调试的 fprintf 和 stderr -&gt; cerr，具体和 printf 一个用法
// 可以在使用 freopen 的时候将 Debug 输出到屏幕
// 调试时用 fprintf(stderr, "%d", clock()) 更方便
// Debug("Ans = %d   Time: %d",Ans,clock());

Third . 数据类型

1. 首先速度的话 int 好像是最快的，所以不考虑内存，精度的话尽量都用 int 存吧

2.vector 里 iterator 比使用下标访问快一点了（虽然 STL 普遍比较慢，如果开 O2，vector 取下标和数组取下标速度差不多（不过 vector 要判越界，当然不开 O2 你最好连 vector 都不要用

3. 数据极为强大的最大流使用 vector 存图，不信的话，你可以自己试试原因在于数据太过巨大，vector 动态的劣势已降至极低，而大量访问连续的内存地址显然比前向星更优

4. 提高时空局部性

提高时间与空间局部性即可使你的程序对高速缓存友好。

如果你写一个树剖，上来先开一大堆数组：
int siz[maxn], top[maxn], son[maxn], fa[maxn], depth[maxn];
而访问的时候，却总是 siz[i]， top[i]之类的连着访问，这样做空间局部性极差，所以为了提高运行速度，我们可以把这些东西扔进结构体里，由于结构体内的元素在内存里是按顺序排列的，所以可以提高空间局部性, 虽然有时也可能变慢 QAQ

struct node
{
    int siz, top, son, depth, fa;
    node() { siz = top = depth = fa = 0;}
};
node nd[maxn];

避免使用步长为 2 的 n 次幂的内存引用由于高速缓存不是全相连的，使用步长为 2 的 n 次幂的内存引用模式所以会导致每次访问都不命中，效率会比较低不过，基本很少会开 2^n 的空间吧 2333。

5.《Bitset》简介

Four. 语句与运算优化

前言：一般我们的程序会编译器转化为汇编语言，

而一些语句在汇编里是等价的，所以不要轻易相信网上的一些什么语句比什么语句快之类的, 如果有对语句相同觉得疑惑的话请自行去这里验证 c++ -> 汇编

编译器远比你想象的聪明，所以最适合优化的便是所谓 “少一些变量”，“少一些判断” 等人工的的优化方式了

位运算技巧

II. 条件语句

当你的 if（A && B）中如果 B 为 false 的可能性比 A 大的话，你就需要互换位置，因为当第一个表达式为 false 的时候，程序就不会执行后面的表达式

III. 关于取模的优化 OvO。

因为避免了模数的除指令运算很费事，所以我们使用加避免了除指令。

inline int modadd(int a,int b){a+=b;return a>=p ? (a-=p) : a;}

// (a+=b) % = p;
// 加法，注意一下大小问题，因为有可能 在 a 远大于 p 的时候答案会大于 P

inline int moddel(int a,int b){a-=b;return a<0 ? (a+=p) : a;}
// (a-=b) % = p;

a % b == a-a/b * b 

//这个性质也许会对你的解题有帮助 

inline int mod_mul(int a,int b,int mod){
    int ret=0;
    __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n" : "=d"(ret):"a"(a),"b"(b),"c"(mod));
    return ret;
}
//据说直接使用汇编语言做 a*b%c 会比直接% 快，
//不过 NOI 系列的比赛都不让用 所以 GG , 不过你可以搞搞其他的（例如毒瘤的月赛，逃


ll mul(ll a,ll b,ll p){
    a=a%p,b=b%p;
    return ((a*b - (ll)(( (long double)a * b + 0.5 ) / p) * p )%p +p)%p;
}//防止精度爆炸的乘
//原理就是 n%p == n-n/p*p 。
//而后面的则是计算了实数 (a*b)/p, 向下取整。
//由于 C++中 long double 的精度是超过 10^18 级别的，因此可以保证结果正确。
//并且式子里两次乘法运算超过了 ll 的范围，由于 C++会高位溢出，
//忽略符号位相当于是在模 2^63 的意义下做。所以最终结果在 2^63 以内，因此结果正确

IV. 对于矩阵乘法可以通过调整 `for` 的顺序使得访问相对连续使得程序运行加快

int c[];
fors(i,1,n)
    fors(k,1,n)
        fors(j,1,n)
            c.m[i][j]=c.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod;

fors(i,1,n)
     fors(j,1,n){
        int ik=x.m[i][k];
        fors(k,1,n)
            c.m[i][j]=c.m[i][j]%mod+ik*y.m[k][j]%mod;
          }

// 数组连续访问，简单点就是下标在前的循环也在前（k）
//下标在后的循环也在后（j）
//矩阵乘法用 i,k,j 的同时将 x[i][k] 用一个临时变量保存貌似可以快很多 QwQ

也就是说减少不必要的计算，对于一个重复计算的值存入临时变量, 并且把访问量越大的尽量放在前面枚举。这样指针的跃动距离会少一些。

V. 顺序访问

顺序访问的话缓存可以实现高速遍历（相对于随机顺序）。但是顺序访问与逆序访问，速度是差不多的，不会对缓存造成什么影响，所以我们在遍历数组的时候要尽量修改跳动的指针为连续的指针

fors(i,1,n)
    S+=A[H[i]];
cout<<S<<endl;

H[i] - > rand()
fors(i,1,n)
    S+=A[H[i]];
cout<<S<<endl;

//如果 H[i] 是一个随机数列的话, 那么就会比较慢

VI. 循环展开+多路并行

在不超过 cache 大小的情况下循环展开越深优化越大

由于 cpu 整数加法运算器有多个，而同一个时间可以最多运算两个整数加法，通过这种方法可以增加流水线吞吐量。实际上，编译器会在第二次隐式汇编优化时候做这个优化，如果你把 gcc 开到 o3 以上的优化程度就可以自动在汇编指令层级变成这种形式

//如松爷 pdf 中的例子
double sum(double *a, int n) {
    double s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}
double sum(double *a, int n) {
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    for (int i = 0; i < n; i += 4) {
        s0 += a[i];
        s1 += a[i + 1];
        s2 += a[i + 2];
        s3 += a[i + 3];
    }
    return s0 + s1 + s2 + s3;
}

不过当展开次数过多时，性能反而下降，因为寄存器不够用也就是寄存器溢出，比较玄学 , 所以你可以使用 Dev c++的调试看看寄存器是否溢出，或者用 clock() 函数看看怎么展开耗时少。

循环次数未知的循环并行性很差，基本没有研究的价值。如果循环展开 k 次，就可以把上限设为 n-k+1，那么最大循环索引 i+k-1 将会比 n 小。然后，再加上第二个循环，以每次处理一个元素的方式处理数组的最后几个元素

优点

1. 分支预测失败减少。

2. 如果循环体内语句没有数据相关，增加了并发执行的机会。

3. 可以在执行时动态循环展开。这种情况在编译时也不可能掌握。

缺点

1. 代码膨胀

2. 代码可读性降低，除非是编译器透明执行循环展开。

3. 循环体内包含递归可能会降低循环展开的得益。

摘自维基百科

VIII. CPU 并发

注意：在使用这个技巧时，需要自行判断能否使用，否则后果…

这个技巧看似简单，但能带来常数级别的飞越，可能出现的情况 $n^2$ 过百万，暴力踩标程。QAQ , 差不多就这么个鬼玩意

fors(int j=1;j<=n; j+=24) {

    ans+=(*(A+j)+*(A+j+1)+*(A+j+2))+(*(A+j+3)+*(A+j+4)+*(A+j+5))+(*(A+j+6)+*(A+j+7)+*(A+j+8))+

                 (*(A+j+9)+*(A+j+10)+*(A+j+11))+(*(A+j+12)+*(A+j+13)+*(A+j+14))+*(A+j+15)+

                 (*(A+j+16)+*(A+j+17)+*(A+j+18))+(*(A+j+19)+*(A+j+20)+*(A+j+21))+(*(A+j+22)+*(A+j+23));

        }

使用条件:

循环展开后，可以方便地用大量简单的运算完成对答案的更新。

观察到你的寄存器并不会溢出。

例题计算 $∑ { i = from ~ 1 ~ to ~ 30000 } ~ ∑{ j = from ~ 1 ~ to ~ 30000 } ( A[i] ~ / ~ B[j])$ 其中 $B[j]<=64,A[i] 1. 尽量不要使用递归。递归可以很优雅和简洁，但是太多的函数调用会造成巨大的开销。

避免在循环中使用 sqrt() 函数，因为计算平方根是非常消耗 CPU 的。

一维数组比多维数组更快。所以你可以多想一下将维的方法

浮点数的乘法通常比除法快–使用 val * 0.5 而不是 val / 2.0。

加法运算比乘法更快–使用 val + val + val 而不是 val * 3。puts() 函数比 printf() 函数快，虽然不是很灵活。

如果你还想研究的话就并行展开，用大数据多次测量比较。用汇编指令说话，比较编译后的汇编差别。以及了解时间周期，便于指出最慢的那个操作。以及背后的原理 ~~(看不懂汇编逃~~

内存开小：主要是数量级上要小，比如 O(nlogn)->O(n),O(n^2)->O(n) 等。申请内存和释放内存次数尽量少：数据结构中使用内存池就是个好例子。

对于很大的图/树重标号，即按 dfs 序重新标号，可以让内存连续。

减少瓶颈操作次数，比如 LCT/线段树的 pushup,pushdown 是瓶颈，所以应该减少它们的次数。ZKW 线段树正是因为减少了期望次数才变快了

10.　dp 的时候精确计算上界，减少状态数。

最后 5 点我是直接加上 ComeIntoPower dalao 的话的，因为我并不怎么会这些操作还是等我技术再好一点的时候说吧，读者可以自行研究一下（太难了，QAQ 逃

总结一下

首先对于一道题，如果只能想出 O(n^2) 的暴力，那么不妨试试这些优化。而不是着拿到一个题，一眼过去就用暴力+卡常。

优化你的算法最重要，计算机科学的支柱是算法，而不是底层优化。

本文到此结束 OvO，如果有 dalao 指明有什么不对的地方，十分感谢

5 条评论

B_Z_B_Y · 2018年10月25日 4:59 下午

突然觉得，手写 stl 还不如直接用 c++库的 stl，~~（自己太弱，老是写出 bug）~~，反正 NOIP 手写，不手写不是很重要（因为该 T 的还是会 T QvQ）（所以总的来说算法研究最重要）

wendster · 2018年10月15日 12:07 下午

诡异，超大字体而又超长文章严重搅乱了我的大脑皮层灰质……

B_Z_B_Y · 2018年10月15日 2:41 下午

等我有时间改改 QAQ

by · 2018年10月14日 12:18 下午

这篇文章的数学公式好像都没显示出来？

by · 2018年10月14日 12:20 下午

好吧，我的锅。。。