写在基石前面

下面这段话来自于 NJU 计算机系统概论 PA 文档，值得一读。

基础设施 - 提高项目开发的效率
在PA中, 基础设施是指支撑项目开发的各种工具和手段. 原则上基础设施并不属于课本知识的范畴, 但是作为一个有一定规模的项目, 基础设施的好坏会影响到项目的推进, 甚至决定项目的成败, 这是你在程序设计课上体会不到的.

事实上, 你已经体会过基础设施给你带来的便利了. 我们的框架代码已经提供了Makefile来对NEMU进行一键编译. 假设我们并没有提供一键编译的功能, 你需要通过手动键入gcc命令的方式来编译源文件: 假设你手动输入一条gcc命令需要10秒的时间(你还需要输入很多编译选项, 能用10秒输入完已经是非常快的了), 而NEMU工程下有30个源文件, 为了编译出NEMU的可执行文件, 你需要花费多少时间? 然而你还需要在开发NEMU的过程中不断进行编译, 假设你需要编译500次NEMU才能完成PA, 一学期下来, 你仅仅花在键入编译命令上的时间有多少?

有的项目即使使用工具也需要花费较多时间来构建. 例如硬件开发平台vivado/quartus一般需要花费半小时到一小时不等的时间来生成比特文件, 也就是说, 你编写完代码之后, 可能需要等待一小时之后才能验证你的代码是否正确. 这是因为, 这个过程不像编译程序这么简单, 其中需要处理很多算法上的NPC问题. 为了生成一个质量还不错的比特文件, 硬件开发工具需要付出比gcc更大的代价来解决这些NPC问题. 这时候基础设施的作用就更加重要了, 如果能有工具可以帮助你一次进行多个方面的验证, 就会帮助你节省下来无数个"一小时".

Google内部的开发团队非常重视基础设施的建设, 他们把可以让一个项目得益的工具称为Adder, 把可以让多个项目得益的工具称为Multiplier. 顾名思义, 这些工具可以成倍提高项目开发的效率. 在学术界, 不少科研工作的目标也是提高开发效率, 例如bug自动检测和修复, 自动化验证, 易于开发的编程模型等等. 在PA中, 基础设施也会体现在不同的方面, 我们会在将来对其它方面进行讨论.

你将来肯定会参与比PA更大的项目, 如何提高项目开发的效率也是一个很重要的问题. 希望在完成PA的过程中, 你能够对基础设施有新的认识: 有代码的地方, 就有基础设施. 随着知识的积累, 将来的你或许也会投入到这些未知的领域当中, 为全世界的开发者作出自己的贡献.

面对数算OJ如同黑盒一般的测试，“基础设施”的重要性更是不言而喻。为了高效的解决挑战OJ时所遇到的各种问题，你可能还需要补充下面的一些知识
本人不保证下述内容的可靠性，欢迎纠错和与笔者讨论

基石

调试

善用工具
机器的效率和准确度往往比人高，比起瞪眼盯着自己写的代码半天看不出来个所以然，不如交给机器分步运行程序，自己则坐在一旁观察程序运行状态的变化来 Debug。
使用现代调试工具几乎是你想要通过OJ所必须要掌握的技能。程设课上所使用的 Visual Studio 自带调试工具。而笔者一般使用 vscode 插件，配合 gdb 进行调试。
另外，如果你会使用 g++ 或者 clang++ 之类的编译器进行手动编译，或者改 vscode 的配置文件来添加编译选项，那么笔者强烈推荐在编译选项中加入 -fsanitize=address 和 -g，这样如果程序出现了数组越界，访问空指针等非法操作，程序会能够中断并且反馈信息（会反馈的时候出现问题时程序执行到的位置），这有利于解决 RE 相关的错误
使用assert
在程序中使用 assert 宏来对程序的运行状况作出限定，能够更早的将问题暴露出来（譬如在访问 a[n] 前用 assert 检测 n 是否超出了数组范围，或者进行空指针检查，这样能比较好的追踪非法访问内存所产生的问题）

随机样例生成和 DiffTest

学会写python
python 是一种非常易用易学的编程语言，在这里你不用总是关心数组越界，int 溢出等问题，也不用被 c 和 c++ 里面一些不易用的东西困扰。用这样的一门语言写一些临时的小工具是相当好用的（比如后文将会提到的随机样例生成器）。
自己造样例
OJ 平台上所用的测试数据是不公开的，而自己手造样例仅仅在数据范围很小的时候可行（而且经常很烦人）。为了使用量大且复杂的数据对代码在本地进行测试（同时使用测试工具追踪 WA 或者 RE），自己手捏一个随机样例生成器相当重要。你还可以将生成器进行调教调整以生成不同特征的样例，进行针对性的测试

DiffTest
DiffTest，中文叫差分测试，俗称对拍，说白了就是找个“能保证结果是对的”程序，和我们自己写的程序的输出做对比，以此来发现问题所在。这样的程序对性能没有多高的要求，往往可以使用暴力方法求解答案。程序可以和随机样例测试结合起来，因为手算随机大样例的结果往往是不可行的。此外，有的时候程序仅在少数情况下结果出错，就更需要我们进行输出结果的对比，获得使得程序出错的样例，再使用调试工具进行进一步的检查。

发挥C++本身的潜力

C++ 提供了很多好用的数据结构和函数的模板，你可以在许多成熟的代码中发现他们的影子。
标准模板库帮你解决了很多问题，比如数组的排序可以使用 algorithm 头文件中的 std::sort() 函数来解决。
当然 STL 的用法太多了，有的时候也不一定适用于题目（可能带来额外的开销，比如电子系最喜欢的#include<iostream>爆内存），需要具体问题具体分析
除了 STL，C++的许多现代特性也能够加速你的开发进度，譬如自动类型推断和简化的for循环语法

std::vector<int> vec = (5,0);
for (auto num : vec)
{
    // Iterate through the vector
}

或者是 lambda function

1
2
3

std::sort(vec.begin(),vec.end(),[](int a,int b) -> int {
    return a > b;
});

增加代码的可读性

别随便命名
总有人喜欢用 abcd 或者中文拼音对变量或者函数命名，但是这种不能一眼看懂的命名往往会导致致命性的效率下降（用不了两分钟你就忘了之前写的变量 e 是什么意思了）
在这里笔者推荐两种常见的命名方法：

驼峰命名法

对于函数，类等的命名，每个单词首字母大写
譬如 GetVal, PriorityQueue
对于变量的命名，第一个单词首字母小写，后面的单词首字母大写
譬如 playerBlood，matrixIndex

下划线命名法

每个单词中间用下划线分割开来
比如 player_blood，get_val

善用宏和函数
假如你要求两个数的最大值，你第一时间想到的可能是

1	int max_num = a < b ? b : a;

那假如你要重复使用最大值的功能呢？

int max_num = a < b ? b : a;
max_num = c < h ? h : c;
max_num = d < i ? i : d;
max_num = e < j ? j : e;
max_num = f < k ? k : f;
max_num = g < l ? l : g;

你可能已经发现了，如果你要重复多次求不同的数对的最大值，写这样的一条表达式是一件非常痛苦的事情，而且这样的代码可读性很差
此时可以使用函数

int max(int a,int b)
{
    return a < b ? b : a;
}

int main()
{
    max_num = max(a,b);
    max_num = max(c,h);
    max_num = max(d,i);
    max_num = max(e,j);
    max_num = max(f,k);
    max_num = max(g,l);
}

这样写起来简单易读（当然更直接的是使用std::max）
对于求最大值这样比较简单的操作也可以使用宏替换
（使用宏的时候需要全大写，使用下划线分割单词）
（一定要注意使用宏的规范性，避免遇到一些难以调试的问题）

#define MAX(a,b) ((a) < (b) ? (b) : (a))
int main()
{
    max_num = MAX(a,b);
    max_num = MAX(c,h);
    max_num = MAX(d,i);
    max_num = MAX(e,j);
    max_num = MAX(f,k);
    max_num = MAX(g,l);
}

max别用宏定义！这里只是举例！
常用的常数也可以使用宏替换
嫌 long long 之类的太长了也可以用宏替换或者 typedef

#define VEC_SIZE 81*114514
#define uint32 unsigned int
typedef long long int64;
vector<int> stu_id(VEC_SIZE);
vector<uint32> stu_score(VEC_SIZE);
int64 stu_num;

开拓眼界

为了解决OJ中的难题，你可能需要使用各种阴间技巧或者课上没有教的算法。这些算法你可能可以在OI WIKI中找到。
尽量使用高效的搜索引擎（百度实在是太垃圾了）
具体代码方面的问题可以在 runoob 和 stackoverflow 等网站中搜索答案

最后再次提醒大家，人生很精彩，适度娱乐，拒绝内卷。祝各位OJ愉快！