乐趣区

关于go:用位运算为你的程序加速

前言

最近在继续优化之前编写的 JSON 解析库 xjson,次要是两个方面的优化。

第一个是反对将一个 JSONObject 对象输入为 JSON 字符串。

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

func TestJson4(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]]

<!–more–>

本次优化之后便能间接输入 JSON 字符串了:

实现过程也很简略,只须要递归遍历 object 中的数据,而后拼接字符串即可,外围代码如下:

func (r Result) String() string {
    switch r.Token {
    case String:
        return fmt.Sprint(r.object)
    case Bool:
        return fmt.Sprint(r.object)
    case Number:
        i, _ := strconv.Atoi(fmt.Sprint(r.object))
        return fmt.Sprintf("%d", i)
    case Float:
        i, _ := strconv.ParseFloat(fmt.Sprint(r.object), 64)
        return fmt.Sprintf("%f", i)
    case JSONObject:
        return object2JSONString(r.object)
    case ArrayObject:
        return object2JSONString(r.Array())
    default:
        return ""
    }
}

用位运算优化

第二个优化次要是进步了性能,查问一个简单 JSON 数据的时候性能进步了大概 ⏫16%.

# 优化前
BenchmarkDecode-12         90013             66905 ns/op           42512 B/op       1446 allocs/op

# 优化后
BenchmarkDecode-12        104746             59766 ns/op           37749 B/op       1141 allocs/op

这里截取了一些重点改变的局部:

在 JSON 解析过程中会有一个无限状态机状态迁徙的过程,而迁徙的时候可能会呈现多个状态。

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

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

咱们简略来剖析下这个位运算为什么会达到判断一个数据是否在一个汇合中同样的成果。

首先以这两个状态为例:

    StatusObjectKey   status = 0x0002
    StatusColon       status = 0x0004

他们别离对应的二进制数据为:

    StatusObjectKey   status = 0x0002 //0010
    StatusColon       status = 0x0004 //0100

当咱们对这两个数据求 | 运算失去的数据是 0110

A:0010
B:0100

C:0110

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

// input:
A:0010
C:0110

// output:
A:0010

----------
// input:
B:0100
C:0110

// output:
B:0100

但咱们换一个 D 与 C 求 & 时:

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

将会失去一个 0 值,只有得出的数据大于 0 咱们就能判断一个数据是否在给定的汇合中了。

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

同样的优化在解析查问语法时也有应用:

其余奇淫巧技

当然位运算还有一些其余技巧,比方判断奇偶数:

// 偶数
a & 1 == 0

// 奇数
a & 1 == 1

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

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

总结

位运算在带来程序性能晋升的同时也升高代码可读性,所以咱们得按需抉择是否应用;

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

相干代码:https://github.com/crossoverJie/xjson

退出移动版