SAVE TIME

· · 个人记录

SAVE TIME

输入输出优化

同样的输入与输出10^7个数（1,2,3，...，10^7）

用cin和cout：

cin>>n;
for(int i=1;i<=n;i++)
   cin>>a[i];

输入时间约为11.998s

for(int i=1;i<=n;i++)
  cout<<a[i]<<" ";

输出时间约为1.439s

关闭同步

iOS::sync_with_stdio(false);

scanf & printf

scanf("%d",&n);
for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);

输入时间约为6.82s

for(int i=1;i<=n;i++)
  printf("%d ",a[i]);

输出时间约为12.621s

貌似输出...

fin & fout

ifstream fin("time.in");
ofstream fout("time.out");
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
      fin>>a[i];
    for(int i=1;i<=n;i++)
      fout<<a[i]<<" ";
    return 0; 
}

输入时间约为1.706s， 输入时间约为1.502s QwQ

另外，还有这种写法：

fin=fopen("time.in","r");
fout=fopen("time.out","w");
fscanf(fin,"%d",&n);
for(int i=1;i<=n;i++)
  fscanf(fin,"%d",&a[i]);
for(int i=1;i<=n;i++)
  fprintf(fout,"%d",a[i]);

快读 & 快写

inline int read() 
{ 
    char c=' ';
    int x=0,y=0; 
    while(!isdigit(c)) 
    { 
       if(c=='-') y=1; 
       c=getchar(); 
    } 
    while(isdigit(c)) 
    { 
       x=(x<<3)+(x<<1)+c-'0'; 
       c=getchar(); 
    } 
    return y?-x:x; 
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) 
      write(x/10);
    putchar(x%10+'0');
}

定义优化

register

把变量放到CPU寄存器中，适用于一些使用频繁的变量(比如，在循环体里)。但寄存器空间有限，如果放得变量太多，多余变量就会被放到一般内存中

For example,

register int a;
for(register int i=1;i<=999999999;i++)
  a++;

用时314ms

int a;
for(int i=1;i<=999999999;i++)
  a++;

用时2104ms

函数优化

inline

把函数指定为内联函数。

但是内联函数一般只会用在函数内容非常简单的时候。这是因为，内联函数的代码会在任何调用它的地方展开，如果函数太复杂，代码膨胀带来的恶果很可能会大于效率的提高带来的益处。

循环优化

循环展开

n=100000000

for(int i=1;i<=n;i++)
  sum+=i;

用时290ms

for(int i=1;i<=n;i+=5)
{
    sum+=i;
    sum+=i+1;
    sum+=i+2;
    sum+=i+3;
    sum+=i+4;
}

用时193ms

others

n=100000000

for(int i=1;i<=n;i++)
  sum1+=i;
for(int i=1;i<=n;i++)
  sum2++;

用时496ms

for(int i=1;i<=n;i++)
{   
    sum1+=i;
    sum2++;
}

用时222ms

关于运算

快速幂

long long pow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
       if(b&1)
         ans*=a
       a*=a;
       b>>=1;
 　 }
    return ans;
}

除法

For example，

a/b/c => a/(bc)
a/b==c => a==bc

位运算优化

x*2 => x<<1

x/2 => x>>1

if(x%2==1) => if（x&1）

绝对值

int abs(int n)
{
   return (n ^ (n >> 31)) - (n >> 31);
}

MAX

int max(int a,int b)
{
    return b&((a-b)> 31)|a&(~(a-b)>>31);
}

MIN

int min(int a,int b)
{
    return a&((a-b)>>31)|b&(~(a-b)>>31);
}

一大堆卡常操作

O(1).O(2).O(3)优化

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)

others

#pragma GCC optimize("Ofast") 
#pragma GCC optimize("inline") 
#pragma GCC optimize("-fgcse") 
#pragma GCC optimize("-fgcse-lm") 
#pragma GCC optimize("-fipa-sra") 
#pragma GCC optimize("-ftree-pre") 
#pragma GCC optimize("-ftree-vrp") 
#pragma GCC optimize("-fpeephole2") 
#pragma GCC optimize("-ffast-math") 
#pragma GCC optimize("-fsched-spec") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("-falign-jumps") 
#pragma GCC optimize("-falign-loops")