Summary Ⅰ( 二 )


Term内项的有序性可以有效缓解项合并的复杂性,准确来说,既方便了同类项的查找匹配以及插入或者合并,又方便了顶层Expr的合并 。
这里仅简述狭义优化,具体的实现过程见下文实现阶段 。
广义优化:
广义“优化”不仅包含最后对于结果的处理,还包含实现过程中对于思维的优化,后者与递归下降的本质息息相关 。所以先来谈谈对于递归下降的见解 。
** 递归下降
显然,递归下降的本质为递归函数,不过并非传统意义上的单递归函数,如(斐波那契数列,爬楼梯),而是综合型递归,也就是在朴素递归中引入了更多的分支,易感乱花渐欲迷人眼 。但是,如果我们在每次进行分支时,就像老师说的,只想当前一步,就不会错乱 。
下面我们来看下这个庞大的递归函数的结构:
哪个是递归函数呢?顶层的函数;
递归参数?字符串;
函数返回值?Expr变量;
递归出口?->->
递归内部实现? ->->
递归体现在哪里?一般来说,递归函数会调用自己进行递归,那么这个递归函数的递归特性体现在哪里呢?中 判断出后调用,实现自我调用,凸显递归本质 。
那么,递归是如何紧紧依赖优化的?前面说的追踪递归容易跟丢,又是怎么回事?
随着这个问题的抛出,我们也来到了本单元作业的核心:字符串展开问题 。
首先回答上面的问题,“哪个类需要提供展开功能?”,固然是三个因子:Func,Der;Func,Der这两个因子都不是最简形式,化简完之后的结果必然是Expr;同时,由于我们只是做了初步展开,所以化简之后的Expr并不是最简形式,因此,Expr类要有合并功能 。
至此,我们完成了对于题目的局部分析,接下来需要进行实际的操作来串联各个组件,以验证上述思路的可行性 。
摆在我们面前的问题是:什么时候进行展开,什么时候合并,在哪里进行优化?
顺藤摸瓜,从递归函数开始推理 。
(+,-) -> (*) ->
{ , , , ,} ->
(*) -> (+,-)
第三步得到之后,该被pull入Term中,pull的过程需要进行同类项合并,此处,对Term中的进行sort 以及merge,便于快速合并同类项,不同的,有不同的merge方法,注意,在此处不需要展开Expr,Func,Der因子,一个简单的设计原则是,非必要 。接下来,Term被呈递到Expr处(+,-),可以看到此时来到了处理流程的最后一步,Expr的合并 。因此,Func,Der,Expr要在此时进行展开,并且展开到最简形式 。但是,我们在Expr处的视野里只有Term,所以,这个展开函数应该是针对Term的 。这也告诉我们,展开的位置和展开的对象不是必然相同的 。Term中,我们需要展开每个,并将这些复杂的都转化为Expr,此处的原因是归一化处理,由于Expr,Func等因子展开后的形式极有可能是Expr形式,因此对于Term中的每个,我们都选择展开为Expr,并且在Term方法中实现展开后的合并优化 。
第三部分-- Bug集中分析:
(三次作业中发现的Bug主要集中在第二三次作业 。)
第一个属于失误Bug,原因是自己并没有删去用于本地测试时的提示信息输出,导致输出冗杂;第二个Bug出在优化问题上,对三角函数内部表达式的优化稍欠考虑,错认为其内部表达式的第一个项为三角因子则整个表达式即为三角因子,优化的目的是为了去掉三角函数可能存在的冗余括号,却不慎缺少了必要的括号;
第一个bug是:在三角因子优化的时候,由于其内部被设计为了表达式,因此递归调用可以得到理论上的最简形式,但是,由于优化处理,导致优化后的Expr.并不能得到最简形式,比如1+cos(0),经过处理后得到1+1,却忽略了1+1还可以继续进行合并,这属于处理上的不当 。因为自己写的也是不断调用Term和的得到字符串并进行拼接,并没有再深一步考虑得到的这些因子之间在化简之后可能的合并关系,本质上属于架构问题,优化之后的项并没有进行彻底有效的合并,甚至将一部分优化放在了字符串转换上,这样得到的结果是只是形式上的优化,并不是实体优化 。因此最终得到的字符串并不是最简字符串,中间递归调用得到的字符串也不是最简的,很可能导致优化出问题 。