|
PSP2.1 |
Personal Software Process Stages |
Time |
|
Planning |
计划 |
|
|
· Estimate |
· 估计这个任务需要多少时间 |
8 |
|
Development |
开发 |
|
|
· Analysis |
· 需求分析 (包括学习新技术) |
0.5 |
|
· Design Spec |
· 生成设计文档 |
0.5 |
|
· Design Review |
· 设计复审 (和同事审核设计文档) |
0 |
|
· Coding Standard |
· 代码规范 (为目前的开发制定合适的规范) |
0 |
|
· Design |
· 具体设计 |
2 |
|
· Coding |
· 具体编码 |
4 |
|
· Code Review |
· 代码复审 |
0.5 |
|
· Test |
· 测试（自我测试，修改代码，提交修改） |
2 |
|
Reporting |
报告 |
|
|
· Test Report |
· 测试报告 |
0.5 |
|
· Size Measurement |
· 计算工作量 |
0.5 |
|
· Postmortem & Process Improvement Plan |
· 事后总结, 并提出过程改进计划 |
1.5 |
|
|
合计 |
12 |
0x01 设计
用一句话概括本次的需求，给小学生出算术题。考虑小学生的算术题，不难发现，其中所出现的数字仅仅包含整数和分数，且所有分数使用真分数的形式表示。每个算式由这些数字和运算符组成，其中运算符包括加、减、乘、除、小括号。不难发现，输出中的乘除号均为Unicode字符而非ASCII字符，所以本次使用C#语言来回避编码问题。（用C++的不要打我…）
根据这样的需求，可以选择构造一个层次结构：算式由数字组成。因此，首先需要实现的就是数字类和算式类。只要让这两个类具有随机生成的功能，本次需求便很容易实现。
对于数字类，我们知道整数可以表示成特殊的分数，即分母是1的分数。那么我们就可以用统一的形式来表示所有数字。
Class 数字 = {分子， 分母}。
那么输出怎么办？对于数字的输出，我们只需要重载一下ToString()方法便可以解决多种输出格式。在ToString()方法中，判断数字是整数、带有整数部分的真分数还是不带有整数部分的分数，选择相应的格式输出即可。
随后，重载数字类的加减乘除和比较运算，即可在代码中直接使用这些运算符。
有了数字，我们现在就要插入运算符，使之构成算式了。我们在学习中缀表达式计算的时候提到过，可以使用栈来记录运算过程。程序实现借鉴这个思想，构造数字栈和符号栈来模拟后缀表达式的运算，拼接成算式。为了更加有效的判重，我还引入一个数字变量来保存结果。
Class 算式 = {数字栈， 符号栈， 运算结果}，
需要注意的一点是，与后缀表达式不同，使用两个栈来保存算式，运算符和数字的关系是不确定的，这时就需要我们人为地规定符号与数字的顺序关系才能保证可以计算出所有情况。对于输出，依然是重载ToString()方法，对两个栈进行拼接。
判定两个算式是否相等，其实就是判定每一步的运算是否相等。因此，两个算式相等的充分必要条件是，符号栈完全相等，且每次运算中的两个运算数分别相等。也就是说，在判定相等时，需要还原两个表达式求值的全过程进行比较才行。这样显然是很慢的，后面会讲到一个非常有效的优化。
0x02 测试
本次程序模块清晰非常适合于进行模块化测试。本次程序中，对于每一个模块方法都有单元模块测试，可以确保在不触发异常的情况下可以返回正确的结果。（由于时间有限，一场处理部分没有进行测试。）对于程序全局功能的测试，采用极端数据和大数据量的方法，都得到了正确的返回结果。
0x03 优化
判重：前面说到，判重的过程是非常慢的，因为要完全还原每一步的运算状态。那么能不能找到一个有效的方式来大概率加速判定呢？答案是肯定的。对于每个算式，我们进行一次计算，保存下来计算的结果。对于任意两个结果不同的算式，显然是不能经过有限次交换一样的。事实证明，这样的优化可以加快80%左右的判定时间。以单次判断为基本单位，程序的时间复杂度为O(n^2)，因此即使优化以后，判断依然是耗费时间最多的执行单元。
输出：本次程序的输出为文本文件，每次输出一个算式和一个结果。由于两步输出是连续操作，如果每次直接输出到文件，会由于硬盘响应速度较慢造成阻塞。因此可以选用Buffer作为输出缓冲，提高性能。这种方式在输出量较小的情况下（如连续执行100000次，每次输出20个算式）对性能有明显改进。
计算结果：本次需求中要求，所有算式在运算过程中不能出现负数，因此在判定过程中就顺带完成了结果的计算。这样可以省去写求结果的方法，直接服用check即可。
0x04 测试
正常数据测试：
-r 10 –n 10000
-r 3 -n 100
极端数据:
-r 1 -n 100
-r 2 -n 10000000000
-r 1000000 -n 100
0x05 总结
本次工程难度不大，但需求数量较多。在实现需求之前，需要统一的设计来满足不同需求的实现。设计在本次工程中起到了非常大的作用。除此以外，本次工程还充分体现出了有一个属于自己的类库的重要性。
补充：性能分析图如下，即便是优化后的算法，大量的时间依然花费在算式判重的问题上。这里可以考虑对每个表达式进行最小转换后进行Hash，使用Set来进行优化。
