OO第一单元总结

零、前言

　　本单元作业分梯度实现了“多项式求导”这个需求。第一次作业更多地是对Java语言的熟悉以及一些常用 工具/类 （如正则表达式和BigInteger）的使用；第二次作业则开始涉及继承、多态、接口等OOP底层逻辑；第三次作业无疑是第二次作业的进一步深入，以Oriented-Object解决更难的求导嵌套问题为例向我们展示了面向对象的强大实力（没错，是点题了）。

　　本文将从 度量分析 和 Bugs分析 和 发现别人Bug的策略 出发，对本单元的三次作业（尤其第二三次作业）设计过程进行了分析和反思，最后的 Summary 部分是对本单元的作业的总结，也有一些积累下来的经验想分享给大家。

一、度量分析

1.1. UML类图

1.1.1. 第一次作业

1.1.2. 第二次作业

1.1.3. 第三次作业

1.1.4. 设计分析&结构分析

　　我们这里将重点放在第二三次作业上对本次作业结构与设计进行分析。

1.1.4.1. 设计分析

　　谈到本单元设计的难点，就不得不谈谈输入的分析处理。抛开没必要细谈的具体实现，我对输入的分析处理有两个主要的想法：流水线 与 去随机。

　　首先是流水线，因为就“读一行数据并检测并处理”而言，个人认为是一件很面向过程的事情，所以就没追求必须用怎样设计类怎样继承封装这类面向对象的思路去解决输入处理问题，而是使用面向过程去模拟了这个行为。对于其中的各类动作，我将他们封装成一个一个的子过程，并依次有确定序地调用这些过程，这样就构造了一条输入处理的流水线。同时，因为这不是一条全速的流水线，所以我处理每个子过程的时候只考虑处理好一件小任务就可以了。

　　其次是去随机，这个想法基于我的两点认知，其一是“虽然我的每一个流水线子过程只处理一件任务，但如果我能把这件任务做得更好，那么下一个子过程处理任务就能有更小的压力”。其二有关学习组合数学时利用减法原理解决问题的思想（即利用补集解决问题），当出现首项符号“可能”忽略的情况，当出现第一个分量如果是1“可能”会忽略等等的随机情况时，我会在前期检测出来并补上这些被忽略的情况。这样就完成了去随机的过程。

　　基于上面的两个想法，我这次设计了一条慢速流水线来处理输入。虽然是慢速，但时间复杂度依旧是线性，也没有过多使用内存空间，因此不会出现资源过分消耗的情况。而使用去随机的设计，虽然无疑增加了工作总量，但是避免了某项子任务工作量过大的情况。

1.1.4.2. 结构分析

　　和大部分人类似，这次的基本结构是Polynomial-Term-Factor（Factor我称为Elem）的架构。但是在此之上有一些变化：比如为了给第三次作业的嵌套准备，我在第二次就将Polynomial抽化成Term的一个List的并引入Derivation类来具体刻画求导前中后的行为。再比如因为Term是我工作的重点，为了尽量减少工作量，我对所有Factor使用了一个统一的接口，以此在Term的视角下屏蔽掉我各个Factor（具体实现有多烂的现实）。

　　除此之外我还实现了其他的一些工具型类。比如第二次作业中用来描述项方便优化的三元组，再比如用来解决嵌套问题的嵌套队列类（这个类更进一步的功能将在4.2.中作为例子出现）。

1.2. 宏观规模

1.2.1. 第一次作业

1.2.2. 第二次作业

 第二次作业中我比较满意我使用接口数组处理求导问题的操作，此处贴出源码，以供学习交流：

public interface Elem {
    BigInteger getCoe();

    BigInteger getExp();

    boolean equal(Object ob);

    void setCoe(BigInteger c);

    void setCoeDefault();

    void setExp(BigInteger e);

    static boolean isPow(Object ob) { return (ob instanceof PowElem); }

    static boolean isSin(Object ob) { return (ob instanceof SinElem); }

    static boolean isCos(Object ob) { return (ob instanceof CosElem); }

    static boolean isHomo(Elem e1, Elem e2) {
        return  (isCos(e1) && isCos(e2)) ||
                (isPow(e1) && isPow(e2)) ||
                (isSin(e1) && isSin(e2));
    }

    Elem clone();

    List<Elem> derivate();
}

　　然后在各种具体实现里具体情况具体分析（以derivate函数（求导函数）为例）：

 幂函数、Sin函数、Cos函数求导实现：

    //derivate in PowElem
    @Override
    public List<Elem> derivate() {
        BigInteger tempCoe;
        BigInteger tempExp = BigInteger.ZERO;
        if (!exp.equals(BigInteger.ZERO)) {
            tempExp = exp.subtract(BigInteger.ONE);
        }
        tempCoe = coe.multiply(exp);
        List<Elem> temp = new ArrayList<Elem>();
        temp.add(new PowElem(tempCoe, tempExp));
        return temp;
    }

    //derivate in SinElem
    @Override
    public List<Elem> derivate() {
        List<Elem> temp = new ArrayList<Elem>();
        if (exp.equals(BigInteger.ZERO)) {
            return temp;
        } else if (!exp.equals(BigInteger.ONE)) {
            BigInteger tempInt = coe.multiply(exp);
            temp.add(new SinElem(tempInt, exp.subtract(BigInteger.ONE)));
        }
        temp.add(new CosElem(BigInteger.ONE, BigInteger.ONE));
        return temp;
    }

    //derivate in CosElem
    @Override
    public List<Elem> derivate() {
        List<Elem> temp = new ArrayList<Elem>();
        if (exp.equals(BigInteger.ZERO)) {
            return temp;
        } else if (!exp.equals(BigInteger.ONE)) {
            BigInteger tempInt = coe.multiply(exp);
            temp.add(new CosElem(tempInt, exp.subtract(BigInteger.ONE)));
        }
        temp.add(new SinElem(BigInteger.ONE.negate(), BigInteger.ONE));
        return temp;
    }

　　（直观感受比各种 if-else结构 好写+好读+好理解（OwO））

　　可以看到这里使用了getCoe() getExp() derivate() clone() 这些函数作为接口，直接作用是在Factor和Term这两层之间用这层接口隔离开来，Term视角下Elem是统一（接口）的，而Elem只需考虑自身接口实现，而不用过多考虑Term本身的限制。这样做有几点好处：

（1）Term与Elem之间的关系通过接口操作简单化，Term实现无需再考虑特殊种类Elem的限制，进而简化了Term的实现

（2）在后续扩展需求时，如果有更多种类Elem的需求，我只需在新的Elem里实现接口就可以了，从而不用对其他Elem和Term做出修改，降低了维护代价。

　　还可以看见我在接口中使用了一些“公用函数”，这些函数主要是与接口和实现Elem的类相关，与Elem接口实现无关，因此放在接口中更适合他们的定位。

1.2.3.第三次作业

1.2.4. 分析

　　总体而言，这次作业的代码量和类的功能强度正相关，并且功能相近的类长度也相近（废话）

1.3. 基于Metrics Calculation的度量分析

　　详细的Metric Calculation结果请移步附录A，这边仅截取一些数据主要对问题最暴露的第三次作业进行片面地分析。

　　各个Metric Calculation参数的意义：

　　下两图的第二列表示ev(G)第三列表示iv(G)最后一列表示v(G)。

　　可以看到，一些经常重复使用的类方法Essential Complexity 较高。部分方法Design Complexity较高的原因推测为一些工具型方法仅被该方法所调用。

　　类的方法的平均循环复杂度或类的方法的总循环复杂度较高的类往往经常或大量处理数组类数据。

二、Bugs分析

2.1. 使用多种方法进行版本控制

　　Bug核心：substring(int start, int end)方法第二个参数表示开区间。

　　在我开始做第二次作业的优化时我习惯地将工程clone了一份。然后在优化的时候发现了自己的一个bug（substring方法的第二个参数表示开区间），修复了之后没有将全部内容拷贝回原工程（有些类因为实际需求被大改了），出现了重大bug。

2.2. 过度优化

　　Bug核心：优化时忽略了输出也要按照输入的基本法

　　优化时忽略了输出也要按照输入的基本法来，并且部分数据还能通过怼拍器的校验就很惨。所以在处理嵌套问题时会将所有嵌套都提出来，于是就出现了sin(2*x)这样的输出QuQ，于是出现了重大Bug，虽然幸运通过了强测，但果然还是逃不过互测。总归还是自己分析问题太片面了，没有考虑到这个问题。

三、发现别人Bug采取的策略

3.1. 目力找bug

　　虽然被倡导多看多学习别人代码，但是比之往届一对一，7个人的全部代码要求两三天看完学习完找出bug显然在当前的学习情况下过于烧脑。所以这个方法仅限于对拍器拍出几个人的不同后用来确定bug的类型，也就是说这种方法只作为黑盒测试的补充。

3.2. 对拍器与黑盒测试

　　用随机数也好py也好造出来大量随机数据用来随机测试，将之前用来测试自己的边界数据以及压力测试数据作为补充。然后，对拍，俗称“机枪扫射”。正如概率论所学到的大数定理，大量随机的黑盒测试往往比看代码具有更高的效率。

3.3. Hack数据复用

　　使用自己用来Hack自己的边界数据，以及曾经Hack住自己的边界数据，往往有奇效。第二次测试曾使用一组观察组内人员优化程度的数据Hack住三个人。

四、Summary

4.1. 分离优化与实现过程（现有架构下优化）

　　在我做这几次作业的时候往往会将所有自己能考虑到的实现和优化问题都放在开始一起考虑，在作业结束之后我发现这样不是一个很好的策略。因为人的能力是有极限的。既没经验也没技术，想在开头就将一切都考虑到都考率往往会将自己困死在设计的开头，或者在实现的过程中忽略掉一些细节问题。

　　反思时我认为优化的过程应该放在实现之后（欢迎讨论），并且承认对于一个架构，优化是有限度的，过分追求优化而增补程序可能会让程序变得杂乱，也不方便进一步的更改。

4.2. 没有什么问题是增加中间层解决不了的

　　如果有，那就再加一层。 ——某OS老师

　　当我一开始接触嵌套表达式时，我是懵逼的，思索之后我发现直接处理嵌套多项式很麻烦（递归下降等暂且不表），于是我就依嵌套分层，将每层的嵌套先提出来依出现顺序组成队列，然后在嵌套位置留下标志，然后就可以轻松解析了，至于队列何时出队怎样组成嵌套项这类问题便是后话了，与具体实现有关，与主题无关，暂按下不表。

　　仔细想想其实流水线过程也是一个多次分层的过程（欢迎讨论），通过一层一层的处理成功将一个字符串转换成对象，每层处理的信息都是类似的，但相对于原始信息都规格化了不少。

附录A. Metrics Calculation详细情况

Metric Calculation信息，相对于1.3.节的分析此处更多地是选取了具有特征作用的信息，是对本单元三次作业的较深层次统计数据选取。

（截取部分显著信息的分析请移步1.3.）

A.1. 第一次作业

A.2. 第二次作业

A.3. 第三次作业