P10815 【模板】快速读入题解

King_and_Grey · 2024-07-29 11:55:07 · 题解

P10815 【模板】快速读入题解

在 C++ 中，输入一般使用 cin、cout。但是他们的速度很慢（是因为 cin 和 cout 为了兼容 C 语言的读入输出在性能上做了妥协）而一些题目在一些题目中，读入的数据量很大，往往超过了 10 ^ 5 的数据量，这时就容易超时。接下来我会介绍几种优化方法。

第一种：解锁

ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

对 cin 和 cout 进行解锁使 cin 和 cout 的速度几乎接近 scanf 和 printf（甚至超过），这样避免输入输出超时。

注意：cin、cout 解锁使用时，不能与 scanf，getchar，printf，getline()，也不能与 freopen 连用，否则会出错。

此外：解锁后会导致在 cout << endl; 使清空缓存，如果大量使用 cout << endl; 的话反而会增加程序输出时间，所以可以换成 \n。

但是这并不能通过此题。

第二种：使用 C 风格

scanf、printf 这两个函数来源于传统的 C，在 stdio.h 和 cstdio（C++）中。使用方法：

scanf("%占位符",&var);
printf("%占位符\n",var);

这样比传统的 cin、cout 快，但由于书写复杂而很少被人采用。

第三种：快读快写

快读基本思想：

一位一位读入，对当前字符进行分析，（第一位是判断是否为负号）
讲读入的数字处理（因为是字符）后存入
最后返回数值

代码：

int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (!isdigit(ch)) {  // ch 不是数字时
    if (ch == '-') w = -1;        // 判断是否为负数
    ch = getchar();               // 继续读入
  }
  while (isdigit(ch)) {  // ch 是数字时
    x = x * 10 + (ch - '0');        // 将新读入的数字加在 x 的后面，就是秦九昭算法
    ch = getchar();                 // 继续读入
  }
  return x * w;                     // 数字 * 正负号 = 实际数值
}
void write(int x){
    if (x < 0) putchar('-'), x = -x;//判断是否为负数
    if (x > 9) write(x / 10);       //逐位分解，递归输出
    putchar(x % 10 + '0');          //转换为字符输出
}

快读快写进一步优化

对于 `int read()`

我们可以在 int 前面加个 inline，inline（内联）对于多次调用的函数有着非常明显的加速作用，而快读明显非常常用。

关于 inline 的优缺点：

优点：对于一些较小的函数，如果频繁调用，可以将其设计为内联函数，省去了执行函数地址转移等操作，占用系统资源更少，执行效率更高。
缺点：如果调用内联函数的地方太多，就会造成代码膨胀，因为编译器会把每个调用内联函数的位置都拷贝一份函数实现嵌入其中，重复的嵌入。

对于 `x = x * 10 + (ch - '0');`

数据的四位运算虽然简单，但是比位运算要慢。

计算机就是将数据以二进制进行运算，所以位运算比四位运算要快。

我们可以把 x = x * 10 + (ch - '0'); 改成 x = (x << 1) + (x << 3) + (ch ^ 48);

其中，x << n 表示 x 的二进制向左移动 n 位空位补 0，相当于 x = x \times 2 ^ n ，(x << 1) + (x << 3) 相当于 x \times 10（请读者自行推导）。

对于 `getchar`

把 getchar() 改成 getchar_unlocked()，效率接近 fread。

讲解完毕。

奉上万能模板：

inline int read(){
    int x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)){
        if (ch == '-') 
            f = -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar_unlocked();
    }
    return x * f;
}

inline void write(int x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

最后奉上本题的代码：

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)){
        if (ch == '-') 
            f = -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar_unlocked();
    }
    return x * f;
}

inline void write(int x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main(){
    int n = read(),ans = 0;
    int a[n + 1];
    for(int i = 1;i<= n;i++){
        a[i] = read();
        ans += a[i];
    }
    write(ans);
    return 0;
}

通过记录。

谢谢观看！！！

P10815 【模板】快速读入 题解