shepherdwind

How to realize velocity template interpreters

前言

承玉曾经写过一篇文章构建前端DSL,文中提到:

从本质上看模板也是一个微型语言,因此可以从 DSL 的角度着手,使用工具快速构建一个适合于特定前端框架的模板引擎。

本文讨论的话题和承玉的差不多,相信大家都知道coffeescript,handlerbars。承玉的DSL和handlerbars类似,我完成了一个模板语言velocity的解析,更接近coffeescript的编译。在此,与大家分享一些经验,如果你也希望知道coffeescript语法解析如何完成的,那么,这片文章应该对你有所帮助。

让我们回顾一下2010年D2的时候,Hedger介绍了Closure Compiler,老赵的jscex,他们有一个共同点,都是对js进行编译,让js运行更快或者提供一起额外的功能。编译这么一个似乎和JavaScript没有关系的话题,却逐渐被越来越多的人提起。

本文主要介绍如何用js写一个编译器,这看起来似乎很高级,实际上,编译原理很复杂,写一个编译器却不怎么难,在做这个模板编译之前,我个人对于编译原理完全不知道的,因为看到coffeescript语法是Jison生成的,然后尝试了一下。写一个编译器,其实就是把一些语法规则翻译成计算机能够理解的结构,计算机所能理解语法规则有专门的描述语言,Yacc + Lex。IBM上有文章如此描述:

Lex 和 Yacc 是 UNIX 两个非常重要的、功能强大的工具。事实上,如果你熟练掌握Lex 和 Yacc 的话,它们的强大功能使创建 FORTRAN 和 C 的编译器如同儿戏。

Yacc + Lex的一个实现是Bison,09年Zach Carter为了研究编译原理课程,用js完成了Bison的实现Jison, 承玉的kison类似。故事就讲到这里,什么是Yacc,Lex,Bison,Jison,Kison,都不重要,重要的是,这些技术使得我们可以使用简单的方式完成复杂的字符串解析(比如编译)任务。现在我们要来实现一个编译器了,看完就知道这一切了。

在此声明,对于编译的理解仅限于个人理解,如有不对之处,欢迎指正。

Lex & Yacc

Lex和Yacc主要用于解决编译中的第一个问题,源文件从字符串变得有意义(结构化数据)。这个过程,又分为两个步骤:

  1. 源文件拆分成各种标志(tokens) Lex
  2. 构造数据结构 Yacc

学习英语的时候,我们都会遇到语法问题,对于陌生的语言,需要知道其语法规则,计算机语法规则与自然语言类似,只是自然语言是与上下文有关的语言,比起计算机语言复杂得多。与上下文无关,其实就是语言的符号意义是确定的。扯远了,举个例子,一个正常的英语句子:

What you name?

回到英文课堂,老师会说,句子是由主语+谓语+宾语构成,这个句子构成的元素是,主语you,谓语what,宾语name,谓语动词前置构成疑问句,疑问句结束用问好。这样的一个语法规则,让计算机理解,需要依据上面的两个步骤:

  1. 识别单词,也就是英语中的主语、谓语和宾语,好吧这些背单词的时候记住就行。标点符号也是词法元素。
  2. 语法识别,上面的句子对应的语法是:谓语 + 主语 + 宾语 + 问号 => 疑问句

    词法识别和英语学习中背单词一样,计算机通过正则在字符串中匹配词,构成语言的基本结构,这些结构按照一定组合规则构成语法。Yacc所做的,是把扫描一串字符串,识别其中的词,把词和所描述的语法一一对照,然后能够得到一些结构化的数据,比如上面英语,计算机就能够知道,这是一个疑问句,疑问句的三个成分是what、you、name,至于这个句子什么意思,你应该如何处理,这是编译过程的第二步了。

velocity syntax

上面简单描述了一下原理,现在开始写语法规则分析器吧。写编译器就是把一套语法规则描述清楚,就像翻译一篇说明书。当然,我们首先需要能明白说明书的意义,本文以velocity模板语言为例,velocity是Java实现的一套模板,是阿里集体后端webx框架的模板语言,语法规则文档,可以大致看下语法,或者点击此处在线尝试vm解释过程。

vm(velocity简称)语法规则很简单,大概开5分钟就能学会,vm虽然简单,但是也是一套比较基本的计算机语言的实现了,对比下,英语我们学习了10年,还没能学好,vm只需要5分钟,自然语言的复杂度,比起计算机语言实在不是一个数量级。

#set( $foo = "Velocity" )
Hello $foo World!

vm语法分为两部分,第一部分是vm语法内容,另一部分是字符串,模板语言都是如此,字符串部分无需考虑,原样输出即可,vm语法主要是前者结构分析。上面的vm输出Hello Velocity World!。语法部分,主要分为两部分References和Directives。

References 和 Literal

References是vm中变量,解析时References输出为变量对应的值,模板语言最基本的功能也就是变量替换,vm同样如此,只是vm还有一些其他复杂的功能。Literal和js里面的字面量一直,是vm里面的基本数据结构。vm是一个模板语言,变量的值可以来自外部,而且是主要数据来源,References和Literal这两者构成了vm语法的基本数据。

References基本形式是$foo,或者加一些修饰符$!{foo}。复杂形式是,变量+属性,支持的属性方式有三种:

  • Properties 最普通的属性$foo.bar
  • Methods 方法$foo.bar(),因为方法是有参数的,参数由References和Literal构成
  • Index 索引$foo['bar'],index可以是字符串,也可以是变量References

上面三种方式和js的对象属性查找方式一样,因为存在Methods和Index,方法和Index本身又可以包含References,引用的组成部分可以是引用。这样式描述形成了递归,语法一般都是通过递归的形式来相互包含。引用(References)里包含自身,这如果使用普通的字符串匹配,逻辑上会有些晕。

Literal是基本的数据结构,分为字符串、map(js中的对象)、数字、数组。map的值由Literal 或者References构成,数组元素同样,字符串和数组相对简单,可以直接从源文件中匹配得到。到此,应该大致明白编译的复杂了吧,就这些基本的数据结构相互包含,要理清其中结构,还是很麻烦的吧,虽然我们可以一眼就知道这些结构,如何让计算机明白,就不那么容易了。不过,通过yacc,我们只需要描述清楚这些结构就行,怎么理清其中关系,Jison会自动处理的。

Directives

前面引用和字面量部分,是vm中关系最复杂的结构了,Directives是一些指令,包括逻辑结构和循环,模块之间引用加载等运算。这些结构比较好搞定,一般都是各自不相干,不像上面,相互引用,纠缠不清。vm解析,最复杂的还是在于引用的确定。

Directives分为单行指令和多行指令,单行指令作用范围是一句,比如#set#parse,多行指令主要是#macro,#foreach,if|else|elseif,这些都是通过#end来结束,这样的区分可以在语法分析阶段完成,也可以在后期处理。

语法分析

本文有些长,已经开始靠近目标了。上面描述语法的过程,是非常重要的,使用yacc描述语法规则,就是对输入源分类的过程。经过上面的分析,yacc的已经差不多构思好了,接下来把规则用yacc语法写下来就好。

在写yacc描述之前,需要做一件是,lex词法分析。词法分析就是要找到上面说的References、Literal、Directives的基本元素。新建一个文件velocity.l,开始写lex描述。

References

从References开始,vm里面引用的最主要的特征是符号$,首先假设有一个vm字符串:

hello $foo world

其中,$foo是References,很明显References是美元符号开头,$后面跟字母,这里需要引入状态码的概念,因为$后面的字母的意义和$前面的字母意义是不一样的,那么当扫描到$以后,可说我们处于不同的状态,区分好状态,就可以专心处理之和vm语法,否则同样的一个字符,意义就不一样。这个状态,我们用mu表示,状态吗可以随意命名,使用mu,是有渊源的,handlerbars的lex文件因为继承了Mustache语法,mu表示Mustache语法开始,我参考了handlerbars,所以用mu

velocity.l写下:

%x mu

%%
[^#]*?/"$"         { this.begin("mu"); if(yytext) return 'CONTENT'; }
<mu>"$!"           { return 'DOLLAR'; }
<mu>"$"            { return 'DOLLAR'; }
<INITIAL><<EOF>>   { return 'EOF'; }

%x声明有的状态码,状态码和字符串或者正则表达式组合成一个特征,比如&lt;mu&gt;"$",双引号表示字符串,这个特征描述表示,mu状态下,遇到$,返回DOLLAR。我们用DOLLAR描述$,至于为什么我们要给$一个名字,再次回到英语中,我们会把单词分为名词、动词,各种分类,语法规则不会直接处理某个特定的词如何组合,而是规定某一类词的组合规则,比如,最普通的句子,主语+谓语+宾语,主语一般是名词,谓语是动词,宾语也是名词,这样描述要简单得多,lex词法分析是给字符做最小粒度的分类,最终,一个vm输入源码,可以归纳到一个分类里,符合英语语法的字符串,我们统称为英语。

特征都使用全大写字母,这是一种约定,因为在yacc描述中,语法规则名都用小写。%%后面第一行,[^#]*?/"$",这是一个正则表达式,正则分为两个部分,第一部分 [^#]*?匹配所有不是符号#的字符,后面一部分"$",中间反斜杠分割,是一个向后断言,匹配美元符号前面所有不是符号#的字符,也就是遇到没有符号的时候,后面通过 this.begin开始状态mu。这里使用到yytext,就是前面正则所匹配到的内容,有个细节,这个匹配去除了#,因为#是另一种状态Directives的开始,这里暂时只讨论引用识别。最后一行,表示结束返回,这个无需理解。

引用的最基本形式,$ + 字母,美元符号识别了,接下来识别后面的字母,使用正则表达式

 <mu>[a-zA-Z][a-zA-Z0-9_]*   { return 'ID'; }

如此,我们可以用这两条规则,开始写第一条yacc语法规则了:

reference
   : DOLLAR ID
       { $$ = {type: "references", id: $2} }
   ;

上面描述的是reference,由lex中返回的DOLLAR和ID组合成为一个reference,大括号里面写的是js代码,用于构造结构化数据,需要什么样的数据可以自己随便搞,$$表示返回结果, $1是DOLLAR词对应的字符串,也就是$$2表示第二个词,也就是ID。复杂的reference可以继续写:

reference
  : DOLLAR ID
  | DOLLAR ID attributes 
  ;

attributes
  : attribute 
  | attributes attribute 
  ;

attribute
  : method 
  | index 
  | property 
  ;

property
  : DOT ID 
  ;

index
  : BRACKET literal CLOSE_BRACKET 
  | BRACKET reference CLOSE_BRACKET 
  ;

reference在原来的基础下,增加了attributes,attributes是由一个或者多个属性组成,在yacc中,使用attributes attribute来描述多个属性的情况,规则直接包含自身的情况还是非常常见的。attribute由 method,index,property 组成,继续拆分,index是两个中括号加一个literal或者 reference 组成,我们可以继续对literal进行分类,同样的描述。我们回到了上面对vm 语法描述的那个分类过程只不过,现在我们使用yacc的语法描述,前面使用的是自然语言。

解析过程

上面讲了那么多,现在来总结一下Jison解析一个字符串的过程。用一张图表示吧:

lext

词汇分析过程就是上面所描述的了,一个lex文件,构成一个词汇表,通过从左到右的扫描输入源,依次匹配词汇表里面定义的模式,然后构成一个个词汇。得到词汇之后,那什么是语法呢,还记得英语语法吗?在计算机里面,语法就是上面所描述的,词汇的组合,规定了词汇的组合形式,比如DOLLAR ID组成一个reference,写yacc语法规则就是不断的对语法进行分类,直到所有的分类最底层都是lex中的词汇,然后语法规则也就ok了。程序会自动根据yacc文件所有定义的规则,分析得到输入源对应的数据结构。

velocity最终的语法描述在这里

状态码

上面简要描述了yacc和lex工作原理过程,实际中,还是会遇到一些有意思的问题。在写vm解析器的时候,最麻烦的事情是,如何保证括号和中括号的匹配,首先看一段vm字符串:

$foo.bar($foo.name("foo")[1])
$foo.bar([)]

经过分析,我发现括号匹配的一个特点是,括号的闭合状态下,它的前一个状态肯定是括号开始,中括号同样如此。因此,我在velocity.l中再引入两种状态,i, c,分别表示括号开始和中括号开始,在匹配到括号或者中括号结束的时候,判断前面的一个状态是否是符号的开始,这样,就能保证括号和中括号的配对。

在lex词汇分析中,状态码是一个堆栈,这个堆栈通过this.begin开始一个状态,this.popStat退出一个状态,词汇可以是多种状态和正则表达式进行组合,状态的开始和结束,需要自己控制,否则可能会有问题。

解析最终得到一个对象,这个对象的构造是根据velocity.yy而生成的。如何选择合适的数据结构,这个是很很重要的,后面的语法树解释过程,完全取决于解析器所返回的语法树。在velocity的语法树,最终得到的是一个一维数组,数组的元素分为字符串和对象两种,如果是对象,那么是vm语法需要进行分析解释的。

语法树解释

得到输入源语法结构之后的工作,相对而言就容易了,这其中会涉及到两个点,我个人觉得比较有意思的。第一个是局部变量,在vm语法中,有一个指令#macro,这个是vm的函数定义,由函数,自然有形参和实参,在函数执行过程中,形参是局部变量,只在函数解析过程中有效,#foreach也会形成一个局部变量,在foreach中有一个内部变量$foreach.index, $foreach.count, $foreach.hasNext这样的局部变量。

局部变量的实现,可以参考lex语法分析过程,在语法树解释过程中,增加一个状态码,当进入一个foreach或者macro的时候,生成一个全局唯一的条件id,并且在状态中压入当前的条件id,当foreach和macro运行结束后,推出一个状态。foreach和macro控制状态,同时构造一个数据空间,贮存临时变量,在vm解析过程中,所有的变量查找和设置,都是通过同样的一个函数。当一个变量查询时,检测到存在状态时,首先依次根据状态码,找到对应状态下的局部变量,如果需要查询的变量在局部环境中找到,那么返回局部对象对应的值,如果是这是值,同样如此。这样的实现和js所中的函数执行上下文有点类似,可以继续想象一下如何实现避包,实现避包其实只需要在一个函数中返回一个函数,这样的语法在vm中没有,不过如果真的可以返回一个函数,那么只需要在这个函数和当前函数执行所对应的状态放在一起,并且不释放状态对象的局部变量,那么避包也就有了。

结束

本文到此要结束了,不知道是否有说明白,具体实现细节可以参考velocity.js源码

一次有意思的内部讨论-sku组合查询算法探索

在前端领域,很少会遇到算法问题,这不能说不是一种遗憾。不过,随着前端处理的任务越来越复杂和重要,偶尔,也能遇到一些算法上的问题。本文,所要讨论的,就是这样一样问题。

什么是SKU

问题来自垂直导购线周会的一次讨论,sku组合查询,这个题目比较俗,是我自己取得。首先,看下什么是sku,来自维基百科的解释:

最小存货单位(Stock Keeping Unit)在连锁零售门店中有时称单品为一个SKU,定义为保存库存控制的最小可用单位,例如纺织品中一个SKU通常表示规格、颜色、款式。

让我们假设在淘宝上,有这么一个手机,如下表格所示:

颜色容量保修期限屏幕大小电池容量
红色4G1 month3.71500mAh
白色8G3 month41900mAh
黑色16G6 month4.32100mAh
黄色64G1 year 2500mAh
蓝色128G   
sku: 白色 + 16G + 3 month + 3.7 + 2100mAh就这么一款可以提供5种颜色,5种容量,4种保修期限, 3种屏幕尺寸,4种电池容量的手机,我们假设它存在,叫xphone。表格中,加粗的5种属性,组合在一起,构成一个sku。现在,应该清楚什么是sku了吧。可以把xphone的规格参数看成一个JS的构造器,每一个sku,对xphone函数进行实例化,返回的一个对象就是一个sku。不过,这和一部手机的概念有一些区别,一个sku对应多个手机,sku是描述手机的最小单位,比如说学校,在学校里面最小教学单位是班级,那么一个班级可以看做一个sku。

问题描述

下面,为了描述问题,我首先假设一个产品属性组合2x2,用[[a, A], [b, B]]表示,那么,sku组合为[ab, Ab, Ab, AB],也是2x2,4个sku。现在我们知道sku对应的数目和价格,依然用js对象来描述为:

{
    ab: {amount: 10, price: 20}
    aB: {amount: 10, price: 30}
    AB: {amount: 10, price: 40}
}

这个的数据说明了,Ab是没有货存的,ab, aB, AB分别有10个货源在。那么,当用户对商品进行选择的时候,如果首先选择A,那么,b应该显示为不可选择状态,因为Ab是没有货的。同样,如果选择了b,那么A应为灰掉,因为Ab还是没有值的。可能的几种状态如下:

初始状态
属性1:
属性2:
1. 选中b,A禁止
属性1:
属性2:
2. 选中A,b禁止
属性1:
属性2:
3. 选中AB,价格为40
属性1:
属性2:

问题:用户选择某个属性后,如何判断哪些属性是可以被选择的。当sku属性只是2x2的时候,还是很容易计算的。但是,如果情况变得复杂,比如4x4x4x5这样的情况,要判断用户的那些行为是可行的,还是会复杂很多的。下面看算法实现吧,还是用2x2这种最简单的形式作为参考。为了方便描述,下面使用result = {ab: ...}表示sku对应的价格和数目的数据对象,使用item表示一个sku属性下的一个元素,items = [[a, A], [b, B]]表示所有sku属性元素。

算法演示

首先来一个演示吧,仅支持高级浏览器。对于第一算法,使用正则匹配,不是很完善,有些不准,仅仅是演示,正则表达式写的不好,不用在意。

下面灰色按钮表示不可选,白色表示可选,红色为选中状态。演示框最下面是可用的sku组合。

第一种算法[正则]:
共进行323次运算,耗时2ms
属性1:
属性2:
属性3:
属性4:
属性5:
属性6:
属性7:
第一种算法优化方式[除法]:
共进行387次运算,耗时1ms. result乘积最大为67672188866017
属性1:
属性2:
属性3:
属性4:
属性5:
属性6:
属性7:
可选择的路线:
3:23:83:101:137:179:227
11:53:67:131:157:191:251
7:29:73:127:167:211:257
17:47:71:103:151:199:241
3:41:89:107:151:223:257
19:53:83:109:163:199:229
13:43:79:101:173:211:239
19:47:67:127:157:191:229
3:37:61:107:167:223:251
2:31:89:97:151:199:257
13:29:59:113:149:193:227
11:41:73:103:173:181:263
19:43:89:103:151:197:263
3:53:83:107:149:199:241
11:29:71:131:157:211:233
13:31:61:113:173:181:229
2:37:83:127:137:211:251
17:53:89:97:151:191:229
3:31:73:103:167:193:239

第一种算法

初始条件
已知所有sku属性的数组items和sku所对应的价格信息result
用户选择了item B,使用数组selected=['B']表示,selected可以为空数组
算法过程
1. 循环所有sku属性forEach(result, (curitems, attr)-&gt;),使curitems等于属性对应的所有元素,attr等于属性id。
2. 克隆数据attrSelected = selected
3. 判断属性attr中是否有元素在数组attrSelected中,如果存在,从attrSelected去掉存在的元素
4. 循环属性下的元素forEach(curitems, (item)-&gt;,使得item等于单个属性的值
5. 把 attrSelecteditem组合成sku
6. 循环result,判断第五组成的sku在result中是否存在,如果存在,退出循环4,返回true,进入步骤8
7. 当前item设置为灰色,标志不可选择
8. 当前item为可选属性元素
9. 循环4和循环1完成,所有item状态标注完成,算法结束

这个方式是最普通的算法实现了,非常直接,一个一个判断所有的item是否可以被选中,判断依据是itemselected的元素组合的sku是否在result数组中存在。在我们上面的例子中,在初始化的情况下,用户没有选中任何元素,那么循环过程,只需要判断a, b, A, Bselected是否存在。如果,用户选中了b,那么循环过程中,依次判断的sku组合是ab, Ab, B,存在的sku组合是ab, aB, AB,所以因为Ab组合没有能知道,所以,A需要标注为不可点。组合sku判断的时候,需要注意的是,因为B和选中的b在同一个属性中,所以组合的时候,需要去掉b,然后组合成B,这是第3步所主要完成的过程。

这样的算法,很简单,但很繁琐,循环嵌套循环,可以简单分析一下算法复杂度。如果sku属性组合元素的总和数用m表示,结果数据长度为n,那么每次选择后,需要的算法大致步骤是m n。这似乎不是很复杂,m n而已,不过,每次判断一个sku组合是否和result中的组合匹配,却不是一个简单的过程,实际上,这可以看做是一个字符串匹配的一个算法了,最简单的还是使用正则匹配,m * n次正则匹配,这样就不怎么快了吧。正则表达式很不稳定,万一sku组合中有一些特殊字符,就可能导致一个正则匹配没能匹配到我们想要的表达式。

第一种算法的优化

经过讨论,第一种算法,有了优化的算法思路。 就第一种算法而言,正则匹配不够优雅,而且比较慢,而我们想要做的事情是比较一个组合是否包含于另外一个组合,用数学语言来描述,就是一个集合是否是另一个集合的子集,怎么来做这样的快速判断呢。

现在问题可以简化为:假设一个集合A{a, b, c}和另外一个集合B{a, e},如何快速判断B是否是A的子集。这个问题比较简单的方法是用B中所有元素依次和A中的元素进行比较,还是简单而粗暴的方式,比正则稍微快一些。对于集合中的元素,它们都以唯一的,通过这样的特性,我们可以把所有字母转换为一个质数,那么 集合A可以表示为集合元素(质数)的积,B同样, B是否是A的子集,这个只需要将B除以A,看看是否可以整除 ,如果可以那么说明,B是A的子集。

现在处理字符串就转换为处理乘法算法了,有了以上的分析,我们可以整理下算法过程:

  1. 数据预处理,生成一组随机数,把所有item一一对应一个质数,把item组合转换为一几个 质数的积
  2. 根据用户已经选择的item进行扫描所有的item,如果item已经被选中,则退出,如果没有, 则和所有已经选择的item进行相乘(特别注意,以选中的item需要去掉和当前匹配的item 在同一个类目中的item,因为一个组合不可能出现两个类目相同的item) ,这个乘机就是 上文中的集合B
  3. 把集合B依次和sku组合构成的积(相当于上文中的集合A)进行相除,比较,如果整除,则 退出,当前匹配的sku可以被选中,如果一直到最好还没有匹配上,则不能被整除。

这样优化了一下看起来比较简单的思路,但是实现起来却一点都不容易,代码在这里。算法也算简化了不少,不过这个预处理过程还是比较麻烦的,而且实际上,和第一种方案的解决的算法复杂度差不多,只是比较的时候使用的是乘除法,而第一种是正则匹配罢了。

第二种算法

后来又过了一周,这个问题被当成一个方案来继续讨论了。大家此时差不多都无话可说了,算法都有实现了,似乎没有什么其他可说的了。就在这个问题就如此结束的时候,正豪站出来了,说不管是第一种还是第一种方案的优化方案,每次用户进行选择,都需要重复计算一遍,这样实在太麻烦了。每次都对所有spu进行扫描,这样不是很好,能不能有其他的方式呢,能否更加直接判断出一个sku是否可以被选择呢。前面的算法,一个sku是否可以被选择,需要依次循环sku 组合的所有元素才可以判断的,这样的过程一定需要吗?

第三种算法就这样诞生了,考虑到JavaScript中的对象属性访问是最快的了,那么对于如果能够直接从一个对象中读取到以选择的sku和需要匹配的sku组合对应的数目,那这样的算法简直就是不用时间啊。下面来详细描述。

下面把问题初始条件假设如下:

初始状态,选中A1
属性1:
属性2:
属性3:

假如已经选中item为A1,那么现在要计算B1是否可以被选择,那么如果我们能够直接获取到A1和B1组合的所有商品数目,那么就能知道B1是否可以被选择了。A1和B1的组合是这样计算的,在上面描述的问题空间中,A1和B1的组合,可能有以下几种: A1+B1+C1, A1+B1+C2,A1+B1+C3。这些组合就可以直接从已知的sku组合中获取信息啦,同样是对象属性查找,快得不得了。示例如下:

A1选中状态下,判断B1是否可用,只需要查找A1 B1 = + +
A1+B1+C1这样的组合,结果可以可以直接从result中获得数据结果。

实际上, 对于任何一个sku和其他sku的组合都是可以通过同样的方式递归查找来实现获取其组合后的商品数目。这样的算法最大的优势是,计算过程是可以缓存的,比如计算A1是否可以被选中,那么肯定需要计算除A1+B1组合的数目,A1的数目是由A1+B1,A1+B2,A1+B3三个子集构成,这三个子集又可以拆分为更细的组合,然后这些所有的组合对应的商品数目都可以获取到了,下次需要判断A1+B2组合,则无需重复计算了。此外,我们可以清晰的获取组合相关的信息,比如某个sku下面可以有的商品数目。

算法实现这里jsfiddle

复杂度分析

第二种算法思路非常有趣,使用动态规划法,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。而且,最终判断一个item是否可以被选择,直接从对象中查找,属于字典查找算法了,应该是很快。但是,乍一看,还是有些问题,递归查找,数据贮存在变量中,这些都是通过空间来换取时间的做法,递归会堆栈溢出吗?查找次数到底多少?

第一个种算法的复杂度还是很容易计算的,首先假设一个n n的矩阵构成sku属性,比如10x10表示,有10个属性,每个属性有10个元素。假设可选择的result长度是m,那么,第一种算法的复杂度大概是 n n * m,这样的算法还是很快的。只是,如果每一个步骤,都使用正则表达式匹配,根据上面的演示,确实会有一些些慢,不过正则表达式的是模糊匹配,可能不是那么稳定。不过除法方式判断需要生成足够的质数,当几个数的乘积太大的时候,可能导致计算机无法运算,所有,使用第1种算法的优化算法,也是有一定限制的。js里面,能够处理的最大数字大概是19位,这个范围内可以操作的范围还是比较大的,这个就不做推算了。此外,通用可以引入负数,这样就可以把质数的范围增大一倍,计算量也小一些,可以处理更大的输入规模了。

第二种算法复杂度,同样对于n * n的数据输入,从第一排算起,第一排第一个A1,组合为A1 + B1, A1 + B2 ...函数递归进入第二层,第二层从第一个B1开始,组合为A1 + B1+ C1, A1 + B1 + C2 ...进入第三层,以此类推,函数每增加一层,需要的计算量是上一层的n倍,总数是 n + n2 + n3 + ... + nn,这个数目是非常庞大了,算法复杂度用nn来描述了,如果是10x10的sku属性组合,初始化需要100亿次计算,有些吓人了,这还需要一个同样庞大的内存数组。

第二种算法的优化

经过上面的算法分析,似乎第二种算法是错误的,无法执行。不过,仔细想想,第二种方法第一初始化的时候算法复杂度非常高,几乎是浏览器无法承受的。但是,一旦数据初始化完成,后面的过程就非常简单了,同样对于n n规模的输入,每次用户选择,这个时候,需要进行的操作是把所有数据遍历一遍,然后直接查询是否存可以被选中。算法复杂度是n n。比起上面第一种算法的优化算法要快,现在主要的问题是,初始化如果使用自上而下,不断拆分问题,这样运算复杂度指数级增加,不过,算法本身是可行的,数据初始化过程,还是需要进一步优化。

第二种算法,把问题一层一层拆分,查找过程分解太过于琐碎,有很多的组合,是完全不可能存在的,算法非常浪费。如果,直接从获得的result数组中读取数据组合,只需要把result循环一遍,所有可能的组合就都可以计算出来了。举个例子,从最上面的2x2的result中,我们知道result对象

    ab: {amount: 10, price: 20}
    aB: {amount: 10, price: 30}
    AB: {amount: 10, price: 40}

计算过程,循环result

  1. 第一次分解ab,a = 10, ab = 10, b = 10
  2. 第二次分解aB, a = a + 10 = 20, aB = 10, B = 10
  3. 第三次分解AB, A = 10, AB = 10, B = B + 10 = 20

三次循环,得到一个新的数据结构var map = {a: 20, ab: 10, b: 10, aB: 10, AB: 10, A: 10, B: 10}通过这个对象,就可以判断任何情况了。比如,初始化的时候,需要查找a, b, c,d,直接查找map对象中是否存在a, b, c, d。如果选择了a,那么需要判断aB, ab,统一直接查找的方式。

经过这样的优化,初始化的时候计算量也不大,这样第二种算法的实现就可以很好的完成任务了。可能这个map对象,可能还是会有点大。

结论

总的来说,比较好的方式是第一种算法的优化(也就是除法判断)和第二种算法。各自有其特点,都有其特色之处,除法判断把 字符串匹配转换为数字运算 ,第二种算法使用 字典查找 。并且都能 快速准确 的计算出结果。

从算法速度来说,第一种算法复杂度是n n m,当然需要一个比较繁琐负责的质数对应转换过程,第二种算法复杂度是 n * n,其初始化过程比较复杂,最初的方式是nn,经过优化,可以提高到n!,n的阶乘。从理论上而言,nn或者n!都是不可用的算法了,就实际情况而言,sku组合大多在,6x6以下,第二种算法还是非常快的。

从算法本身而言,第二种算法想法非常奇妙,容易理解,实现代码优雅。只是初始化比较慢,在初始化可以接受的情况下,还是非常推荐的,比如淘宝线上的sku判断。此外,第二种算法获得的结果比起第一种更具有价值,第二种方式直接取得组合对应的数目,价格信息,而第一种只是判断是否可以组合,从实际应用角度而言,第二种方式还是剩下不少事的。

感觉只要善于去发现,还能能够找到一些有意思的解决问题思路的。