daicy
发布于 2019-04-17 / 1073 阅读
0
0

如何编写一个高效的Java表达式求值程序

当然,这个标题是有一点夺人眼球,但我确实这么做了(关于是否相信基准测试结果,这是另一个话题)。

所以,上周我一直在找一个小型、实用的计算数学表达式的类库。偶然间我在stackoverflow上看到了一个帖子,里面推荐的库(Expr)确实是很快而且基本拥有我需要的所有特性。但不幸的是,它不支持提供限制变量范围(在虚拟机里面,所有变量都位于一个全局命名空间)。

所以,我做了一件正常人不会做的事情:重新发明轮子,自己编写一个解析器和执行器。那是一个下雨的周六,我想到了用一个小型递归向下的解析器,一个简化了的、可以计算表达式的抽象语法树。抽象语法树使用一个小型变量管理助手,看起来也没什么大不了的。但它不是没有用。我做出一个初步的实现并且执行速度特别快。在进行了一些测试后,更让我充满信心,它执行的所有运算都正确无误。我想与最前面提到的类库相比,确认这个计算器到底有多快。在没有对每个内部循环和其他的执行进行优化前,我不报太大的期望,毕竟有不少类库是商业软件。所以当我看到测试结果的时候很惊讶。下面的清单展示了一个小的基准测试,使用不同的类库计算同一个表达式。 parsii 是我编写的库,测试时用的是最终版本。这个版本做了一些简化,比如预先计算了常量表达式。但是没有使用任何“黑魔法”,比如生成字节码或者其他类似的操作。

在性能评估中,一个用例是执行表达式”2 + (7 – 5) * 3.14159 * x^(12-10) + sin(-3.141)”。其中X的取值范围为0到1000000。测试时先运行10次,对JIT进行预热。然后再运行15次计算平均时间:

  • PARSII: 28.3 ms
  • EXPR: 37.2 ms
  • MathEval: 7748.5 ms
  • JEP: 647.0 ms
  • MESP: 220.8 ms
  • JFEP: 274.3 ms

现在我敢肯定,每一个类库都有自己的优势,所以不能直接对它们进行比较。尽管如此,令人吃惊的是一个简单实现的程序可以拥有这么好的表现。

如果读者对于编译器的原理不太了解的话,下面是一个关于编译器运行机制的简单介绍:

同其他的解析器或者编译器一样,parsii使用了传统的分词器。它将字符流转化成词法单元流,所以”4 + 38″,也就是字符数组’4′, ‘ ‘, ‘+’, ‘ ‘, ’3′ , ‘ ‘, ‘‘, ’8′被转化成:

  • 4 (整数)
  • + (符号)
  • 3 (整数)
  • * (符号)
  • 8 (整数)

分词器取到一个字符,接着判断是一个什么类型的词法单元,然后再读入这个属于词法单元的所有字符。每一个词法单元都有类型、文本内容并且知道起始位置(行号和字符)。网上有很多深入的教程,所以在这里就不详细讲解了。你可以看一下源代码,但正如我说的,它只是一个初步的实现。

解析器用来将传入的词法单元流翻译成可以执行的AST(抽象语法树),它是一个传统的自上而下递归解析器。这是实现解析器最简单的方式,完全手写,没有利用工具生成。像这样的解析器只拥有一个包含所有语法规则的方法。

同样,关于这种类型的解析器也有很多的教程,但是如何恰当地处理错误却缺少相关的示例。除了解析表达式的速度和正确性外,优秀的错误处理机制是一个优秀解析器的最核心因素之一。正如在源代码里看到的那样,实现起来并不是太困难。因为解析器在解析表达式的过程中从来不会抛出异常,
所有的错误都被收集起来,并且继续尽可能进行解析。即使在第一个错误发生以后已经不能成功解析生成AST,重要的是要能够尽可能的继续解析。因为在一次的执行中我们需要报告尽可能多的错误。这样的方法也同样用在了分词器报告上。比如报告非法格式的词法单元,例如带有2个小数点的浮点数,放到同样的错误列表中。

执行一个解析完成后的抽象语法树非常简单。每一个抽象语法树节点都包含一个计算方法,从根节点开始到父节点会调用这个它。这里的执行结果就是表达式的结果,一个简单的例子就是算数运算,包含了+、-、*等操作。

执行一个解析完成后的抽象语法树非常简单。每一个抽象语法树节点都包含一个计算方法,它的父亲从根节点开始调用此方法。算数运算,代表了+、-、*等操作。

为了减少执行时间,程序里运用了3种优化措施:首先,在完成解析AST后,在根节点上进行一个简化的方法调用,并且会扩散到每一个子节点。每一个节点判断自己的子表达式中是否有简化的表达形式。例如:对于算数运算,我们检查2个操作数是不是都是常量(数字)。如果是数字,我们将计算表达式并且返回一个包含计算结果的常量。对于函数,如果所有的参数都是常量的话,也会进行此类优化。

在表达式中使用变量时会执行第二种优化。这里使用map用来在需要的时候来对变量的值进行读写。这肯定是有效的,并且会进行很多次的查找。所以我们有一个叫做Variable类,它包含了变量名称和变量值。在进行表达式解析时,变量在作用域范围内(仅是一个map)只被查找一次,之后就可以一直使用。由于每次查找都返回相同的实例,所以在计算表达式值时变量的访问就像读写字段一样廉价,因为我们刚刚获取了Variable类的

第三个也是最后一个优化很可能不是经常起作用。但是由于易于实现,还是应用了这种尤华。它的功能基本上和名字“延迟运算”一样,主要用于函数调用。函数不会自动计算所有参数值,并且调用函数。而“延迟运算”会检查所有的参数,自行决定哪些参数需要计算。在if函数中可以看到它应用的实例。

parsii遵循MIT许可证授权。在GitHub上可以找到所有的源代码,并且包含了预编译的jar包。

原文链接: dzone 


评论