微信号:QunarTL

介绍:Qunar技术沙龙是去哪儿网工程师小伙伴以及业界小伙伴们的学习交流平台.我们会分享Qunar和业界最前沿的热门技术趋势和话题;为中高端技术同学提供一个自由的技术交流和学习分享平台.

第四届 Hackathon 大赛 CodeCode 小组 JSON

2018-09-27 08:00 周磊

周磊


个人介绍:周磊,2014年加入去哪儿网技术团队。目前在火车票事业部/国际火车票,参与开发了国际火车票交易、国际火车票供应等项目。个人对票务供应链、行程基础数据提供(线路规划、联程算法、出行方案制定)等有浓厚兴趣,有志寻找智能出行的实现方法。


编程马拉松(英语:Hackathon,又译为黑客松),又称黑客日(Hack day)、黑客节(Hackfest)或编程节(Codefest),是一个流传于黑客(hacker)当中的新词汇。Qunar Hackathon 大赛, 是一年一度程序技术大赛,与携程跨公司参与,其中大赛包含创建大赛信息、提供题目、报名组队、评委评审等环节,每个环节都需要统筹各类信息及把控时间安排。出题人根据公司实际业务找到问题,以鼓励参赛选手解决实际问题为目的,最终项目落地促进公司业务线发展。第四届 Qunar Hackathon 是一个 24 小时的编程项目,选手需要在规定的时间内,完成大赛题目的要求。Qunar Hackathon 的口号是:Solve the real,change the world!

本次大赛中,我所在的队伍是CodeCode队,我们小组积极备赛,最终通过共同的努力获得了大赛二等奖!比赛结束已经1个多月,我们小组对本次大赛中的项目做了一个总结,希望大家一起参考学习。

在 19 道题目中,我们结合自身掌握的知识范畴,选择了一个有具体实施方案的题目:自动化接口 Diff 工具。

题目方向:

自动化接口 Diff 工具

项目题目:

很多业务场景修改之后需要进行回归测试,回归测试最常用的方法就是新接口结果与线上结果进行对比(复杂 JSON 数据),但是回归需要许多 case,比如机票需要验单程、往返、不同出发到达地点日期等不同条件,因此想要通用性较强的工具,工具要求能够对比不同类型的返回结果,能够选择性的忽略某些节点,忽略下面的节点不参与对比,能够并发的执行多调测试用例,以减少等待时间。

输入: 接口返回对象样例(序列化的 JSON 串),支持复杂的 list\map 嵌套, 返回量可能较大,大的会有 1M

输入: 接口对比地址

输入: 测试不同 case 的条件(一次可以支持多个条件进行测试)

输入: 忽略节点(例如每次请求的 queryId 不一致,但其他一致,这个节点不作为对比点)

输出:对比接口结果不一致的节点(JSON 串不考虑顺序的影响,顺序不同但是内容一致算一致)

期待结果:

期待能够显示出两个链接中不同的 JSON 节点与不同的内容

产出物:

提供方案和代码

提供数据/信息

评审标准:

  1. 对比结果的准确性

  2. 响应时间

一、如何组建团队

确定题目之后,需要详细分析题目及洞悉需求方的需求。如上面这个题目,通过题目内容的分析,可以从下面几个方面考虑:首先,应当提供的是工具类。从易用性方面考虑,提供出来的应该是一个简单易用的 jar 包,由此决定了项目的结构。然后,根据可输入请求条件可以是接口对比地址,及需要支持并发,则在设计上应当有 web 的请求会更容易做到。最后,关于结果的输出,除去 jar 包中的实现和结果数据输出,另外一部分就是怎样最直观的的显示,则需要一个前端开发人员。

因此,先确定了团队成员:队长,负责设计和整体规划;2 名开发(负责核心算法实现);一名前端(效果展示)。

队伍名称:CodeCode

队伍名称来历:题目是 JSON Diff,意思是左侧的 JSON 数据和右侧的 JSON 数据做对比。 所以命名为 CodeCode,既表示左侧 Code 和右侧 Code 的 JSON 数据对比,也寓意着能够通过编码的方式解决实际问题。

二、如何设计

队伍已经确认了,那么为了达成目标,又该如何设计?

2.1 项目如何设计

项目结构上,需要提供 jar 和 web 工程。所以此处设计为父子工程。如下图

其中 jsondiff-util 为 jar 包: 主要的业务逻辑实现。

jsondiff-web 为 war 工程: 主要负责页面展示和请求接入,直观的表现 jar 中的功能。

2.2 功能模块如何划分

一般是按照职责划分,如:

前端显示,则均为 FE 负责。

接口定义,全员参与确定。主要为前后端交互人员确定,并输出确定的接口文档。其中,优先定义好接口,接口是解耦前后端开发的关键,以及对需求理解程度的体现。全员参与确定接口,有助于所有人在此环节,将所有问题抛出,最终达成一致的目标。

基于目标的具体实现,其中后端开发人员应当负责重点和难点问题突破,并优先解决难点问题。

三、如何确定和实现难点问题

优先分析实现过程中的难点问题。因为难点问题不解决,相当于整体就有断层,那就会造成项目失败,或者整体考虑不全等问题,造成后续返工修改,消耗成本会更大。那么项目实施过程中,要如何找到难点问题?

以此题目举例,首先分析 JSON 的特性:

1、JSON 对象是一个无序的“‘名称/值’对”集合。一个对象以“{”(左括号)开始,“}”(右括号)结束。每个“名称”后跟一个“:”(冒号);“‘名称/值’ 对”之间使用“,”(逗号)分隔。 2、数组是值(value)的有序集合。一个数组以“[”(左中括号)开始,“]”(右中括号)结束。值之间使用“,”(逗号)分隔。 3、值(value)可以是双引号括起来的字符串(string)、数值(number)、true、false、 null、对象(object)或者数组(array),这些结构可以嵌套。 4、字符串(string)是由双引号包围的任意数量 Unicode 字符的集合,使用反斜线转义。一个字符(character)即一个单独的字符串(character string)。

总结一下 JSON 的数据结构即为:

null:表示为 null boolean:表示为 true 或 false number:一般的浮点数表示方式 string:表示为 "..." array:表示为 [ ... ] object:表示为 { ... }

基于以上 JSON 特性,需要比较属性差异,则对于基础数据类型(null/boolean/number/string)使用 equals 即可比较出是否相同,而 object 和 array 如何比较是否相同,分析如下:

object 结构中的属性因 JSON 的输出是无序的,所以比较时需要对属性的无序性进行处理,如先进行排序后,再比较基础属性。那么对于 object 的属性中嵌套 object 的结构(如{"a":{"b":"b1"},"c":"c1"} 和 {"c":"c1","a":{"b":"b1"}}),如何比较是否相同,此处先带着此问题,看下文分析。

array 结构本身有序,其中的数据可以是基础数据类型,也可以是 object 以及 array 类型。如果 array 中是 object 的类型,怎样比较每个 object 类型的差异,又需要如何比较 array 间的差异?还有一种情况是在实际应用过程中,需要忽略 array 的有序性(如航班列表,可能并不在乎顺序,而只关注增删的航班),那么问题就来了,array 也变成无序的了,那这时候 array 中的每个 object 又如何比较呢?还有的问题是顺序比较也可能增减。比如 [a,b,c] 变为[a,x,b,c],应该找出新增了 x,而不是 b 和 x 比,c 和 b 比的一对一顺序比较。可以说解决后面的乱序问题后,也就能解决有序的增减问题,所以重点是解决乱序。

在比较前,有那么多的问题存在,为了基于统一的一种结构进行分析,则应当对 JSON 有预处理。从扩展性方面,可能会增加各种各样的需求;从易用性方面,应当有一种结构,可以基于此结构,做很多的切面层等;从可行性方面,也应当有一种结构,可以涵盖最基础的情况,然后再开始分析和落实。suoy 快速的定位和取出需要的 JSON 结构中的信息等等情况,应当有一种结构,可以建立最基础的结构予以支持。比如把输入的 JSON 转换成可以解析的语法分析树,这个思想其实可以借鉴 java 编译的过程,创建语法分析树,是后续链接、速度优化、倒排序等等,提供了基础。那么我们就遇到了第一个难点问题。

难点一:需要创建一个什么样的语法分析树?

方案一:创建两个大 Map<String, Object>  比较。那么问题来了:这个 map 的 key(类型为 string) 需要如何设计呢?因为 JSON 的 key其实是可以是任意字符的,只要是被双引号包着,如 "","\"","\\"" 都是可能的。上面给的这个双引号是否可以当做从 root 开始到叶子节点的路径区分符呢?因为如果双引号出现在 key 中,那么 key 中一定跟着转义字符。那是否可以使用前先把转义字符替换成别的字符如统一为下划线,或者干脆替换成双引号呢?因为 """ 为 JSON 的 key 是不合法的,必存在转义字符为 "\"" 的形式来表示。可是遇到 "\\"" 和父节点为 "\" 子节点为 "\"" 或者这样的结构 {"":{"":{"\"":"abc"}}} 和 {"":{"\"":{"":"abc"}}}, 如果把【\"】再替换成【"】, 是不是又认为是相同的节点了呢?其实这之间,我们忽略了节点的层级结构试图使用一个分隔符去代替,而 JSON 中 key 可以是任意字符,那么这种组合就可能是错误的。所以此方案存在缺陷,不可行。

方案二:使用 Map<List<String>, Object>。这样就屏蔽了一定要使用一个分隔符的问题。但是问题又来了,对于 array 结构,key 是相同的,该如何解决?如果对于 array 的情况,使用相同的 List<String>  的 key,然后把 array 的子节点都放到 value 里,那么 value 又该如何设计?或者简单的对每个 array 中的 object 加个下标值来区分 key,而对于要忽略 array 顺序的情况需求,如对于左侧数组中的第一个元素和右侧数组中的第二个元素开始可能是一样的(第二个数组中增加了第一个元素,而其他都一样),却因为 key 增加了下标,结果就不一样了,这种加下标值方案看来是行不通的。使用 Map<List<String>, Object> 这种结构几乎完全的丢失了原始 JSON 的层次结构(调用者期望和输入时结构一致的需求)。这时候如果在 key 中增加个父节点的引用,value 增加子节点的 List 或 Map<List<String>, Object> 可以么?但是在遇到下文中要解决的难点二问题时,使用起来较为麻烦,所以此方案也暂时不考虑。

难点二:array 的对象无序又不完全一致时,如何快速确定 array 中的两个对象相同或找出最相似呢?

如下面两个 JSON, 其中左侧的 JSON:

 
           
  1. {

  2. "users": [{

  3. "name": "alice",

  4. "age": 38,

  5. "number": 76

  6. },

  7. {

  8. "name": "bob",

  9. "age": 45,

  10. "number": 91

  11. },

  12. {

  13. "name": "eve",

  14. "age": 6,

  15. "number": 33

  16. }]

  17. }

右侧的 JSON:

 
           
  1. {

  2. "users": [{

  3. "name": "alice",

  4. "age": 38,

  5. "number": 76

  6. },

  7. {

  8. "name": "eve",

  9. "age": 6,

  10. "number": 33

  11. },

  12. {

  13. "name": "bob",

  14. "age": 47,

  15. "number": 91

  16. }]

  17. }

以上期望是:忽略数组有序性,需要确定左侧第二个元素的 bob 对象和右侧的第三个元素对象 bob 相似,并比较其中的 age 属性,从 45 岁更改到了 47 岁。

方案一:使用相同权值标记法。比较两个 object 中的属性如果相同则权值 +1,并累计 object 的属性相同次数,对比完所有的差异 object,找出其中权值总和相差最小的两个 object 为最相似,然后在找出次相似的对象,直到比较结束。这种方案的问题是如果是两个大的数组嵌套了 N*M 层的结构。从两个 array 中完全匹配相似度最高的两个对象,则最坏的可能性是要进行的比较次数为(N*M)的笛卡尔积(即 (N*M) (N*M) 次),才可以确定两个 array 中的一个 object 是否相似。即使把中间的结果都使用空间换时间的方式存储下来为了最后确认了顶层的 array 的 object 后,再确定次顶层的时候使用。这种递归的比较可想而知,当 N*M 很大时,是相当的慢。故此种方法在嵌套结构很深的时候是不可行的,但是适用于数量级很小的比较中,因为可以准确的匹配出差异数量,比如数量级小于 1000 次。

方案二:降维。 降维是解决多维问题到低纬问题的常用手段。在比较之前,是否可以将 N*M 的问题转化为 1*M 的问题?分析发现,object 对象中的属性是无序的,但可以通过构建一个 TreeMap 的结构使之有序,然后 toString 之后生成一个此 object 的代表值,这里称之为 objectKey。这样每个 object 都有了一个 objectKey 值,那么 array 是否也可以根据对象中的 objectKey 创建一个 TreeMap, 并且生成自己 arrayObjectKey 了呢?这样就将 array 的 object 的 N 种组合结构转化为一个属性值 arrayObjectKey 的结构了,即 N 纬度转变成了一个纬度。最后就可以快速的确认出顶层的 array 的对应关系,然后确认次顶层,次次顶层...且此种方法是在比较之前进行的单个 JSON 的数据的分析,时间复杂度低。这也是我们最终采用了此种方案原因之一。

基于上面的难点问题,我们给出了最终的方案:

方案三:输入 JSON 的字符串,解析成对应结构的语法分析树,并创建特征值,递归比较出最终结果集。具体实现步骤如下:

1、创建的语法分析树。根据 JSON 结构创建 Node 节点(node 的结构参考附件)。创建过程中即可将忽略的节点直接标记为忽略; 空值是否参与比较做预处理;当遇到 array 或 object 结构时,递归计算 objectKey 值。如下图:

2、创建语法树的同时,降纬,并标记特征值。

其中的 objectKey 生成了,但是我们发现这个 objectKey 会随着 JSON 的层级加深,尤其是 array 的多级结构时(即 array 中的 object 中还有array),此 objectKey 会很大,每一层级几乎包含了整个 JSON 串, 极限情况下,就是一个完全的 array 嵌套结构时(如“{[[[a,b,c]]]}”),达到最差。这在空间复杂度上是一个很大的问题。如何解决这个问题呢? 使用 MD5 数字签名,可以很好的解决空间复杂度增长的问题,并为后续比较相同的 object 缩短了一定的时间,但是其中丢失了 key 和 value 合并的 objectKey 的键值特性。假如我们就直接使用 objectKey 的形式保存这种键值特性,然后下面的就是带来的难点问题三。

难点问题三:如何快速确定两个字符串相似度最高?

至于相似度计算,其实是可以抽离成模块,可替换为几种不同的相似度。比如字符串的编辑距离,欧式距离,余弦相似度等。

参考了以上的一些算法,但从 JSON Diff 的乐观角度来看,是属性和值都尽可能的一致,考虑到匹配速度等因素,这里使用了一种很简洁的实现方式,我们称之为字符统计数特征值。如果比较两个字符串差异度,可以快速的桶化计数。也就是将字符串按照 byte 值散列到256(2 的 8 次方)个数组中,并记录每个 byte 出现的次数。使用两个数组差异最小值来计算相似度。

相似度 = 求和 256 个元素的(Math.min(a,b) - Math.abs(a-b))

如字符串:"aaabacb"  和 "aaababc" 其中 a/b/c 的个数相同,权值很接近。但是此种丢失了顺序结构,上面的这个例子就是认为是相同的。但是上面这种结果显然是不对的,如何解决呢? 我们这边采用的是找到相似后(可能有多个相似度很高的对象),然后再反向建树,即再反向回归到 JSON 的结构,刨出错误的匹配。以及在是否使用字符桶计数的方法前,根据数量级做不同方案的决策。如比较的数量级小于 1000 次,则使用权重相同标记法精确匹配确认结果。

把 key 和 value 创建完 TreeMap 的结构后,使用 key+value 一起(即 TreeMap 的 toString)创建特征值,还是 key 和 value 分别创建特征值属性好呢?

因 JSON Diff 的过程中只有 key 相同了,再去匹配 value 才更有意义。比如 key+value 的形式,可能连起来匹配的相似度很高,但是对于 JSON 来说,key 都不相同,比较 value 是没有意义的,如 {"a":{"b":"c"}} 和 {"a":{"":"bc"}}。所以此处我们采用 key 和 value 分开建立权重值,总体计算权重的时候,我们让 key 的权重系数更高,这样由于 key 都不相同的情况下,差异性会因为给的系数而呈现出较大的差异性。并且可以灵活调整权重系数。目前 key 的计算权重系数为 30,value 为 1。但是这里面的 key 的权重值也不建议设置的太大,因为太大,可能由于两个 JSON 实际上是差不多的,比如一个 JSON 使用的是带 null 值的输出方式,另一个采用的是 value 为 null 值时 key 和 value 均不输出方式,实际上,是否是 null 对于很多的业务场景,影响并不大(对于 null 有特殊意义的除外)。

3、比对算法,数组无序匹配的快速剪枝。

其中,一定是要已经去除了完全匹配的节点,这样可以快速的剪枝(就是减少数据基数)。因为 JSON Diff,通常情况下还是大部分的内容相同,少部分内容是不同的。

针对上面的比对算法,具体的匹配算法流程可参见用例图解如下:

第一步,基于每个 JSON 数据,创建语法树的同时,构建 key 及 value 的特征值。

第二步,比较两个 JSONObject 差异对象的相似度的值

第三步,比较完所有对应层级下的 JSONArray 的差异,生成了差异表。

第四步,使用动态规划的思想,找出差异度最小的两个 JSONObjcet。

第五步,输出结果。

四、总结

4.1 比对算法:效率

时间复杂度

构建语法树:O(n), n 为 JSON 节点总数

比对:O(n),对于全等节点

比对:O(n ^ 2 * m),无序数组,n、m 为数组长度

输出:O(n), n 为 JSON 节点总数

空间复杂度

构建语法树:O(k),k 为 JSON 的最深层级

可使用 MD5 HASH 精简特征值,牺牲少许速度

比对及输出:O(1),与输入数据量相似

4.2 准确性 VS 效率

时间性能——

构建语法树:约 0.5 ~ 1 秒

比对:通常约 100 毫秒

输出:< 100ms

单次完整响应时间:约 2 秒,70% 为网络通讯时间

准确性——

优先去除完全相同对象(剪枝)

从下向上构建特征值,获取最相似的数组元素

若数组元素数量很少,可完全循环对比

4.3 常用思考方法总结

降维的思想。将问题去除一个维度,如从三维空间转换为二维空间或者更低的空间。可以使得复杂度降低,但是应当保留一些特性。

剪枝的思想。计算过程中,如果问题成指数或者增长很快,可以考虑在计算过程中加入剪枝的思想,即把最初的计算规模减低(可能失去一些准确性),但是整体上是可以保持快速计算的需求。

动态规划。把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。

附录

Node 的设计:

 
           
  1. public class Node implements Serializable {

  2.    /**

  3.     * 该节点的Key,若节点为Array中的一个元素,则key为null。

  4.     */

  5.    private String key;

  6.    /**

  7.     * 节点的值。可以为String, Number, Boolean, null, <Array> 或 <Map>

  8.     */

  9.    private Object value;

  10.    /**

  11.     * 该元素所有子节点的有序组合。

  12.     * 若两个元素的objectKey相等,则它们必然相等。

  13.     */

  14.    private String objectKey;

  15.    /**

  16.     * 为arrayObjectKey的特征值。

  17.     * 将该key按字节读取,记录每种‘字节码’(共256种)出现的次数。

  18.     * 若两个元素的arrayWeight相近,则它们相近。

  19.     * 在比较某层元素时,其key拥有更大权重(因为只有key相同,value才具备价值)。

  20.     */

  21.    private int[] arrayKeyWeight;

  22.    /**

  23.     * 为arrayObjectValue的特征值。

  24.     * 将该value按字节读取,记录每种‘字节码’(共256种)出现的次数。

  25.     * 若两个元素的arrayValueWeight相近,则它们相近。

  26.     * 在比较某层元素时,其key拥有更大权重(因为只有key相同,value才具备价值)。

  27.     */

  28.    private int[] arrayValueWeight;

  29.    /**

  30.     * 相对于根节点的节点深度

  31.     */

  32.    private int depth;

  33.    /**

  34.     * 代表从其value开始计,包含的所有数组的路径总和(即数组的叶子节点之和)。

  35.     * 例如,若value为[2,3,4],则quantity为3;若value为[[2,3],[4,5],[{"key":6}]],quantity为5。

  36.     * 原始JSON和对比JSON的此数值相乘,以计算在某个层级进行数组对比时,预计的对比次数。

  37.     * 默认为0,代表value下面不含数组。

  38.     */

  39.    private int arrayQuantity = 0;

  40.    /**

  41.     * 节点的值类型

  42.     */

  43.    private NodeEnum valueType;

  44.    public String getKey() {

  45.        return key;

  46.    }

  47.    public Node setKey(String key) {

  48.        this.key = key;

  49.        return this;

  50.    }

  51.    public Object getValue() {

  52.        return value;

  53.    }

  54.    public Node setValue(Object value) {

  55.        this.value = value;

  56.        return this;

  57.    }

  58.    public String getObjectKey() {

  59.        return objectKey;

  60.    }

  61.    public Node setObjectKey(String objectKey) {

  62.        this.objectKey = objectKey;

  63.        return this;

  64.    }

  65.    public int[] getArrayKeyWeight() {

  66.        return arrayKeyWeight;

  67.    }

  68.    public Node setArrayKeyWeight(int[] arrayKeyWeight) {

  69.        this.arrayKeyWeight = arrayKeyWeight;

  70.        return this;

  71.    }

  72.    public int[] getArrayValueWeight() {

  73.        return arrayValueWeight;

  74.    }

  75.    public Node setArrayValueWeight(int[] arrayValueWeight) {

  76.        this.arrayValueWeight = arrayValueWeight;

  77.        return this;

  78.    }

  79.    public int getDepth() {

  80.        return depth;

  81.    }

  82.    public Node setDepth(int depth) {

  83.        this.depth = depth;

  84.        return this;

  85.    }

  86.    public NodeEnum getValueType() {

  87.        return valueType;

  88.    }

  89.    public Node setValueType(NodeEnum valueType) {

  90.        this.valueType = valueType;

  91.        return this;

  92.    }

  93.    public int getArrayQuantity() {

  94.        return arrayQuantity;

  95.    }

  96.    public Node setArrayQuantity(int arrayQuantity) {

  97.        this.arrayQuantity = arrayQuantity;

  98.        return this;

  99.    }

  100.    public Node addArrayQuantity(int arrayQuantity) {

  101.        this.arrayQuantity += arrayQuantity;

  102.        return this;

  103.    }

  104.    @Override public String toString() {

  105.        final StringBuilder sb = new StringBuilder("Node{");

  106.        sb.append("key='").append(key).append('\'');

  107.        sb.append(", value=").append(value);

  108.        sb.append('}');

  109.        return sb.toString();

  110.    }

  111. }


团队合影(注:有小伙伴远程支持,未出现在图片中)

参考文献

编辑距离: https://blog.csdn.net/ac540101928/article/details/52786435 http://en.wikipedia.org/wiki/Editdistance http://en.wikipedia.org/wiki/Levenshteindistance 相似度算法: https://blog.csdn.net/hgzlhgzlhgzl/article/details/68925980 余弦相似度: https://blog.csdn.net/u012160689/article/details/15341303 几种高效的字符串匹配算法: https://blog.csdn.net/lianhuijuan/article/details/61617018

 
Qunar技术沙龙 更多文章 java 泛型解析 从人肉到智能,阿里运维体系经历了哪些变迁? 机器学习之 scikit-learn 开发入门(2) 机器学习之 scikit-learn 开发入门(1) 去哪儿2018-3期技术应届生培训圆满结束
猜您喜欢 .NET Core中的性能测试工具BenchmarkDotnet 【原题】每个架构师都应该研究下康威定律 物联网网络编程、Web编程综述 尽快遇见最棒的自己,就得每周读一本书 Android开发技术周报 Issue#0