前言

卡常数操作并不是想象的那么简单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

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。---2018 NOIP 退役人士

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

    好吧, 我的锅。。。

发表评论

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

你是机器人吗? =。= *