前言

卡常数操作并不是想象的那么简单 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.vectoriterator 比使用下标 访问 快一点了(虽然 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 &amp;&amp; B)中 如果 Bfalse 的可能性比 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. 尽量不要使用递归。递归可以很优雅和简洁,但是太多的函数调用会造成巨大的开销。

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

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

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

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

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

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

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

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

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

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


总结一下

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

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

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

分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔。

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 下午

    好吧, 我的锅。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注