揭秘你处理数据的“底层逻辑”,详解公式引擎计算(一)

2021年09月15日 阅读数:1
这篇文章主要向大家介绍揭秘你处理数据的“底层逻辑”,详解公式引擎计算(一),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

背景

身处信息时代之中,咱们最能明显感觉到的一点就是密集数据大量爆发,人们积累的数据也愈来愈多。这些庞杂的数据出如今一块儿,传统使用的不少数据记录、查询、汇总工具并不能知足人们的需求。更有效的将这些大量数据处理,让计算机听懂人类须要的数据效果,从而造成更加自动化、智能的数据处理方式。算法

为了处理这些海量数据,出现了各类大数据引擎、搜索引擎、计算引擎、3D引擎等,用以更好解决数据庞杂带来人工没法处理的问题。而做为其中比较基础的计算公式引擎,是在计算程序中负责对数据进行处理的核心部分。接下来咱们将展开介绍计算引擎的基本原理、计算链和异步函数构成,并从计算公式引擎的基本概念出发,用咱们的表格电子组件做为例子,为你们演示这些内容如何在JavaScript中实现。后端

公式引擎的计算原理

计算引擎负责解决数据来源的统计,数据的操做,数据的管理,并将合适的计算结果按照要求给予返回。针对数据处理的目的不一样,须要返回的内容不一样,也有很对多应不一样的类别。数组

为了实现让计算机更好的识别咱们须要的处理操做,须要进过编译的过程,将咱们书写的语言翻译成机器能够识别的语言。异步

而整个编译阶段的流程,按照过程划分是按照下图进行的:函数

其中比较关键的两个环节是词法分析、语法分析的过程,在这两部分会将咱们的输入逐渐拆分,转化为程序可以识别的内容。工具

输入内容后,编译器先对内容进行词法分析,在这一步编译器的任务是识别源程序中的单词是否有误,编译程序中实现这种功能的部分通常称为词法分析器。一般词法分析的输出是一个个单独的单词符号。大数据

以JS为例,在这个过程当中有三个主要部分:分析函数参数、分析变量声明、分析函数声明。语法分析阶段的目的是识别出源程序的语法结构(即语句或句子)是否错误,这一阶段一般能够发现语法的错误。在这个阶段中,编译器实际处理的是来自词法分析得出的单词符号。搜索引擎

而在计算公式引擎中咱们处理数据的方式和编译原理中处理语言这一过程极度类似,从实际应用出发实现一个相似Excel的计算公式的计算公式引擎,咱们能够采用的思路是从词法分析出发,将完整的长串公式语句拆分红小块内容,而后再进行语法分析,最后对生成语法结构树进行运算。接下来让咱们一块儿看看细节如何实现。翻译

公式引擎的实现细节

咱们从公式计算开始为你们说明,公式计算即由一个公式字符串进行计算后,得出表达式结果。好比:公式“=1+10*11”
计算后获得结果111。电子计算机并非人类,这样一个简单的表达式想要彻底正确计算,最终变成咱们须要的数据内容,并非简单的咱们看一眼后,口算就获得答案。实现这样类Excel表格计算的功能,须要经过词法分析,语法分析,语法结构树计算这几个过程。blog

1. 词法分析

中经常使用的公式进行说明。

首先咱们进行词法分析,在这个过程当中咱们将公式字符拆成字符串数组,在Excel表格公式计算中,表达式的公式字符串中只包括:运算符、符号、字符串、数字、数组、引用、名称这几类。

名称:sum

运算符:( ) :/ % +

引用:A1 A11 B1

数字:100

2. 语法分析

词法分析完成以后,咱们对词法分析的结果进行进一步语法分析。一般计算中语法分析能够采用表达式树或者堆栈(即逆波兰式)来处理。

这里咱们先介绍表达式树的方法。

语法分析——表达式树

使用表达式树进行分析的过程,从一棵二叉树开始。首先咱们将词法分析的结果按照优先级组成表达式树,表达式树的叶子结点就是操做数,内部节点是操做符。

在这个事例中,冒号的优先级最高,其次是括号,最后是除号。当这棵树造成以后,就离咱们拿到最终的运算结果很接近了。

咱们会采用递归调用的方式对这颗树进行运算,从根结点出发,到sum,一直向下递归,到A1:A11时,有了第一个结果,而后逐层返回计算结果。

这就完证的展现了如何实现一个公式计算。

语法分析——逆波兰算法

逆波兰算法是在语法分析阶段造成了一个堆栈(即逆波兰表达式),这个表达式的核心在于将普通咱们是用的中缀表达式转换为后缀表达式。括号在运算的过程当中只进行运算顺序的提示,但并非实际参与计算的元素内容,因此在中缀转后缀的过程当中就能够省略掉括号内容,

而后由计算机编写代码完成运算。

这里展现了一棵树转化成对应的逆波兰式的样子。

二叉树递归VS逆波兰算法

与一棵树递归计算相比,逆波兰式更符合数学计算的习惯。但实际在项目中处理这种公式计算的时候,到底哪种更加能处理更复杂的状况呢?

让咱们来看一个多层嵌套的公示内容:

这个公示的使用场景是SUMIFS函数多列求和,等价于下面这个内容:

=SUMIFS($C:$C,$B:$B,$A1)+SUMIFS($D:$D,$B:$B,$A1)+….

很明显上面的公式更加简单,采用二叉树递归的方式,只须要判断SUMIFS节点的父节点以及孩子结点内容,只须要短短一行代码就能够搞定这个多列求和。

可是若是是用逆波兰算法,代码一开始遇到SUM就开始计算,很难断定SUM此时要运行的内容其实在最内层括号之中。能够解决,但却并非最简单的。

对比结果

与堆栈的方式相比,树的解法更容易扩展、加强,能够更加轻松应对复杂的公式。这在处理大量公式、复杂计算就是得天独厚的优点。

总结

在介绍完如何解析并进行公式计算的全过程以后,接下来咱们会继续介绍在公式计算引擎中计算链和异步函数的相关内容。在处理复杂公式时,有向图如何求解,calcOnDemand解法又是什么,还有在先后端计算中异步函数的花式用法。

以为不错点个赞再走吧~后续还会为你们带来更多有趣的内容~