多符号表达式的共同子表达式提取教程

生成的符号表达式，可能会存在过于冗长的问题，且多个符号表达式中，有可能存在相同的计算部分，如果不进行处理，计算过程中会导致某些算式计算多次，从而影响计算效率。

那么多个符号表达式生成函数时，如何将多个符号表达式中相同算子提取出来，以便实现计算效率的提升？

一种方案是：共同子表达式提取（Common Subexpression Elimination，CSE） ，即找到多个表达式中相同的子表达式，并将其提取出来。这可以通过建立一个表达式树或图的数据结构，然后检测重复的子树来实现。一旦发现相同的子表达式，你可以将其计算结果保存起来，而不是多次计算。这通常需要对表达式进行遍历和分析。

1. Python实现（推荐）

在Python中，可以利用sympy中的cse实现，案例如下：

from sympy import symbols, cse, expand# 定义符号变量
x, y, z = symbols('x y z')# 创建一些符号表达式
expr1 = x**2 + y**3 + x**z
expr2 = x**2 - y**2 + 5*x**z
expr1 = expand(expr1)
expr2 = expand(expr2)combined_expr = [expr1, expr2]# 进行共同子表达式提取
common_subexpr, simplified_expr = cse(combined_expr)# 打印提取出的共同子表达式
print("共同子表达式：", common_subexpr)# 打印简化后的表达式
print("简化后的表达式：", simplified_expr)"""
Output:
>> 共同子表达式： [(x0, x**2), (x1, x**z)]
>> 简化后的表达式： [x0 + x1 + y**3, x0 + 5*x1 - y**2]
"""

2. MATLAB实现

• 法1：利用subexpr，优点：可读性强；缺点：不够简洁，原因是该函数一次只能提取1个变量，为此，可以考虑进行多次迭代提取，可参考MATLAB加速计算：符号表达式——子表达式法，代码传送门

  clear
  A=str2sym('[a b; c d]')
  [V,D]=eig(A)subexpr([V;D])
  

• 法2：将符号表达式保存成.m文件，利用MATLAB Coder生成C，生成的C中会自动进行CSE处理。但可读性差

在 MATLAB 中，共同子表达式提取（Common Subexpression Elimination，CSE）通常由 MATLAB 编译器自动处理。MATLAB 的 JIT（Just-In-Time）编译器会尝试优化你的代码，包括检测和消除共同的子表达式以提高执行效率。


MATLAB 中 JIT 编译器的工作原理如下：

• 解释执行和分析： 初始时，MATLAB 会解释执行你的代码，并进行一些分析以了解哪些表达式是重复计算的。
  
  
• JIT 编译： 一旦 MATLAB 确定了可能的优化机会，它会对代码进行 JIT 编译。这时，MATLAB 将生成优化后的机器代码。
  
  
• 执行优化后的代码： 在 JIT 编译之后，MATLAB 将执行优化后的代码，其中可能包括共同子表达式提取等优化。
  
  
  虽然 MATLAB 的 JIT 编译器会尝试进行一些优化，但并不保证在所有情况下都能实现最优的共同子表达式提取。在某些特殊情况下，你可能需要手动考虑一些优化策略，如使用局部变量来存储重复计算的结果。
  
  
  总的来说，MATLAB 通常会在后台自动处理共同子表达式提取，而无需显式的用户干预。如果你对具体的代码片段有疑虑，可以使用 MATLAB 的 Profiler 工具来分析代码性能，并查看是否存在潜在的优化机会。

---

参考链接：

• https://docs.sympy.org/latest/modules/simplify/simplify.html#sympy.simplify.cse_main.cse
• https://zhuanlan.zhihu.com/p/673052435