快资讯：用位运算为你的程序加速

最近在持续优化之前编写的 JSON解析库 xjson，主要是两个方面的优化。

第一个是支持将一个 JSONObject对象输出为 JSON字符串。

这点在上个版本中只是利用自带的 Print函数打印数据：

【资料图】

funcTestJson4(t*testing.T){str:=`{"people":{"name":{"first":"bob"}}}`first:=xjson.Get(str,"people.name.first")assert.Equal(t,first.String(),"bob")get:=xjson.Get(str,"people")fmt.Println(get.String())//assert.Equal(t,get.String(),`{"name":{"first":"bob"}}`)}

Output:

map[name:map[first:bob]]

本次优化之后便能直接输出 JSON 字符串了：

实现过程也很简单，只需要递归遍历 object 中的数据，然后拼接字符串即可，核心代码如下：

func(rResult)String()string{switchr.Token{caseString:returnfmt.Sprint(r.object)caseBool:returnfmt.Sprint(r.object)caseNumber:i,_:=strconv.Atoi(fmt.Sprint(r.object))returnfmt.Sprintf("%d",i)caseFloat:i,_:=strconv.ParseFloat(fmt.Sprint(r.object),64)returnfmt.Sprintf("%f",i)caseJSONObject:returnobject2JSONString(r.object)caseArrayObject:returnobject2JSONString(r.Array())default:return""}}

第二个优化主要是提高了性能，查询一个复杂 JSON 数据的时候性能提高了大约 ⏫16%.

#优化前BenchmarkDecode-129001366905ns/op42512B/op1446allocs/op#优化后BenchmarkDecode-1210474659766ns/op37749B/op1141allocs/op

这里截取了一些重点改动的部分：

在 JSON 解析过程中会有一个有限状态机状态迁移的过程，而迁移的时候可能会出现多个状态。

比如当前解析到的 token 值为 {，那它接下来的 token 可能会为 ObjectKey:"name",也可能会是 BeginObject:{,当然也可能会是 EndObject:}，所以在优化之前我是将状态全部存放在一个集合中的，在解析过程中如果发现状态不满足预期的列表时则会抛出语法异常的错误。

所以优化之前是遍历这个集合来进行判断的，这样的时间复杂度为 O(N),但当我们换成位运算就不一样了，时间复杂度直接就变为O(1)了，同时还节省了一个切片的存储空间。

我们简单来分析下这个位运算为什么会达到判断一个数据是否在一个集合中同样的效果。

首先以这两个状态为例：

StatusObjectKeystatus=0x0002StatusColonstatus=0x0004

他们分别对应的二进制数据为：

StatusObjectKeystatus=0x0002//0010StatusColonstatus=0x0004//0100

当我们对这两个数据求 |运算得到的数据是 0110：

A:0010B:0100C:0110

这时候如何我们如果用这两个原始数据与 C:0110做 &运算时就会还原为刚才的两个数据。

//input:A:0010C:0110//output:A:0010----------//input:B:0100C:0110//output:B:0100

但我们换一个 D 与 C 求 &时：

D:1000//0x0008对应的二进制为1000C:0110D":0000

将会得到一个 0 值，只要得出的数据大于 0 我们就能判断一个数据是否在给定的集合中了。

当然这里有一个前提条件就是，我们输入的数据高位永远都是是 1 才行，也就是2的幂。

同样的优化在解析查询语法时也有使用：

当然位运算还有一些其他技巧，比如判断奇偶数：

//偶数a&1==0//奇数a&1==1

乘法和除法，右移1一位是除以2，左移一位是乘以2.

x:=2fmt.Println(x>>1)//1fmt.Println(x<<1)//4

位运算在带来程序性能提升的同时也降低代码可读性，所以我们得按需选择是否使用；

再一些底层库、框架代码对性能有极致追求的场景推荐使用，但在业务代码中对数据做加减乘除就没必要用位运算了，只会让后续的维护者一脸懵逼。

相关代码：https://github.com/crossoverJie/xjson

往期推荐

JetBrains IDE 中的隐藏宝石技巧

XJSON 是如何实现四则运算的？

用面向对象的方式操作 JSON 甚至还能做四则运算 JSON 库

几百行代码实现一个 JSON 解析器

几百行代码实现一个脚本解释器

点分享

点点赞

点在看

关键词： 时间复杂度 四则运算 前提条件