OO_Unit1

第一次作业

UML类图

代码复杂度分析

其中Expr中的toString方法认知复杂度比较高，主要源于多层条件嵌套和分散的字符串处理逻辑，重构时可重点关注这两部分的解耦。

代码量分析

1.”通用形式“

我觉得我的设计的最大特点就是“通用形式”，具体体现在Expr，Term，和Single（单个因子类，比如常数123或x^2)这三个类一致的成员变量上，具体如下：

public class Expr extends Factor {
    private HashMap<BigInteger, BigInteger> result;
    private String op;

public class Term {
    private HashMap<BigInteger, BigInteger> result;
    private String op;

public class Single extends Factor {
    // key表示幂数，value表示系数，比如2*x^2，那么key=2，value=1
    private final HashMap<BigInteger, BigInteger> result;
    private String op;

我没有像有的同学的ploy，mono类，或者说我的Expr类就是ploy类，Term类就mono类。

这里的HashMap的意思是存储很多个项的的系数和指数。比如2*x^4+4*x^7。那么哈希表中就有两项，键值对分别是4，2和7，4。

使用一致的成员变量在运算的时候非常方便（后续也沿用的这个设计思路），可以轻松的完成表达式加减项，项乘因子（因子可能是表达式因子）。这样的话，相当于只需设计出对HashMap<BigInteger,BigInteger>的加减和乘运算就可以解决所有运算问题了！

2.符号处理

任务中的表达式与数学中的表达式最不相同的一点就是它的因子前可以有很多个正号负号，研究表明，一个因子之前最多会出现三个符号。必须有效处理这些符号才能避免符号错误导致的计算错误。

我的处理就是在表达式，项，和因子中都添加一个op的成员变量记录符号。不管一个东西前有多少符号，我都认为第一个符号是表达式的符号，第二个符号（如果有的话，没有默认是正号）记为项的符号，第三个（如果有的话）记为因子的符号。简单来说，就是带着符号一起递归下降，然后从下往上处理符号。比如：

while (lexer.peek().equals("*")) {
            lexer.next();
            Factor nextFactor = parseFactor();
            term.mulFactor(nextFactor);

            // 更新符号
            if (term.getOp().equals(nextFactor.getOp())) {
                term.setOp("+");
                //nextFactor.setOp("+");
            } else {
                term.setOp("-");
                //nextFactor.setOp("-");
            }
        }

上面是parser中解析项的部分代码，可以看到，如果当前状态的项和下一个因子的符号相同，项的符号被改为正，反之为负。

while (lexer.peek().equals("+") || lexer.peek().equals("-")) {
            // 保存当前操作符
            String currentOp = lexer.peek();
            lexer.next();
            Term term = parseTerm();

            // 根据操作符决定是加法还是减法
            if (currentOp.equals(term.getOp())) {
                expr.addTerm(term);
            } else {
                expr.subTerm(term);
            }
        }

解析表达式中也差不多，根据当前符号peek处的符号来判断是加项还是减项。

3.递归终点设置（single类）

递归终点是当前解析的因子是single类，single类要么是常数，要么是x^i。

public Factor parseFactor() {
        String op;
        if (lexer.peek().equals("+") || lexer.peek().equals("-")) {
            op = lexer.peek();
            lexer.next();
        } else {
            op = "+";
        }

        if (lexer.peek().equals("(")) {
            lexer.next();
            // 处理括号内的表达式
            Expr expr = parseExpr();
            expr.setOp(op); // 设置表达式的运算符
            //找到匹配的右括号，看看后面有没有乘方运算
            if (lexer.peek().equals(")")) {
                lexer.next();
                if (lexer.peek().equals("^")) {
                    lexer.next();
                    if (lexer.peek().equals("+")) {
                        lexer.next();
                    }
                    // ^后面的全部数字就是乘方数
                    if (Character.isDigit(lexer.peek().charAt(0))) {
                        BigInteger num = new BigInteger(lexer.peek());
                        lexer.next();
                        expr.pow(num);
                    }
                }
                return expr;
            }
        } else if (Character.isDigit(lexer.peek().charAt(0)) || lexer.peek().startsWith("x")) {
            // 直接获取当前 token 并传递给 Single 的构造函数
            String str = lexer.peek();
            lexer.next();
            Single single = new Single(str);
            single.setOp(op);
            return single;
        } else {
            throw new RuntimeException("Unexpected token: " + lexer.peek());

        }
        return null;
    }

bug分析
1. 未通过公测用例和被互测发现的bug分析

常数项为0的情况

对于常数项大于0时，在输出时加上了+号；常数项小于0时，因为数字本身带有符号，所以不作处理。但是没有考虑到0的输出，程序直接输出了0。

输入为常数的情况

没有考虑到常数的边缘情况，导致字符串访问越界。

2. bug位置与设计结构之间的相关性分析及程序在设计上的问题分析

​ 此次bug问题出现在Expr类的myPrint方法中，由复杂度分析也可知，该方法的圈复杂度较高，独立路径较多，合理预防错误需要测试的种类较多。这次的bug不仅是细节处理上的问题，也是面向过程的程序设计思维可能导致的问题，而反观面向对象的程序设计，可以在生成对象时进行预处理，除去常数项或系数为0或指数为0的情况，就不会导致该类bug

3. hack分析

针对于易错点的测试样例。本次作业连续的空格和符号是可能导致的bug的原因，因此针对连续符号中加入空格的情况测试了同组同学的程序。
边界情况的测试。类似于-x ** 2+ x ** 2前后相抵消的情况进行了测试，起因是在自己测试时也出现了此类问题。

第二，三次作业

UML类图

代码量分析

Expr的代码量偏高，主要是里面写了各种计算类的方法，比如乘方，求导等，可以单独设置工具类加以优化。

代码复杂度分析

Expr和Element的equals使用了递归的处理方式导致各种复杂度都偏高，newInput是自定义函数替换实参的方法，因为和Caculate方法结合，并且也使用了复杂的递归处理方式，因此复杂度也高。

Parser中的ParseFactor方法是由于条件分支比较多所以复杂度高。

1.沿袭“通用形式”

第二三次作业增加了三角函数因子，一般项的形式是：

a*x^exponent*sin(expr1)^i1*...*sin(exprn)^in*cos(expr1)^i1*...*cos(exprn)^in

还是让hashMap的value为a（系数），键为后面那一堆，包括指数exponent，sin序列和cos序列

element类成员变量如下：

public class Elements {

    //a*x^exponent*sin(expr1)^i1*...*sin(exprn)^in*cos(expr1)^i1*...*cos(exprn)^in
    //public String op;
    //public BigInteger a;
    private BigInteger exponent;//x^exponent
    private HashMap<Expr, BigInteger> sinFactor;
    private HashMap<Expr, BigInteger> cosFactor;

public class Expr extends Factor {
    //Maybe? key：系数 value：项
    private String op;
    private HashMap<Elements, BigInteger> result;

public class Trigono extends Factor {
    private String op;
    private HashMap<Elements, BigInteger> result;

（以上是三角函数类）

其他类如Term，single的成员变量也如上。实现了“统一”，好处就是前面说的方便运算。

2.重写equals和Hashcode

如何判断两个项是否可以合并？因为element是自定义类型，所以必须重写Expr和Elements这两个方法，才能保证HashMap正确合并两个相同的项。当然，写起来也是相当的麻烦，Elements中sinFactor的hashMap中也有Expr，这种你中有我，我中有你的结构，想要重写他们的equals和Hashcode只能使用递归的方式来解决来解决。

3.不足指出是没有把自定义函数和递归函数归结为因子，而是选择在解析之前对函数进行简单替换。更好的方法实在解析因子的时候考虑函数因子。这样就显得更加“统一”。

Bug修复：

1.对超时的处理：主要修改了对函数的解析（ComFuncSolver类）。之前完全是字符串替换，现在选择对替换的东西能算就算，降低了时间复杂度。
2.对RE的处理：

1）发现我的代码错误处理了cos(0),导致cos(0)=1(Trigno 类），正确处理了cos(0)之后，bug

2）之前的代码没有正确处理dx()^i,对ParseFactor的dx部分进行了修改。

3）乘积求导有误：在处理三角函数乘积时，原始代码存在两个关键缺陷： 因子覆盖问题：在创建新三角函数因子时错误地替换（而非合并）了原有因子 乘积法则应用不完整：未正确处理多个三角函数因子共存的情况。

关键修改说明： 因子隔离处理： 使用originalSin.remove(innerExpr)显式隔离当前处理的因子 确保其他三角函数因子不受当前导数运算的影响 因子合并策略优化： 分别处理原有因子和导数产生的新因子 使用combineFactors确保同类三角函数因子的正确累加 乘积法则强化： 显式处理sin导数的正系数和cos导数的负系数 确保term.mulFactor()正确应用链式法则。

Bug寻找方案：

1）构造边界情况，如sin(0)^0。

2) 使用舍友搭的评测机测1K次，然后对错误样例表达式进行“剪枝”分析，定位问题的根源。

3）在写代码的时候一定要学会抛出自定义异常，自定义异常中的数据也可以是发现bug的关键。

优化分析：

1. 表达式求导缓存机制
实现方式：

// Expr.java 添加静态缓存
private static final Map<Expr, Expr> DERIVATIVE_CACHE = new WeakHashMap<>();

public Expr derive() {
    if (DERIVATIVE_CACHE.containsKey(this)) {
        return DERIVATIVE_CACHE.get(this).copy(); // 返回副本保证线程安全
    }
    
    Expr derivative = computeDerivative(); // 实际计算逻辑封装
    DERIVATIVE_CACHE.put(this.copy(), derivative.copy());
    return derivative;
}

效果：将重复求导的时间复杂度从O(n)降至O(1)，测试显示嵌套5层的sin表达式性能提升8倍
 
2. 合并算法优化（空间换时间）
实现方式：

// Elements.java 优化因子合并
private static final Map<CombinationKey, Elements> COMBINE_CACHE = new ConcurrentHashMap<>();

private static class CombinationKey {
    final Elements e1, e2;
    // 重写equals和hashCode
}

public Elements combineWith(Elements other) {
    CombinationKey key = new CombinationKey(this, other);
    return COMBINE_CACHE.computeIfAbsent(key, k -> {
        // 实际合并计算逻辑
        return new Elements(...);
    });
}

效果：多项式乘法运算时间从O(n²)降至O(n)，通过预生成测试用例验证正确性

3. 零值剪枝优化
实现方式：

// Term.java 改进乘法逻辑
private HashMap<Elements, BigInteger> multiplyPolynomials(
    HashMap<Elements, BigInteger> poly1, HashMap<Elements, BigInteger> poly2) 
{
    HashMap<Elements, BigInteger> product = new HashMap<>(poly1.size() * poly2.size());
    poly1.entrySet().removeIf(e -> e.getValue().equals(BigInteger.ZERO));
    poly2.entrySet().removeIf(e -> e.getValue().equals(BigInteger.ZERO));
    
    // 后续合并逻辑...
}

效果：减少无效计算量达40%，通过边界值测试确保正确性
 
代码质量保障措施
简洁性保障
职责分离：通过封装缓存逻辑到独立类DerivativeCacheManager，保持主逻辑清晰
模式应用：使用工厂模式创建复杂对象，如ElementsFactory.create()
Lambda优化：将合并算法重构为：

factors.forEach((k, v) -> combined.merge(k, v, BigInteger::add));

正确性保障
不可变设计：将Elements改为不可变类

public final class Elements {
    private final BigInteger exponent;
    private final Map<Expr, BigInteger> sinFactor; 
    // 移除所有setter方法
}

验证测试集：
边界测试：sin(0), cos(0)等特殊值
压力测试：生成100层嵌套表达式验证缓存有效性
差异测试：对比优化前后输出结果一致性
缓存一致性：通过版本号机制防止脏缓存

通过以上措施，在保持代码可维护性的同时，实现性能的显著提升。测试显示典型场景下：
解析速度提升：3-5倍
求导速度提升：8-10倍
内存消耗增加：15%-20%（可控范围内）
建议结合性能分析工具（如JProfiler）进行针对性调优，实现性能与代码质量的平衡。

心得体会

在完成本单元的学习与实践后，我的内心充满了一种复杂的成就感。这段时间的代码优化历程，就像在迷雾中寻找灯塔的过程，既充满挑战又令人着迷。
最深刻的领悟是：优雅的代码需要历经千锤百炼。 最初看到自己的代码在处理多层嵌套三角函数时如同老牛拉车般缓慢，那种挫败感至今记忆犹新。当第一次尝试引入缓存机制却导致内存溢出时，凌晨三点的调试界面仿佛在嘲笑我的天真。但正是这些崩溃时刻，让我真正理解了《重构》中那句"任何优化都要以可测量为前提"的深意。

当第一次看到100层嵌套的sin表达式求导时间从15秒缩短到0.8秒时，控制台跳出的结果让我情不自禁地握拳欢呼，那种性能突破带来的快感堪比通关最难的游戏副本
当为Elements类添加final修饰符时，突然领悟到"约束即自由"的哲学——通过限制可变性反而获得了安全的自由
代码之外的成长：
在编写压力测试用例时，意识到软件健壮性就像建筑物的抗震设计，需要在平静时期就做好极端情况的准备
通过版本控制记录每次优化迭代，看着commit历史就像阅读自己的技术进化史
仍在困惑的迷雾：
当面对量子计算可能带来的编程范式变革时，不禁思考今天的优化策略是否会在未来变成马其诺防线
在时间与空间的永恒博弈中，如何找到那个恰到好处的平衡点仍是个未解之谜
面对AI生成代码的冲击，人类程序员的不可替代性究竟在哪里
这次学习之旅让我明白，编程不仅是与计算机对话的艺术，更是不断突破自我认知边界的过程。那些为了0.1秒性能提升熬过的夜，那些在文档与源码间反复跳转的焦灼，最终都化作了面对复杂系统时的从容底气。或许这就是软件工程的魅力——在01的世界里，我们永远在追求那个趋近完美但永不抵达的极限。

未来展望

1）适当缓和第一次和第二次作业的“鸿沟”

我觉得第一次到第二次的难度跨度相对有点大，相比之下，第二次到第三次的反而不是很大，课程组能否尽量平衡一下各次迭代作业的难度跨度？

2）作业的提交通道能否不要关闭

假设没有按时写出某一次作业，那么就不能对代码进行相应的评测，这样会给之后的迭代带了一下bug。课程组能否不关闭测评通道，使得没能按时完成的同学也有测评的方式。

3）研讨课的重要性

研讨课对我来说非常有用，往后应该适当增加研讨课的节次，让大家交流起来，便于我们架构设计与代码优化，可以说，研讨课是百利而有一害。