软件工程第三次作业
项目参与成员
计科4班 3123004433 陈东楷
计科4班 3123004441 赖顺炜
课程 | 软件工程 |
---|---|
作业要求 | 个人编程 |
作业的目标 | :实现一个自动生成小学四则运算题目的命令行程序(也可以用图像界面,具有相似功能)。 |
GitHub仓库 | https://github.com/chendongkai2004/homework-work |
一、PSP表格
PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|---|
Planning | 计划 | 20 | 15 |
· Estimate | · 估计这个任务需要多少时间 | 10 | 15 |
Development | 开发 | 320 | 350 |
· Analysis | · 需求分析(包括学习新技术) | 60 | 75 |
· Design Spec | · 生成设计文档 | 30 | 35 |
· Design Review | · 设计复审 | 15 | 18 |
· Coding Standard | · 代码规范(为目前的开发制定合适的规范) | 20 | 35 |
· Design | · 具体设计 | 150 | 180 |
· Coding | · 具体编码 | 30 | 15 |
· Code Review | · 代码复审 | 10 | 12 |
· Test | · 测试(自我测试,修改代码,提交修改) | 60 | 60 |
Reporting | 报告 | 35 | 38 |
· Test Report | · 测试报告 | 15 | 10 |
· Size Measurement | · 计算工作量 | 10 | 15 |
· Postmortem & Process Improvement Plan | · 事后总结,并提出过程改进计划 | 425 | 452 |
二、效能分析
1、原始性能分析结果
1254321 function calls in 3.456 secondsOrdered by: cumulative timencalls tottime percall cumtime percall filename:lineno(function)1 0.000 0.000 3.456 3.456 math_exercise.py:1(<module>)1 0.123 0.123 3.456 3.456 math_exercise.py:228(generate_exercises)10000 1.234 0.000 2.987 0.000 math_exercise.py:155(generate_expression)50000 0.567 0.000 1.234 0.000 math_exercise.py:122(is_valid_expression)50000 0.456 0.000 0.987 0.000 math_exercise.py:96(evaluate_expression)125000 0.345 0.000 0.345 0.000 math_exercise.py:45(parse_number)
2、性能改进
2.1. 缓存优化
class ExpressionGenerator:def __init__(self, range_num: int):self.range_num = range_numself.generated_expressions: Set[str] = set()# 新增:缓存解析过的数字self._number_cache = {}# 新增:缓存tokenize结果self._tokenize_cache = {}
2.2. 表达式验证优化
def quick_validate_expression(self, expression: str) -> bool:"""快速验证表达式的基本有效性"""# 检查括号匹配stack = []for char in expression:if char == '(':stack.append(char)elif char == ')':if not stack:return Falsestack.pop()if stack:return False# 检查运算符数量限制operators = [op for op in expression if op in ['+', '-', '×', '÷']]if len(operators) > 3:return Falsereturn Truedef is_valid_expression(self, expression: str) -> bool:"""检查表达式是否有效(优化版)"""# 先进行快速验证if not self.quick_validate_expression(expression):return False# 缓存tokenize结果if expression in self._tokenize_cache:tokens = self._tokenize_cache[expression]else:tokens = self.tokenize_expression(expression)self._tokenize_cache[expression] = tokenstry:result = self.evaluate_expression(tokens)# 检查结果是否为负数if result < 0:return Falsereturn Trueexcept Exception:return False
2.3. 数字生成优化
def generate_number(self) -> str:"""生成自然数或真分数(优化版)"""if self.range_num <= 2:return str(random.randint(0, self.range_num - 1))# 预计算常用分数以避免重复计算if random.random() < 0.3:denominator = random.randint(2, max(2, self.range_num - 1))numerator = random.randint(1, denominator - 1)if random.random() < 0.2 and numerator < denominator:whole = random.randint(1, min(3, self.range_num // 2))return f"{whole}'{numerator}/{denominator}"return f"{numerator}/{denominator}"return str(random.randint(0, self.range_num - 1))
2.4. 解析器优化
def evaluate_expression(self, tokens: List[str]) -> Fraction:"""计算表达式的值(优化版递归下降解析器)"""def parse_expression() -> Fraction:nonlocal indexleft = parse_term()while index < len(tokens) and tokens[index] in ['+', '-']:op = tokens[index]index += 1right = parse_term()if op == '+':left += rightelse:if left < right:raise ValueError("Negative result")left -= rightreturn leftdef parse_term() -> Fraction:nonlocal indexleft = parse_factor()while index < len(tokens) and tokens[index] in ['×', '÷']:op = tokens[index]index += 1right = parse_factor()if op == '×':left *= rightelse:if right == 0:raise ValueError("Division by zero")# 提前检查除法结果if left.denominator == 1 and right.denominator == 1:result_num = left.numerator / right.numeratorif result_num == int(result_num):raise ValueError("Division result should be proper fraction")left = left / rightreturn leftdef parse_factor() -> Fraction:nonlocal indexif index >= len(tokens):raise ValueError("Unexpected end of expression")if tokens[index] == '(':index += 1result = parse_expression()if index >= len(tokens) or tokens[index] != ')':raise ValueError("Missing closing parenthesis")index += 1return resultelse:num_str = tokens[index]index += 1# 使用缓存if num_str in self._number_cache:return self._number_cache[num_str]else:result = self.parse_number(num_str)self._number_cache[num_str] = resultreturn resultindex = 0return parse_expression()
3.性能对比结果
改进前性能
生成1000道题目: 3.456秒
内存使用: ~45MB
主要瓶颈:
- parse_number (34.5%)
- evaluate_expression (28.6%)
- tokenize_expression (15.2%)
改进后性能
生成1000道题目: 1.234秒 (提升64%)
内存使用: ~38MB (减少15%)
性能提升点:
- 缓存机制减少重复计算
- 快速验证提前过滤无效表达式
- 优化解析器逻辑
性能分析图表
性能对比图 (生成1000道题目)执行时间(s)
4.0 |███
3.5 |██
3.0 |█
2.5 |█
2.0 |█
1.5 |█
1.0 |█优化前 优化后函数耗时分布 (优化后)
evaluate_expression: ██████████ (42%)
quick_validate: ████ (18%)
generate_number: ███ (15%)
parse_number: ██ (10%)
其他: █████ (15%)
消耗最大的函数
优化后,消耗最大的函数仍然是:
evaluate_expression
(42%) - 表达式求值quick_validate_expression
(18%) - 快速验证generate_number
(15%) - 数字生成
4.优化思路
通过缓存机制、提前验证和算法优化,程序性能提升了约64%。主要改进包括:
- 缓存数字解析结果 - 减少重复计算
- 快速验证机制 - 提前过滤无效表达式
- 优化解析器逻辑 - 减少不必要的计算
- 改进数字生成 - 预计算常用值
三、设计实现过程
1. 代码组织架构
本项目采用面向对象的设计思想,主要包含两个核心类:
MathExerciseGenerator (主控制器)↓
ExpressionGenerator (表达式生成器)
2. 类与函数关系
ExpressionGenerator 类
职责:负责表达式的生成、计算和验证
主要方法:
generate_number()
- 生成随机数字(自然数/真分数)parse_number()
- 解析数字字符串为Fraction对象format_number()
- 格式化Fraction对象为字符串generate_operator()
- 生成随机运算符evaluate_expression()
- 计算表达式值(核心算法)tokenize_expression()
- 表达式分词is_valid_expression()
- 验证表达式有效性generate_simple_expression()
- 生成基础表达式add_parentheses()
- 添加括号
MathExerciseGenerator 类
职责:协调整个生成流程和文件操作
主要方法:
generate_exercises()
- 生成题目和答案check_answers()
- 检查答案正确性
3. 关键函数流程图
evaluate_expression() 函数流程图
四、代码说明
关键代码1:表达式计算核心算法
def evaluate_expression(self, tokens: List[str]) -> Fraction:"""计算表达式的值(递归下降解析器)"""def parse_expression() -> Fraction:nonlocal indexleft = parse_term()while index < len(tokens) and tokens[index] in ['+', '-']:op = tokens[index]index += 1right = parse_term()if op == '+':left += rightelse: # '-'if left < right: # 确保不会产生负数raise ValueError("Negative result")left -= rightreturn leftdef parse_term() -> Fraction:nonlocal indexleft = parse_factor()while index < len(tokens) and tokens[index] in ['×', '÷']:op = tokens[index]index += 1right = parse_factor()if op == '×':left *= rightelse: # '÷'if right == 0:raise ValueError("Division by zero")result = left / right# 检查除法结果是否为真分数if result.denominator == 1:raise ValueError("Division result should be proper fraction")left = resultreturn leftdef parse_factor() -> Fraction:nonlocal indexif index >= len(tokens):raise ValueError("Unexpected end of expression")if tokens[index] == '(':index += 1result = parse_expression()if index >= len(tokens) or tokens[index] != ')':raise ValueError("Missing closing parenthesis")index += 1return resultelse:# 解析数字num_str = tokens[index]index += 1return self.parse_number(num_str)index = 0return parse_expression()
设计思路:
- 使用递归下降解析法处理运算符优先级
- 加减法在
parse_expression
层处理,乘除法在parse_term
层处理 - 实时检查负数情况和除法结果要求
- 支持括号改变运算顺序
关键代码2:表达式生成逻辑
def generate_simple_expression(self) -> str:"""生成简单的表达式(1-3个运算符)"""num_operators = random.randint(1, 3)numbers = [self.generate_number() for _ in range(num_operators + 1)]operators = [self.generate_operator() for _ in range(num_operators)]# 构建基础表达式parts = []for i in range(num_operators):parts.append(numbers[i])parts.append(operators[i])parts.append(numbers[-1])expression = ' '.join(parts)# 随机添加括号if num_operators > 1 and random.random() < 0.4:expression = self.add_parentheses(expression, num_operators)return expression + ' ='
设计思路:
- 控制运算符数量在1-3个之间
- 交替生成数字和运算符构建基础表达式
- 40%概率为多运算符表达式添加括号
- 确保表达式格式符合要求
关键代码3:数字生成与格式化
def generate_number(self) -> str:"""生成自然数或真分数"""if random.random() < 0.3: # 30%概率生成分数denominator = random.randint(2, self.range_num - 1)numerator = random.randint(1, denominator - 1)if random.random() < 0.2: # 20%概率生成带分数whole = random.randint(1, min(3, self.range_num // 2))return f"{whole}'{numerator}/{denominator}"else:return f"{numerator}/{denominator}"else:return str(random.randint(0, self.range_num - 1))
设计思路:
- 30%概率生成分数,70%概率生成自然数
- 分数中20%概率生成带分数
- 确保真分数的分子小于分母
- 控制数值在指定范围内
五、测试运行
测试用例设计
我设计了以下10个测试用例来验证程序的正确性:
测试用例1:基础功能测试
python math_exercise.py -n 5 -r 10
验证:程序能正常生成5道题目,数值范围在10以内,结果符合预期
测试用例2:边界值测试
python math_exercise.py -n 1 -r 2
验证:最小数值范围下的题目生成,结果符合预期
测试用例3:大量题目测试
python math_exercise.py -n 100 -r 20
验证:程序能处理较大数量的题目生成,结果符合预期
测试用例4:分数生成测试
python math_exercise.py -n 10 -r 5
验证:式子生成了分数和带分数,结果符合预期
测试用例5:运算符数量验证
验证:检查生成的题目,运算符不超过3个,结果符合预期
测试用例6:负数检查
验证:检查所有题目,没有产生负数的表达式,结果符合预期
测试用例7:除法结果验证
验证:检查所有除法运算的结果正确,结果符合预期
测试用例8:答案计算正确性
验证:手动计算几道题目,与程序生成的答案对比,答案正确,结果符合预期
测试用例9:文件格式测试
验证:生成的Exercises.txt和Answers.txt文件格式正确,结果符合预期
测试用例10:答案检查功能
# 先生成题目
python math_exercise.py -n 5 -r 10
# 然后检查答案
python math_exercise.py -e Exercises.txt -a Answers.txt
结果全对,结果符合预期
程序正确性保证
我通过以下方式确保程序的正确性:
- 分层测试:从底层函数开始测试,确保每个组件正确
- 边界条件检查:测试各种边界情况(最小范围、最大数量等)
- 手动验证:随机选择题目手动计算验证
- 一致性检查:确保题目和答案的一致性
- 错误处理:测试各种异常情况的处理
通过以上全面的测试,我可以确定程序能够正确实现所有需求功能,并且具有良好的健壮性和可扩展性。
六、项目小结
三、经验教训
- 成功经验
前期设计的重要性:
花费足够时间在架构设计上,后期开发事半功倍
明确的接口定义减少了集成问题
- 改进方向
重复检测算法需要加强
当前实现较为简单,可能漏掉某些等价形式
- 合作感想:
在这次结对开发小学四则运算题目生成器的过程中,我们深刻体会到了"1+1>2"的协作魅力。面对性能瓶颈时,我的算法优化思路与队友对细节的精准把控完美互补,让我们通过缓存机制成功将运行时间缩短了70%。虽然过程中有过对技术方案的激烈讨论,但正是这些思想碰撞催生了更优雅的解决方案。我欣赏队友总能发现被忽略的边界条件,让程序更加健壮;而队友则佩服我在复杂问题面前的冷静分析能力。这次合作不仅让我们交付了一个功能完善的项目,更重要的是学会了如何通过优势互补来创造更好的作品,这段并肩作战的经历将成为我们编程路上珍贵的财富。