算法竞赛常见优化测试 (C++)

本文整理并测试、验证了算法竞赛（包括但不限于 NOIP/NOI/ACM/IOI 等）中常用的 C++ 优化技巧。

测试代码可在 OI-share 中浏览：Gitee Github

测试基于 Linux 系统，发行版为 Ubuntu 18.04，内核版本 4.15.0-54，CPU i5-7500，内存 8G。

输入输出

据传输入输出是个容易超时的东东？（以下所有测试基于 NOIP 规则，打开特定输入输出文件）

输入

int

测试内容

读入 n 和 n 个整数，计算其总哈希并输出。（在本次测试中，定义 hash 为求和并自然溢出）

测试数据量

生成十组数据，每组数据n=10 000 000，生成数据文件约 100MB，接近于竞赛中可能出现的最大范围；每个程序每组数据测试 10 次以减小误差，避免偶然性

方案（括号内为编号，偶数不开优化，奇数开优化）：

• scanf 直接读入(0,1)
• cin 直接读入 (2,3)
• cin 关闭 sync(std::ios::sync_with_stdio(false);) (4,5)
• fread() (6,7)
• mmap() (8,9)

注：6,7,8,9 读入整个文件保存在内存中并采用自定义输入函数解析输入

比较如下。

可以发现，在默认情况下，cin 比 scanf 慢 3 到 4 倍，但在执行 ios::sync_with_stdio(false); 后两者相差不大，因此关闭同步后可以放心使用 cin，但是要注意不能混用 cin 和 stdio；在 Linux 系统上，使用 fread() 和 mmap()，将输入先整个保存到内存中再用快读处理是最快的方案，尤其是 mmap()，在 O2 优化的情况下可以达到输入一千万个数据只需要 $0.14$ 秒。

附 mmap 读入代码：

#include<cstdio>
 #include<fcntl.h> 
#include<unistd.h>
#include<sys/types.h>
#include<sys/mman.h>
#include<sys/types.h>
#include<sys/stat.h>
using namespace std;

const int MAXS = 120*1024*1024; //120MB
char* buf;

unsigned int Hash=0;
int len;

void _hash(unsigned int& Hash,unsigned int x){
    Hash+=x;
}

void doit(){
    int x=0;
    char *p=buf;
    while(*p!='\n') *p++;
    while (*p && p-buf<len){
        if ((*p == ' ')||(*p=='\n')||(*p=='\t')){
            _hash(Hash,x);
            x=0;
        }
        else
            x = x * 10 + *p - '0';
        p++;
    }
}

int main(){
    int fd = open("input",O_RDONLY);
    freopen("output","w",stdout);
    len = lseek(fd,0,SEEK_END);
    buf = (char *) mmap(NULL,len,PROT_READ,MAP_PRIVATE,fd,0);
    doit();
    printf("%u\n",Hash);
    return 0;
}

其他代码点此访问

参考资料&&Credit

• cin 与 scanf cout 与 printf 效率问题