OO第三次作业快速化简的一点思考

写在前面

这篇文章主要介绍的是我在写OO第三次作业时对于加快化简的一点思考。
在化简的时候，最基础也最重要的就是如何判断两个对象是否相等，基于此我们才能进行各种🐺人化简。
一般的想法是对每个类重写equals函数，然后再通过递归调用eqauls函数判断两个对象是否相等。这种方法虽然直白，但是效率却低得惊人。
拿我的结构举例，我的结构是典型的expression-term-factor三层结构，在每一级结构中用ArrayList保存下一级的对象。如果要判断两个对象是否相等，我需要用O(n)的时间将两个对象的ArrayList中的元素一一比较，在比较的过程中还需要递归调用ArrayList中元素的equals函数，而在递归调用的equals函数中可能又要用O(n)的时间...这显然过于地低效。
为了解决化简的时候时间复杂度爆炸的问题，我想出了一种方法，它可以让你只需在构造表达式时进行一次递归，之后无需递归即可化简表达式。
附上此篇文章的CSDN博客连接

分析递归调用equals函数低效的原因

为了找到高效的算法，我们首先得找到平常的方法为什么低效。原因很简单：我们在判断两表达式是否相等时做了很多重复的工作。
举个🌰，如果我要判断sin((x + x)) * sin((x + x))是否和sin((x))*sin((x))提取公因子，我需要四步：

1. 首先我判断sin((x + x))是否和sin((x))相等，通过一次递归调用equals，我发现x != x，于是我判断它们不相等；
2. 然后我要比较sin((x + x))是否和sin((x))相等，又通过一次递归调用equals，我发现x + x != x，所以它俩也不相等；
3. 比较sin((x + x))是否和sin((x))相等...
4. 比较sin((x + x))是否和sin((x))相等...

因为每个表达式中有2个因子，所以在一一比较时我得比较4次，每次都需要递归调用equals函数。
然而我们很容易发现在上面的方法中我们做了很多重复的工作。当我们在第一步时已经对sin((x + x))进行了递归，分析了它的结构，然鹅在第二步中我们又对sin((x + x))进行了递归，又分析了一次它的结构。
所以我想：如果能用一种有效的表示方法记录对每个表达式结构的分析，那我们就只要在构建表达式的递归中用这种表达方式记录每个表达式的结构，这样在化简时就无需重复递归，只要比较两个表达式的结构是否相同就可以了。

我的方法

1. 创造一套记录结构的表达方式

首先我们得自己创造一个记录因子、项和表达式的表达方式，这样就方便我们在之后的化简中进行比较。这里分享我的表达方式。
我用字符串记录结构，并对因子、项和表达式分别创立了一套规则，规则如下：

表达式：字符串由 各项的字符串通过 +/- 号连接
为了有序化，各项的字符串以字典序排列

项：字符串由 各个因子的字符串通过 * 号连接
为了有序化，各因子的字符串以字典序排列

因子：
sin, cos,的字符串由 前缀+幂次+嵌套的东西的字符串 组成
sin: 用s作为前缀
cos: 用c作为前缀

x的幂次的字符串由 前缀+幂次 组成
x的幂次: 用x作为前缀

常数的字符串由 前缀+常数的值 组成
常数：用n作为前缀

举个🌰，比如我要表达sin(cos((2*x))) + cos(x)：

1. 将x表示为x2
2. 将2表示为n2
3. 将(2*x)表示为n2*x2(注意n2的字典序在x2之前)
4. 将cos((2*x))表示为c2n2*x2
5. 将sin(cos((2*x)))表示为s1c2n2*x2
6. 同上，将cos(x)表示为c1x1
7. 最后将sin(cos((2x))) + cos(x)表示为c1x1+s1c2n2*x2（注意 c1x1的字典序在s1c2n2x2之前)

2. 在构建表达式的递归中将每个因子、项和表达式用上述的方法表示出来

由于我们在构建是要用到递归，所以我们在构建表达式的同时可以很方便地将表达式用上述方法表示。
例如输入sin(cos((2x)))，首先我在字符串中添加s1作为前缀，然后递归调用构建类去构建cos((2x))，返回cos((2x))的字符串c2n2*x2。调用结束后我再将s1的前缀与cos((2x))的字符串c2n2*x2拼接即可得到sin(cos((2*x)))的字符串s1c2n2*x2。

3. 化简时：只需比较各字符串是否相同即可

用文章开头提到的🌰，我要判断sin((x + x)) * sin((x + x))是否和sin((x))*sin((x))提取公因子。我只需要以下四步：

1. 对比sin((x + x))的字符串是否和sin((x))的字符串相同；
2. 对比sin((x + x))的字符串是否和sin((x))的字符串相同；
3. 对比sin((x + x))的字符串是否和sin((x))的字符串相同；
4. 对比sin((x + x))的字符串是否和sin((x))的字符串相同。

看似与一般的方法一样需要四步，然而我在每一步判断时只需对比字符串是否相同就可以了，而不需要递归调用很多次equals函数。这样时间就大大缩短了，我们就不需要担心TLE而放弃很多🐺优化了。😂

写在后面

最后我得澄清一下，我并没有做🐺优化，因为当我想出这个方法的时候已经无限逼近于截止时间了...可谓是有心做🐺，无力回天了qwq。
之所以把这种方法写下来，是想把我的这个奇特的想法分享给大家，起一个抛砖引玉的效果，希望能对大家之后的作业有帮助。
当然这种方法也有很多可以改进的地方。比如将字符串包装成一个类，显得更加面向对象；比如用这种思路，把字符串操作改为位操作，从而通过hash值判断等等。
如大佬们有更加好的方法，欢迎提出讨论！