什么是变量的深拷贝和浅拷贝?

zkbhj 发表了文章 • 0 个评论 • 152 次浏览 • 2020-07-24 10:41 • 来自相关话题

通用深拷贝和浅拷贝的区别
 

深拷贝和浅拷贝最根本的区别在于是否真正获取一个对象的复制实体,而不是引用。

 假设B复制了A,修改A的时候,看B是否发生变化:

如果B跟着也变了,说明是浅拷贝,拿人手短!(修改堆内存中的同一个值)
如果B没有改变,说明是深拷贝,自食其力!(修改堆内存中的不同的值)

 浅拷贝(shallowCopy)只是增加了一个指针指向已存在的内存地址,
深拷贝(deepCopy)是增加了一个指针并且申请了一个新的内存,使这个增加的指针指向这个新的内存,
使用深拷贝的情况下,释放内存的时候不会因为出现浅拷贝时释放同一个内存的错误。
 
Go语言中的深浅拷贝
 
1、深拷贝(Deep Copy):

拷贝的是数据本身,创造一个样的新对象,新创建的对象与原对象不共享内存,新创建的对象在内存中开辟一个新的内存地址,新对象值修改时不会影响原对象值。既然内存地址不同,释放内存地址时,可分别释放。

值类型的数据,默认全部都是深复制,Array、Int、String、Struct、Float,Bool。

2、浅拷贝(Shallow Copy):

拷贝的是数据地址,只复制指向的对象的指针,此时新对象和老对象指向的内存地址是一样的,新对象值修改时老对象也会变化。释放内存地址时,同时释放内存地址。

引用类型的数据,默认全部都是浅复制,Slice,Map。
 
深拷贝示例:
package main

import (
"fmt"
)

// 定义一个Robot结构体
type Robot struct {
Name string
Color string
Model string
}

func main() {
fmt.Println("深拷贝 内容一样,改变其中一个对象的值时,另一个不会变化。")
robot1 := Robot{
Name: "小白-X型-V1.0",
Color: "白色",
Model: "小型",
}
robot2 := robot1
fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, &robot2)

fmt.Println("修改Robot1的Name属性值")
robot1.Name = "小白-X型-V1.1"

fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, &robot2)

}深拷贝 内容一样,改变其中一个对象的值时,另一个不会变化。
Robot 1:{小白-X型-V1.0 白色 小型} 内存地址:0xc000072330
Robot 2:{小白-X型-V1.0 白色 小型} 内存地址:0xc000072360
修改Robot1的Name属性值
Robot 1:{小白-X型-V1.1 白色 小型} 内存地址:0xc000072330
Robot 2:{小白-X型-V1.0 白色 小型} 内存地址:0xc000072360浅拷贝示例2:
package main

import (
"fmt"
)

// 定义一个Robot结构体
type Robot struct {
Name string
Color string
Model string
}

func main() {

fmt.Println("浅拷贝 使用new方式")
//new方式返回的是一个指针,是引用类型,所以会触发浅拷贝
robot1 := new(Robot)
robot1.Name = "小白-X型-V1.0"
robot1.Color = "白色"
robot1.Model = "小型"

robot2 := robot1
fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)

fmt.Println("在这里面修改Robot1的Name和Color属性")
robot1.Name = "小蓝-X型-V1.2"
robot1.Color = "蓝色"

fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)
}浅拷贝 使用new方式
Robot 1:&{小白-X型-V1.0 白色 小型} 内存地址:0xc000068330
Robot 2:&{小白-X型-V1.0 白色 小型} 内存地址:0xc000068330
在这里面修改Robot1的Name和Color属性
Robot 1:&{小黑-X型-V1.2 黑色 小型} 内存地址:0xc000068330
Robot 2:&{小黑-X型-V1.2 黑色 小型} 内存地址:0xc000068330另外一种浅拷贝方式:&取指针赋值
package main

import (
"fmt"
)

// 定义一个Robot结构体
type Robot struct {
Name string
Color string
Model string
}

func main() {

fmt.Println("浅拷贝 内容和内存地址一样,改变其中一个对象的值时,另一个同时变化。")
robot1 := Robot{
Name: "小白-X型-V1.0",
Color: "白色",
Model: "小型",
}
robot2 := &robot1
fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)

fmt.Println("在这里面修改Robot1的Name和Color属性")
robot1.Name = "小黑-X型-V1.1"
robot1.Color = "黑色"

fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)

}
参考文档:
https://www.cnblogs.com/mikeCao/p/8710837.html
https://www.cnblogs.com/guichenglin/p/12736203.html
  查看全部
通用深拷贝和浅拷贝的区别
 


深拷贝和浅拷贝最根本的区别在于是否真正获取一个对象的复制实体,而不是引用


 假设B复制了A,修改A的时候,看B是否发生变化:


如果B跟着也变了,说明是浅拷贝,拿人手短!(修改堆内存中的同一个值)
如果B没有改变,说明是深拷贝,自食其力!(修改堆内存中的不同的值)


 浅拷贝(shallowCopy)只是增加了一个指针指向已存在的内存地址,
深拷贝(deepCopy)是增加了一个指针并且申请了一个新的内存,使这个增加的指针指向这个新的内存,
使用深拷贝的情况下,释放内存的时候不会因为出现浅拷贝时释放同一个内存的错误。
 
Go语言中的深浅拷贝
 
1、深拷贝(Deep Copy):

拷贝的是数据本身,创造一个样的新对象,新创建的对象与原对象不共享内存,新创建的对象在内存中开辟一个新的内存地址,新对象值修改时不会影响原对象值。既然内存地址不同,释放内存地址时,可分别释放。

值类型的数据,默认全部都是深复制,Array、Int、String、Struct、Float,Bool。

2、浅拷贝(Shallow Copy):

拷贝的是数据地址,只复制指向的对象的指针,此时新对象和老对象指向的内存地址是一样的,新对象值修改时老对象也会变化。释放内存地址时,同时释放内存地址。

引用类型的数据,默认全部都是浅复制,Slice,Map。
 
深拷贝示例:
package main

import (
"fmt"
)

// 定义一个Robot结构体
type Robot struct {
Name string
Color string
Model string
}

func main() {
fmt.Println("深拷贝 内容一样,改变其中一个对象的值时,另一个不会变化。")
robot1 := Robot{
Name: "小白-X型-V1.0",
Color: "白色",
Model: "小型",
}
robot2 := robot1
fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, &robot2)

fmt.Println("修改Robot1的Name属性值")
robot1.Name = "小白-X型-V1.1"

fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, &robot2)

}
深拷贝 内容一样,改变其中一个对象的值时,另一个不会变化。
Robot 1:{小白-X型-V1.0 白色 小型} 内存地址:0xc000072330
Robot 2:{小白-X型-V1.0 白色 小型} 内存地址:0xc000072360
修改Robot1的Name属性值
Robot 1:{小白-X型-V1.1 白色 小型} 内存地址:0xc000072330
Robot 2:{小白-X型-V1.0 白色 小型} 内存地址:0xc000072360
浅拷贝示例2:
package main

import (
"fmt"
)

// 定义一个Robot结构体
type Robot struct {
Name string
Color string
Model string
}

func main() {

fmt.Println("浅拷贝 使用new方式")
//new方式返回的是一个指针,是引用类型,所以会触发浅拷贝
robot1 := new(Robot)
robot1.Name = "小白-X型-V1.0"
robot1.Color = "白色"
robot1.Model = "小型"

robot2 := robot1
fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)

fmt.Println("在这里面修改Robot1的Name和Color属性")
robot1.Name = "小蓝-X型-V1.2"
robot1.Color = "蓝色"

fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)
}
浅拷贝 使用new方式
Robot 1:&{小白-X型-V1.0 白色 小型} 内存地址:0xc000068330
Robot 2:&{小白-X型-V1.0 白色 小型} 内存地址:0xc000068330
在这里面修改Robot1的Name和Color属性
Robot 1:&{小黑-X型-V1.2 黑色 小型} 内存地址:0xc000068330
Robot 2:&{小黑-X型-V1.2 黑色 小型} 内存地址:0xc000068330
另外一种浅拷贝方式:&取指针赋值
package main

import (
"fmt"
)

// 定义一个Robot结构体
type Robot struct {
Name string
Color string
Model string
}

func main() {

fmt.Println("浅拷贝 内容和内存地址一样,改变其中一个对象的值时,另一个同时变化。")
robot1 := Robot{
Name: "小白-X型-V1.0",
Color: "白色",
Model: "小型",
}
robot2 := &robot1
fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)

fmt.Println("在这里面修改Robot1的Name和Color属性")
robot1.Name = "小黑-X型-V1.1"
robot1.Color = "黑色"

fmt.Printf("Robot 1:%s\t内存地址:%p \n", robot1, &robot1)
fmt.Printf("Robot 2:%s\t内存地址:%p \n", robot2, robot2)

}

参考文档:
https://www.cnblogs.com/mikeCao/p/8710837.html
https://www.cnblogs.com/guichenglin/p/12736203.html
 

什么是RPC?

zkbhj 发表了文章 • 0 个评论 • 161 次浏览 • 2020-07-23 16:52 • 来自相关话题

1.1 基本概念
 
RPC(Remote Procedure Call)远程过程调用,简单的理解是一个节点请求另一个节点提供的服务本地过程调用:如果需要将本地student对象的age+1,可以实现一个addAge()方法,将student对象传入,对年龄进行更新之后返回即可,本地方法调用的函数体通过函数指针来指定。远程过程调用:上述操作的过程中,如果addAge()这个方法在服务端,执行函数的函数体在远程机器上,如何告诉机器需要调用这个方法呢?
 简单总结,RPC需要以下三个步骤来完成:

1、首先客户端需要告诉服务器,需要调用的函数,这里函数和进程ID存在一个映射,客户端远程调用时,需要查一下函数,找到对应的ID,然后执行函数的代码。
2、客户端需要把本地参数传给远程函数,本地调用的过程中,直接压栈即可,但是在远程调用过程中不再同一个内存里,无法直接传递函数的参数,因此需要客户端把参数转换成字节流,传给服务端,然后服务端将字节流转换成自身能读取的格式,是一个序列化和反序列化的过程。
3、数据准备好了之后,如何进行传输?网络传输层需要把调用的ID和序列化后的参数传给服务端,然后把计算好的结果序列化传给客户端,因此TCP层即可完成上述过程,gRPC中采用的是HTTP2协议。

总结一下上述过程:
// Client端
// Student student = Call(ServerAddr, addAge, student)
1. 将这个调用映射为Call ID。
2. 将Call ID,student(params)序列化,以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr,这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功,那么就将结果反序列化,并赋给student,年龄更新

// Server端
1. 在本地维护一个Call ID到函数指针的映射call_id_map,可以用Map<String, Method> callIdMap
2. 等待服务端请求
3. 得到一个请求后,将其数据包反序列化,得到Call ID
4. 通过在callIdMap中查找,得到相应的函数指针
5. 将student(params)反序列化后,在本地调用addAge()函数,得到结果
6. 将student结果序列化后通过网络返回给Client





在微服务的设计中,一个服务A如果访问另一个Module下的服务B,可以采用HTTP REST传输数据,并在两个服务之间进行序列化和反序列化操作,服务B把执行结果返回过来。






由于HTTP在应用层中完成,整个通信的代价较高,远程过程调用中直接基于TCP进行远程调用,数据传输在传输层TCP层完成,更适合对效率要求比较高的场景,RPC主要依赖于客户端和服务端之间建立Socket链接进行,底层实现比REST更复杂。

1.2 rpc demo










 
完整源码:https://github.com/guangxush/wheel/tree/master/RPC/src
 
2. gRPC的使用

2.1. gRPC与REST 
REST通常以业务为导向,将业务对象上执行的操作映射到HTTP动词,格式非常简单,可以使用浏览器进行扩展和传输,通过JSON数据完成客户端和服务端之间的消息通信,直接支持请求/响应方式的通信。不需要中间的代理,简化了系统的架构,不同系统之间只需要对JSON进行解析和序列化即可完成数据的传递。但是REST也存在一些弊端,比如只支持请求/响应这种单一的通信方式,对象和字符串之间的序列化操作也会影响消息传递速度,客户端需要通过服务发现的方式,知道服务实例的位置,在单个请求获取多个资源时存在着挑战,而且有时候很难将所有的动作都映射到HTTP动词。正是因为REST面临一些问题,因此可以采用gRPC作为一种替代方案,gRPC 是一种基于二进制流的消息协议,可以采用基于Protocol Buffer的IDL定义grpc API,这是Google公司用于序列化结构化数据提供的一套语言中立的序列化机制,客户端和服务端使用HTTP/2以Protocol Buffer格式交换二进制消息。gRPC的优势是,设计复杂更新操作的API非常简单,具有高效紧凑的进程通信机制,在交换大量消息时效率高,远程过程调用和消息传递时可以采用双向的流式消息方式,同时客户端和服务端支持多种语言编写,互操作性强;不过gRPC的缺点是不方便与JavaScript集成,某些防火墙不支持该协议。注册中心:当项目中有很多服务时,可以把所有的服务在启动的时候注册到一个注册中心里面,用于维护服务和服务器之间的列表,当注册中心接收到客户端请求时,去找到该服务是否远程可以调用,如果可以调用需要提供服务地址返回给客户端,客户端根据返回的地址和端口,去调用远程服务端的方法,执行完成之后将结果返回给客户端。这样在服务端加新功能的时候,客户端不需要直接感知服务端的方法,服务端将更新之后的结果在注册中心注册即可,而且当修改了服务端某些方法的时候,或者服务降级服务多机部署想实现负载均衡的时候,我们只需要更新注册中心的服务群即可。






参考文档:
https://www.jianshu.com/p/7d6853140e13
https://www.jianshu.com/p/eb66b0c4113d
 
  查看全部
1.1 基本概念
 
  • RPC(Remote Procedure Call)远程过程调用,简单的理解是一个节点请求另一个节点提供的服务
  • 本地过程调用:如果需要将本地student对象的age+1,可以实现一个addAge()方法,将student对象传入,对年龄进行更新之后返回即可,本地方法调用的函数体通过函数指针来指定。
  • 远程过程调用:上述操作的过程中,如果addAge()这个方法在服务端,执行函数的函数体在远程机器上,如何告诉机器需要调用这个方法呢?

 简单总结,RPC需要以下三个步骤来完成:

1、首先客户端需要告诉服务器,需要调用的函数,这里函数和进程ID存在一个映射,客户端远程调用时,需要查一下函数,找到对应的ID,然后执行函数的代码。
2、客户端需要把本地参数传给远程函数,本地调用的过程中,直接压栈即可,但是在远程调用过程中不再同一个内存里,无法直接传递函数的参数,因此需要客户端把参数转换成字节流,传给服务端,然后服务端将字节流转换成自身能读取的格式,是一个序列化和反序列化的过程。
3、数据准备好了之后,如何进行传输?网络传输层需要把调用的ID和序列化后的参数传给服务端,然后把计算好的结果序列化传给客户端,因此TCP层即可完成上述过程,gRPC中采用的是HTTP2协议。

总结一下上述过程:
// Client端 
// Student student = Call(ServerAddr, addAge, student)
1. 将这个调用映射为Call ID。
2. 将Call ID,student(params)序列化,以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr,这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功,那么就将结果反序列化,并赋给student,年龄更新

// Server端
1. 在本地维护一个Call ID到函数指针的映射call_id_map,可以用Map<String, Method> callIdMap
2. 等待服务端请求
3. 得到一个请求后,将其数据包反序列化,得到Call ID
4. 通过在callIdMap中查找,得到相应的函数指针
5. 将student(params)反序列化后,在本地调用addAge()函数,得到结果
6. 将student结果序列化后通过网络返回给Client

QQ截图20200723155851.jpg


在微服务的设计中,一个服务A如果访问另一个Module下的服务B,可以采用HTTP REST传输数据,并在两个服务之间进行序列化和反序列化操作,服务B把执行结果返回过来。

QQ截图20200723155953.jpg


由于HTTP在应用层中完成,整个通信的代价较高,远程过程调用中直接基于TCP进行远程调用,数据传输在传输层TCP层完成,更适合对效率要求比较高的场景,RPC主要依赖于客户端和服务端之间建立Socket链接进行,底层实现比REST更复杂。

1.2 rpc demo

QQ截图20200723160048.jpg


QQ截图20200723160056.jpg

 
完整源码:https://github.com/guangxush/wheel/tree/master/RPC/src
 
2. gRPC的使用

2.1. gRPC与REST 
  • REST通常以业务为导向,将业务对象上执行的操作映射到HTTP动词,格式非常简单,可以使用浏览器进行扩展和传输,通过JSON数据完成客户端和服务端之间的消息通信,直接支持请求/响应方式的通信。不需要中间的代理,简化了系统的架构,不同系统之间只需要对JSON进行解析和序列化即可完成数据的传递。
  • 但是REST也存在一些弊端,比如只支持请求/响应这种单一的通信方式,对象和字符串之间的序列化操作也会影响消息传递速度,客户端需要通过服务发现的方式,知道服务实例的位置,在单个请求获取多个资源时存在着挑战,而且有时候很难将所有的动作都映射到HTTP动词。
  • 正是因为REST面临一些问题,因此可以采用gRPC作为一种替代方案,gRPC 是一种基于二进制流的消息协议,可以采用基于Protocol Buffer的IDL定义grpc API,这是Google公司用于序列化结构化数据提供的一套语言中立的序列化机制,客户端和服务端使用HTTP/2以Protocol Buffer格式交换二进制消息
  • gRPC的优势是,设计复杂更新操作的API非常简单,具有高效紧凑的进程通信机制,在交换大量消息时效率高,远程过程调用和消息传递时可以采用双向的流式消息方式,同时客户端和服务端支持多种语言编写,互操作性强;不过gRPC的缺点是不方便与JavaScript集成,某些防火墙不支持该协议。
  • 注册中心:当项目中有很多服务时,可以把所有的服务在启动的时候注册到一个注册中心里面,用于维护服务和服务器之间的列表,当注册中心接收到客户端请求时,去找到该服务是否远程可以调用,如果可以调用需要提供服务地址返回给客户端,客户端根据返回的地址和端口,去调用远程服务端的方法,执行完成之后将结果返回给客户端。这样在服务端加新功能的时候,客户端不需要直接感知服务端的方法,服务端将更新之后的结果在注册中心注册即可,而且当修改了服务端某些方法的时候,或者服务降级服务多机部署想实现负载均衡的时候,我们只需要更新注册中心的服务群即可。


QQ截图20200723160510.jpg


参考文档:
https://www.jianshu.com/p/7d6853140e13
https://www.jianshu.com/p/eb66b0c4113d
 
 

怎么理解软件开发中的上游和下游?

回复

zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 948 次浏览 • 2020-07-22 09:35 • 来自相关话题

IaaS,PaaS、SaaS分别指什么?有什么区别?

回复

zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 330 次浏览 • 2020-05-25 14:48 • 来自相关话题

数据结构:堆(Heap)

zkbhj 发表了文章 • 0 个评论 • 241 次浏览 • 2020-05-20 12:23 • 来自相关话题

堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

堆的常用方法:
 
构建优先队列支持堆排序快速找出一个集合中的最小值(或者最大值)在朋友面前装逼

堆属性

堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。

在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。

例子:






这是一个最大堆,,因为每一个父节点的值都比其子节点要大。10 比 7 和 2 都大。7 比 5 和 1都大。

根据这一属性,那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆,根节点中的元素总是树中的最小值。堆属性非常的有用,因为堆常常被当做优先队列使用,因为可以快速的访问到“最重要”的元素。

注意:堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。--唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。


堆和普通树的区别

堆并不能取代二叉搜索树,它们之间有相似之处也有一些不同。我们来看一下两者的主要差别:

节点的顺序。在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。

内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来存储数组,且不使用指针。

平衡。二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索。在二叉树中搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。

来自数组的树

用数组来实现树相关的数据结构也许看起来有点古怪,但是它在时间和空间山都是很高效的。

我们准备将上面的例子中的树这样存储:[ 10, 7, 2, 5, 1 ]就这多!我们除了一个简单的数组以外,不需要任何额外的空间。

如果我们不允许使用指针,那么我们怎么知道哪一个节点是父节点,哪一个节点是它的子节点呢?问得好!节点在数组中的位置index 和它的父节点以及子节点的索引之间有一个映射关系。

如果 i 是节点的索引,那么下面的公式就给出了它的父节点和子节点在数组中的位置:parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。
 
我们将写公式放到前面的例子中验证一下。





 
 

注意:根节点(10)没有父节点,因为 -1 不是一个有效的数组索引。同样,节点 (2),(5)和(1) 没有子节点,因为这些索引已经超过了数组的大小,所以我们在使用这些索引值的时候需要保证是有效的索引值。

 
复习一下,在最大堆中,父节点的值总是要大于(或者等于)其子节点的值。这意味下面的公式对数组中任意一个索引 i都成立:
 
array[parent(i)] >= array[i]
可以用上面的例子来验证一下这个堆属性。

如你所见,这些公式允许我们不使用指针就可以找到任何一个节点的父节点或者子节点。事情比简单的去掉指针要复杂,但这就是交易:我们节约了空间,但是要进行更多计算。幸好这些计算很快并且只需要O(1)的时间。

理解数组索引和节点位置之间的关系非常重要。这里有一个更大的堆,它有15个节点被分成了4层:






图片中的数字不是节点的值,而是存储这个节点的数组索引!这里是数组索引和树的层级之间的关系:





 
由上图可以看到,数组中父节点总是在子节点的前面。

注意这个方案与一些限制。你可以在普通二叉树中按照下面的方式组织数据,但是在堆中不可以:






在堆中,在当前层级所有的节点都已经填满之前不允许开是下一层的填充,所以堆总是有这样的形状:






注意:你可以使用普通树来模拟堆,但是那对空间是极大的浪费。

 
更多操作可以参考原文链接:
 
作者:唐先僧
链接:https://www.jianshu.com/p/6b526aa481b1
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 查看全部
堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

堆的常用方法:
 
  1. 构建优先队列
  2. 支持堆排序
  3. 快速找出一个集合中的最小值(或者最大值)
  4. 在朋友面前装逼


堆属性

堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。

在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。

例子:

QQ截图20200520120758.jpg


这是一个最大堆,,因为每一个父节点的值都比其子节点要大。10 比 7 和 2 都大。7 比 5 和 1都大。

根据这一属性,那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆,根节点中的元素总是树中的最小值。堆属性非常的有用,因为堆常常被当做优先队列使用,因为可以快速的访问到“最重要”的元素。


注意:堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。--唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。



堆和普通树的区别

堆并不能取代二叉搜索树,它们之间有相似之处也有一些不同。我们来看一下两者的主要差别:

节点的顺序。在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。

内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来存储数组,且不使用指针。

平衡。二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索。在二叉树中搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。

来自数组的树

用数组来实现树相关的数据结构也许看起来有点古怪,但是它在时间和空间山都是很高效的。

我们准备将上面的例子中的树这样存储:
[ 10, 7, 2, 5, 1 ]
就这多!我们除了一个简单的数组以外,不需要任何额外的空间。

如果我们不允许使用指针,那么我们怎么知道哪一个节点是父节点,哪一个节点是它的子节点呢?问得好!节点在数组中的位置index 和它的父节点以及子节点的索引之间有一个映射关系。

如果 i 是节点的索引,那么下面的公式就给出了它的父节点和子节点在数组中的位置:
parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2
注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。
 
我们将写公式放到前面的例子中验证一下。

QQ截图20200520121220.jpg

 
 


注意:根节点(10)没有父节点,因为 -1 不是一个有效的数组索引。同样,节点 (2),(5)和(1) 没有子节点,因为这些索引已经超过了数组的大小,所以我们在使用这些索引值的时候需要保证是有效的索引值。


 
复习一下,在最大堆中,父节点的值总是要大于(或者等于)其子节点的值。这意味下面的公式对数组中任意一个索引 i都成立:
 
array[parent(i)] >= array[i]
可以用上面的例子来验证一下这个堆属性。

如你所见,这些公式允许我们不使用指针就可以找到任何一个节点的父节点或者子节点。事情比简单的去掉指针要复杂,但这就是交易:我们节约了空间,但是要进行更多计算。幸好这些计算很快并且只需要O(1)的时间。

理解数组索引和节点位置之间的关系非常重要。这里有一个更大的堆,它有15个节点被分成了4层:

QQ截图20200520121352.jpg


图片中的数字不是节点的值,而是存储这个节点的数组索引!这里是数组索引和树的层级之间的关系:

QQ截图20200520121418.jpg

 
由上图可以看到,数组中父节点总是在子节点的前面。

注意这个方案与一些限制。你可以在普通二叉树中按照下面的方式组织数据,但是在堆中不可以:

QQ截图20200520121555.jpg


在堆中,在当前层级所有的节点都已经填满之前不允许开是下一层的填充,所以堆总是有这样的形状:

QQ截图20200520121602.jpg


注意:你可以使用普通树来模拟堆,但是那对空间是极大的浪费。


 
更多操作可以参考原文链接:
 
作者:唐先僧
链接:https://www.jianshu.com/p/6b526aa481b1
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

数据结构之:平衡树

zkbhj 发表了文章 • 0 个评论 • 208 次浏览 • 2020-05-08 11:47 • 来自相关话题

一.概念:

   平衡树是二叉搜索树和堆合并构成的数据结构,它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二.优势

   对一棵查找树(search tree)进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。

三.种类:

  平衡二叉树的常用实现方法有红黑树(rbt)、AVL、替罪羊树、Treap、伸展树(spaly)、SBT
 
四、为何引入平衡树?解决什么问题?
 
   一个长度为n的有序序列,从中查找一个指定的值,要花多少时间?
   一个最简单的做法就是一个个去试。如果你运气好,第一个就碰上了;如果你运气不好,最后一个才是你要查的值,那就需要把n个值都检查一遍。时间复杂度O(n)。
当然你可能注意到了有序这个有用的性质,所以可以采用二分查找的方式,具体就不赘述了。时间复杂度O(log(n))。
   但是如果要添加一个数据(及动态更新)怎么办?要保证序列的有序性,你必须要插入到适当的位置。这个位置同样可以通过二分查找在O(log(n))的时间中找出。
可是插入的过程呢?我们必须把后面的数据一个个顺次往后挪一格,而这需要O(n)的时间。 这也意味着删除的时间复杂度也就是O(n)。太慢了!无法满足大数据底线O(nlogn)左右的时间复杂度。所以我们需要快一点的方法(数据结构)。

下面介绍其中的一种实现:红黑树——这是一个在当今信息界公认的最快的平衡二叉树之一。STL(Standard Template Library,C++里的一个标准库)里的< set >与< map >就由其作为底层数据结构。
 
红黑树
 
  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性:

(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意:

(01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
(02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。





 
实际应用
 
红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。
 
————————————————
版权声明:本文为CSDN博主「zhengx辉」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/yiye2017zhangmu/java/article/details/81516337
更多参考文档:
https://blog.csdn.net/lemonoil/java/article/details/54405613
https://www.cnblogs.com/skywang12345/p/3245399.html
https://mp.weixin.qq.com/s/jz1ajDUygZ7sXLQFHyfjWA
 
  查看全部
一.概念:

   平衡树是二叉搜索树和堆合并构成的数据结构,它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

二.优势

   对一棵查找树(search tree)进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。

三.种类:

  平衡二叉树的常用实现方法有红黑树(rbt)、AVL、替罪羊树、Treap、伸展树(spaly)、SBT
 
四、为何引入平衡树?解决什么问题?
 
   一个长度为n的有序序列,从中查找一个指定的值,要花多少时间?
   一个最简单的做法就是一个个去试。如果你运气好,第一个就碰上了;如果你运气不好,最后一个才是你要查的值,那就需要把n个值都检查一遍。时间复杂度O(n)。
当然你可能注意到了有序这个有用的性质,所以可以采用二分查找的方式,具体就不赘述了。时间复杂度O(log(n))。
   但是如果要添加一个数据(及动态更新)怎么办?要保证序列的有序性,你必须要插入到适当的位置。这个位置同样可以通过二分查找在O(log(n))的时间中找出。
可是插入的过程呢?我们必须把后面的数据一个个顺次往后挪一格,而这需要O(n)的时间。 这也意味着删除的时间复杂度也就是O(n)。太慢了!无法满足大数据底线O(nlogn)左右的时间复杂度。所以我们需要快一点的方法(数据结构)

下面介绍其中的一种实现:红黑树——这是一个在当今信息界公认的最快的平衡二叉树之一。STL(Standard Template Library,C++里的一个标准库)里的< set >与< map >就由其作为底层数据结构。
 
红黑树
 
  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性:

(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意:

(01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
(02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

251730074203156.jpg

 
实际应用
 
红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。
 
————————————————
版权声明:本文为CSDN博主「zhengx辉」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/yiye2017zhangmu/java/article/details/81516337
更多参考文档:
https://blog.csdn.net/lemonoil/java/article/details/54405613
https://www.cnblogs.com/skywang12345/p/3245399.html
https://mp.weixin.qq.com/s/jz1ajDUygZ7sXLQFHyfjWA
 
 

神经病和精神病是一个病吗?有什么区别?

回复

zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 518 次浏览 • 2020-04-30 14:49 • 来自相关话题

序列化结构数据方法ProtoBuf使用(PHP和Go)

zkbhj 发表了文章 • 0 个评论 • 273 次浏览 • 2020-04-13 17:24 • 来自相关话题

一、在PHP下使用ProtoBuf
 
PHP如果要使用protobuf 需要安装 protoc+ 安装protobuf composer包
 
protoc用于根据protobuf数据结构文件(.proto)生成对应的类,用于生成protobuf文件安装 google/protobuf composer 包composer require google/protobuf
 
怎么用呢?开搞!
 
1、首先,需要定一个消息类型。创建一个关于Person的定义文件(以.proto为后缀),如示例为person.proto,文件内容如下:
syntax="proto3";
package test;
message Person{
string name=1;//姓名
int32 age=2;//年龄
bool sex=3;//性别

syntax="proto3":表明使用的是proto3格式,如果不指定则为proto2package test:定义包名为test,生成类时,会产生一个目录为testmessage Person:消息主体内容,里面为各个字段的定义
 
2、生成对应的PHP类
 
定义好Person的格式后,该格式如果不生成我们所需要的类库,其实是无任何意义的,还google提供一个工具protoc生成我们要的类库。也就是最开始说的 protoc!
 
proto 最新版的下载地址是:最新3.11.3。可以通过 官方包Release 进行有选择的下载。
tar -zxvf protobuf-php-3.11.3.tar.gz
cd protobuf-3.11.3
./configure --prefix=/usr/local/protobuf
make
make install解压安装完后,就可以通过下面的命令,生成对应的类库了:
/usr/
local/protobuf/bin/protoc --php_out=./ person.proto生成后将在当前目录产生如下文件:
 
GPBMetadata/Person.phpTest/Person.php
 
3、类库生成完了,就可以在PHP项目中使用ProtoBuf了:

在PHP中使用ProtoBuf依赖一个protobuf的扩展,目前提供两种方式进行使用: 
php的c扩展,php的lib扩展包,
 
这两者均可在刚才下载包里可以找到。
 
另外,也可以使用composer进行安装该依赖扩展:
composer require google/protobuf
这里我主要是使用composer安装,应该它可以帮我产生autoload。安装好依赖后,我们就可以开始在php环境下使用protobuf了。

序列化
<?php
include 'vendor/autoload.php';
include 'GPBMetadata/Person.php';
include 'Test/Person.php';
$bindata = file_get_contents('./data.bin');
$person = new Test\Person();
$person->mergeFromString($bindata);
echo $person->getName();运行后,产生的data.bin,只有14Byte
 
反序列化
<?php
include 'vendor/autoload.php';
include 'GPBMetadata/Person.php';
include 'Test/Person.php';
$bindata = file_get_contents('./data.bin');
$person = new Test\Person();
$person->mergeFromString($bindata);
echo $person->getName();PHP常用的使用方法:

序列化:
1、serializeToString:序列化成二进制字符串
2、serializeToJsonString:序列化成JSON字符串

反序列化:
1、mergeFromString:二进制字符串反序列化
2、mergeFromJsonString:Json字符串反序列化

二、在Golang下使用ProtoBuf
 
安装protoc的方法和PHP中类型,编译安装即可。
 
安装好之后,需要安装ProtoBuf的编译器插件:protoc-gen-go:
 
进入GOPATH目录,运行:
go get -u github.com/golang/protobuf/protoc-gen-go  如果成功,会在GOPATH/bin下生成protoc-gen-go.exe文件(Windows上)。
 
1、准备好之后,就可以开始写proto文件了。假设文件目录为:
$GOPATH/src/test/protobuf/pb/user.proto代码如下:
//指定版本
//注意proto3与proto2的写法有些不同
syntax = "proto3";

//包名,通过protoc生成时go文件时
package test;

//手机类型
//枚举类型第一个字段必须为0
enum PhoneType {
HOME = 0;
WORK = 1;
}

//手机
message Phone {
PhoneType type = 1;
string number = 2;
}

//人
message Person {
//后面的数字表示标识号
int32 id = 1;
string name = 2;
//repeated表示可重复
//可以有多个手机
repeated Phone phones = 3;
}

//联系簿
message ContactBook {
repeated Person persons = 1;
}然后运行如下命令:
protoc --go_out=. *.proto
会生成一个user.pb.go的文件。
 
2、使用:
package main;

import (
"github.com/golang/protobuf/proto"
"go_dev/kongji/proto/test"
"io/ioutil"
"os"
"fmt"
)

func write() {
p1 := &test.Person{
Id: 1,
Name: "小张",
Phones: []*test.Phone{
{test.PhoneType_HOME, "111111111"},
{test.PhoneType_WORK, "222222222"},
},
};
p2 := &test.Person{
Id: 2,
Name: "小王",
Phones: []*test.Phone{
{test.PhoneType_HOME, "333333333"},
{test.PhoneType_WORK, "444444444"},
},
};

//创建地址簿
book := &test.ContactBook{};
book.Persons = append(book.Persons, p1);
book.Persons = append(book.Persons, p2);

//编码数据
data, _ := proto.Marshal(book);
//把数据写入文件
ioutil.WriteFile("./test.txt", data, os.ModePerm);
}

func read() {
//读取文件数据
data, _ := ioutil.ReadFile("./test.txt");
book := &test.ContactBook{};
//解码数据
proto.Unmarshal(data, book);
for _, v := range book.Persons {
fmt.Println(v.Id, v.Name);
for _, vv := range v.Phones {
fmt.Println(vv.Type, vv.Number);
}
}
}

func main() {
write();
read();
}
 

内容整理自下面链接:
https://www.jianshu.com/p/ce098058edf0
https://developers.google.cn/protocol-buffers/docs/gotutorial
https://developers.google.cn/protocol-buffers/docs/reference/go-generated
  查看全部
一、在PHP下使用ProtoBuf
 
PHP如果要使用protobuf 需要安装 protoc+ 安装protobuf composer包
 
  • protoc用于根据protobuf数据结构文件(.proto)生成对应的类,用于生成protobuf文件
  • 安装 google/protobuf composer 包composer require google/protobuf

 
怎么用呢?开搞!
 
1、首先,需要定一个消息类型。创建一个关于Person的定义文件(以.proto为后缀),如示例为person.proto,文件内容如下:
syntax="proto3";
package test;
message Person{
string name=1;//姓名
int32 age=2;//年龄
bool sex=3;//性别
}
 
  1. syntax="proto3":表明使用的是proto3格式,如果不指定则为proto2
  2. package test:定义包名为test,生成类时,会产生一个目录为test
  3. message Person:消息主体内容,里面为各个字段的定义

 
2、生成对应的PHP类
 
定义好Person的格式后,该格式如果不生成我们所需要的类库,其实是无任何意义的,还google提供一个工具protoc生成我们要的类库。也就是最开始说的 protoc!
 
proto 最新版的下载地址是:最新3.11.3。可以通过 官方包Release 进行有选择的下载。
tar -zxvf protobuf-php-3.11.3.tar.gz
cd protobuf-3.11.3
./configure --prefix=/usr/local/protobuf
make
make install
解压安装完后,就可以通过下面的命令,生成对应的类库了:
/usr/
local/protobuf/bin/protoc --php_out=./ person.proto
生成后将在当前目录产生如下文件:
 
  • GPBMetadata/Person.php
  • Test/Person.php

 
3、类库生成完了,就可以在PHP项目中使用ProtoBuf了:

在PHP中使用ProtoBuf依赖一个protobuf的扩展,目前提供两种方式进行使用: 
  1. php的c扩展,
  2. php的lib扩展包,

 
这两者均可在刚才下载包里可以找到。
 
另外,也可以使用composer进行安装该依赖扩展:
composer require google/protobuf

这里我主要是使用composer安装,应该它可以帮我产生autoload。安装好依赖后,我们就可以开始在php环境下使用protobuf了。

序列化
<?php
include 'vendor/autoload.php';
include 'GPBMetadata/Person.php';
include 'Test/Person.php';
$bindata = file_get_contents('./data.bin');
$person = new Test\Person();
$person->mergeFromString($bindata);
echo $person->getName();
运行后,产生的data.bin,只有14Byte
 
反序列化
<?php
include 'vendor/autoload.php';
include 'GPBMetadata/Person.php';
include 'Test/Person.php';
$bindata = file_get_contents('./data.bin');
$person = new Test\Person();
$person->mergeFromString($bindata);
echo $person->getName();
PHP常用的使用方法:

序列化:
1、serializeToString:序列化成二进制字符串
2、serializeToJsonString:序列化成JSON字符串

反序列化:
1、mergeFromString:二进制字符串反序列化
2、mergeFromJsonString:Json字符串反序列化

二、在Golang下使用ProtoBuf
 
安装protoc的方法和PHP中类型,编译安装即可。
 
安装好之后,需要安装ProtoBuf的编译器插件:protoc-gen-go:
 
进入GOPATH目录,运行:
go get -u github.com/golang/protobuf/protoc-gen-go
  如果成功,会在GOPATH/bin下生成protoc-gen-go.exe文件(Windows上)。
 
1、准备好之后,就可以开始写proto文件了。假设文件目录为:
$GOPATH/src/test/protobuf/pb/user.proto
代码如下:
//指定版本
//注意proto3与proto2的写法有些不同
syntax = "proto3";

//包名,通过protoc生成时go文件时
package test;

//手机类型
//枚举类型第一个字段必须为0
enum PhoneType {
HOME = 0;
WORK = 1;
}

//手机
message Phone {
PhoneType type = 1;
string number = 2;
}

//人
message Person {
//后面的数字表示标识号
int32 id = 1;
string name = 2;
//repeated表示可重复
//可以有多个手机
repeated Phone phones = 3;
}

//联系簿
message ContactBook {
repeated Person persons = 1;
}
然后运行如下命令:
 protoc --go_out=. *.proto
会生成一个user.pb.go的文件。
 
2、使用:
package main;

import (
"github.com/golang/protobuf/proto"
"go_dev/kongji/proto/test"
"io/ioutil"
"os"
"fmt"
)

func write() {
p1 := &test.Person{
Id: 1,
Name: "小张",
Phones: []*test.Phone{
{test.PhoneType_HOME, "111111111"},
{test.PhoneType_WORK, "222222222"},
},
};
p2 := &test.Person{
Id: 2,
Name: "小王",
Phones: []*test.Phone{
{test.PhoneType_HOME, "333333333"},
{test.PhoneType_WORK, "444444444"},
},
};

//创建地址簿
book := &test.ContactBook{};
book.Persons = append(book.Persons, p1);
book.Persons = append(book.Persons, p2);

//编码数据
data, _ := proto.Marshal(book);
//把数据写入文件
ioutil.WriteFile("./test.txt", data, os.ModePerm);
}

func read() {
//读取文件数据
data, _ := ioutil.ReadFile("./test.txt");
book := &test.ContactBook{};
//解码数据
proto.Unmarshal(data, book);
for _, v := range book.Persons {
fmt.Println(v.Id, v.Name);
for _, vv := range v.Phones {
fmt.Println(vv.Type, vv.Number);
}
}
}

func main() {
write();
read();
}

 

内容整理自下面链接:
https://www.jianshu.com/p/ce098058edf0
https://developers.google.cn/protocol-buffers/docs/gotutorial
https://developers.google.cn/protocol-buffers/docs/reference/go-generated
 

序列化结构数据方法ProtoBuf源码解读

zkbhj 发表了文章 • 0 个评论 • 342 次浏览 • 2020-04-13 16:53 • 来自相关话题

在上一篇 《序列化结构数据方法ProtoBuf编码》 中,我们详细解析了 ProtoBuf 的编码原理。

有了这个知识储备,我们就可以深入 ProtoBuf 序列化、反序列化的源码,从代码的层面理解 ProtoBuf 具体是如何实现对数据的编码(序列化)和解码(反序列化)的。

我们重新复习一下, ProtoBuf 的序列化使用过程:
 
定义 .proto 文件protoc 编译器编译 .proto 文件生成一系列接口代码调用生成的接口实现对 .proto 定义的字段的读取以及 message 对象的序列化、反序列化方法

具体调用代码如下:
Example1 example1;
example1.set_int32val(val);
example1.set_stringval("hello,world");
example1.SerializeToString(&output);
调用 SerializeToString 函数将 example1 对象序列化(编码)成字符串。我们的目的就是了解 SerializeToString 函数里到底发生了什么,是怎么一步一步得到最终的序列化结果的。
 

注意:并非编码成字符串数据,string 只是作为编码结果的容器


我们在 .proto 文件中定义的 message 在最终生成的对应语言的代码中,例如在 C++ (xxxx.pb.h、xxxx.pb.cpp) 中每一个在 .proto 文件中定义的 message 字段都会在代码中构造成一个类,且这些 message 消息类继承于 ::google::protobuf::Message,而 ::google::protobuf::Message 继承于一个更为轻量的 MessageLite 类。其相关的类图如下所示:





 
而我们经常调用的序列化函数 SerializeToString 并定义在基类 MessageLite 中。
 
编码

当某个 Message 调用 SerializeToString 时,经过一层层调用最终会调用底层的关键编码函数 WriteVarint32ToArray 或 WriteVarint64ToArray,整个过程如下图所示:






WriteVarint32ToArray 函数可在源码目录下的 google.protobuf.io 包下的 coded_stream.h 中找到。在上一篇 深入 ProtoBuf - 编码 中我们解析了 Varint 编码原理和详细过程,WriteVarint32ToArray(以及 WriteVarint64ToArray)并是 Varint 编码的核心。

可以对照上一篇指出的 Varints 编码的几个关键点来阅读以下代码,可以看出编码实现确实优雅,代码如下:inline uint8* CodedOutputStream::WriteVarint32ToArray(uint32 value, uint8* target) {
// 0x80 -> 1000 0000
// 大于 1000 0000 意味这进行 Varints 编码时至少需要两个字节
// 如果 value < 0x80,则只需要一个字节,编码结果和原值一样,则没有循环直接返回
// 如果至少需要两个字节
while (value >= 0x80) {
// 如果还有后续字节,则 value | 0x80 将 value 的最后字节的最高 bit 位设置为 1,并取后七位
*target = static_cast<uint8>(value | 0x80);
// 处理完七位,后移,继续处理下一个七位
value >>= 7;
// 指针加一,(数组后移一位)
++target;
}
// 跳出循环,则表示已无后续字节,但还有最后一个字节

// 把最后一个字节放入数组
*target = static_cast<uint8>(value);
// 结束地址指向数组最后一个元素的末尾
return target + 1;
}

// Varint64 同理
inline uint8* CodedOutputStream::WriteVarint64ToArray(uint64 value,
uint8* target) {
while (value >= 0x80) {
*target = static_cast<uint8>(value | 0x80);
value >>= 7;
++target;
}
*target = static_cast<uint8>(value);
return target + 1;
}在上面已添加详细注释,这里再强调几个关键点。
 
value | 0x80:xxx ... xxxx xxxx | 000 ... 1000 0000 的结果其实就是将最后一个字节的第一个 bit(最高位) 置 1,其他位不变,即 xxx ... 1xxx xxxx。注意 target 是 uint8 类型的指针,这意味它只会截断获取最后一个字节,即 1xxx xxxx,这里的 1 意味着什么?这个 1 就是所谓的 msb 了,意味着后续还有字节。之后就是右移 7 位(去掉最后 7 位),处理下一个 7位。通过这里的代码应该可以体会到为什么 Varints 编码结果是低位排在前面了。

了解了最底层 IO 包中的编码函数,再结合上篇文章介绍的编码原理,对 ProtoBuf 的编码应该有了更深入的认识。

Varints 类型序列化实现

int32、int64、uint32、uint64

int32 类型编码函数对应为 WriteInt32ToArray,源码如下:// WriteTagToArray 函数将 Tag 部分写入
// WriteInt32NoTagToArray 函数将 Value 部分写入
// WriteTagToArray 和 WriteInt32NoTagToArray 底层
// 均调用 coded_stream.h 中的 WriteVarint32ToArray
//因为 ProtoBuf 中的 Tag 均采用 Varint 编码
// int32 的 Value 部分也采用 Varint 编码
inline uint8* WireFormatLite::WriteInt32ToArray(int field_number, int32 value,
uint8* target) {
target = WriteTagToArray(field_number, WIRETYPE_VARINT, target);
return WriteInt32NoTagToArray(value, target);
}int64、uint32、uint64 类型与 int32 类型同理,只是处理位数有所不同。

uint32 和 uint64 也是采用 Varint 编码,所以底层编码实现与 int32、int64 一致。

 sint32、sint64

这两种类型编码函数对应为 WriteSInt32ToArray 和 WriteSInt64ToArray 。

在上一篇文章 深入 ProtoBuf - 编码 中我们已经介绍过 Varint 编码在负数的情况下编码效率很低,固对于 sint32、sint64 类型我们会采用 ZigZag 编码将负数映射成正数然后再进行 Varint 编码,而这种映射并非采用存储的 Map,而是使用移位实现。sint32 的 ZigZag 源码实现如下:inline uint32 WireFormatLite::ZigZagEncode32(int32 n) {
// 右移为算数右移
// 左移时需要先将 n 转成 uint32 类型,防止溢出
// 当 n 为正数时 result = 2 * n
// 当 n 为负数时 result = - (2 * n + 1)
return (static_cast<uint32>(n) << 1) ^ static_cast<uint32>(n >> 31);
}经过 ZigZagEncode32 编码之后,数字成为一个正数,之后等同于 int32 或 int64 进行完全相同的编码处理。

bool 与 enum

bool 和 enum 本质就是整型,编码处理与 int32、int64 相同。

32-bit、64-bit
fixed32/fixed64

fixed32 类型对应 WriteFixed32ToArray 函数,32-bit、64-bit类型的字段比起上述 Varint 类型则要简单的多,因为每个数字均是固定字节,源码如下:inline uint8* WireFormatLite::WriteSFixed32ToArray(int field_number,
int32 value, uint8* target) {
target = WriteTagToArray(field_number, WIRETYPE_FIXED32, target);
return WriteSFixed32NoTagToArray(value, target);
}其中 WriteSFixed32NoTagToArray 源码如下:
inline uint8* WireFormatLite::WriteSFixed32NoTagToArray(int32 value,
uint8* target) {
return io::CodedOutputStream::WriteLittleEndian32ToArray(
static_cast<uint32>(value), target);
}由此可知,对于位数固定的 sfixed32 是将其转成 uint32 类型,然后使用与 fixed32 相同的函数写入。

sfixed64 与 sfixed32 同理,不赘述。
 
Length delimited 字段序列化

因为其编码结构为 Tag - Length - Value,所以其字段完整的序列化会稍微多出一些过程,其中有一些需要我们进一步整理。现在以一个 string 类型字段的序列化为例,来看看其序列化的完整过程,画出其程序时序图(上文出现过)如下:






可对照上述时序图来阅读源码,其序列化实现的几个关键函数为:
 
ByteSizeLong:计算对象序列化所需要的空间大小,在内存中开辟相应大小的空间WriteTagToArray:将 Tag 值写入到之前开辟的内存中WriteStringWithSizeToArray:将 Length + Value 值写入到之前开辟的内存中

其序列化代码的重点过程在上图的右下角,先是调用 WriteTagToArray 函数将 Tag 值写入到内存,返回指向下一个字节的指针以便继续写入。调用 WriteStringWithSizeToArray 函数,这个函数主要又执行了两个函数,先是执行 WriteVarint32ToArray 函数(注意 WriteTagToArray 内部调用的也是这个函数,因为 Tag 和 Length 都采用 Varints 编码),此函数的作用是将 Length 写入。执行的第二个函数为 WriteStringToArray,此函数的作用是将 Value(一个 UTF-8 string 值) 写入到内存,其中底层调用了 memcpy() 函数。

综上,对于 Varint 类型的字段自然采用 Varint 编码。

而对于 Length delimited 类型的字段,Tag-Length-Value 中的 Tag 和 Length 依然采用 Varint 编码,Value 若为 String 等类型,则直接进行 memcpy。

另外对于 embedded message 或 packed repeated ,则套用上述规则。底层编码实现实际并是遍历字段下所有内嵌字段,然后递归调用编码函数即可。

作者:404_89_117_101
链接:https://www.jianshu.com/p/62f0238beec8
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 查看全部
在上一篇 《序列化结构数据方法ProtoBuf编码》 中,我们详细解析了 ProtoBuf 的编码原理。

有了这个知识储备,我们就可以深入 ProtoBuf 序列化、反序列化的源码,从代码的层面理解 ProtoBuf 具体是如何实现对数据的编码(序列化)和解码(反序列化)的。

我们重新复习一下, ProtoBuf 的序列化使用过程:
 
  • 定义 .proto 文件
  • protoc 编译器编译 .proto 文件生成一系列接口代码
  • 调用生成的接口实现对 .proto 定义的字段的读取以及 message 对象的序列化、反序列化方法


具体调用代码如下:
Example1 example1;
example1.set_int32val(val);
example1.set_stringval("hello,world");
example1.SerializeToString(&output);

调用 SerializeToString 函数将 example1 对象序列化(编码)成字符串。我们的目的就是了解 SerializeToString 函数里到底发生了什么,是怎么一步一步得到最终的序列化结果的。
 


注意:并非编码成字符串数据,string 只是作为编码结果的容器



我们在 .proto 文件中定义的 message 在最终生成的对应语言的代码中,例如在 C++ (xxxx.pb.h、xxxx.pb.cpp) 中每一个在 .proto 文件中定义的 message 字段都会在代码中构造成一个类,且这些 message 消息类继承于 ::google::protobuf::Message,而 ::google::protobuf::Message 继承于一个更为轻量的 MessageLite 类。其相关的类图如下所示:

QQ截图20200413164703.jpg

 
而我们经常调用的序列化函数 SerializeToString 并定义在基类 MessageLite 中。
 
编码

当某个 Message 调用 SerializeToString 时,经过一层层调用最终会调用底层的关键编码函数 WriteVarint32ToArray 或 WriteVarint64ToArray,整个过程如下图所示:

6009978-d3f8eaef64fe78e9.png


WriteVarint32ToArray 函数可在源码目录下的 google.protobuf.io 包下的 coded_stream.h 中找到。在上一篇 深入 ProtoBuf - 编码 中我们解析了 Varint 编码原理和详细过程,WriteVarint32ToArray(以及 WriteVarint64ToArray)并是 Varint 编码的核心。

可以对照上一篇指出的 Varints 编码的几个关键点来阅读以下代码,可以看出编码实现确实优雅,代码如下:
inline uint8* CodedOutputStream::WriteVarint32ToArray(uint32 value, uint8* target) {
// 0x80 -> 1000 0000
// 大于 1000 0000 意味这进行 Varints 编码时至少需要两个字节
// 如果 value < 0x80,则只需要一个字节,编码结果和原值一样,则没有循环直接返回
// 如果至少需要两个字节
while (value >= 0x80) {
// 如果还有后续字节,则 value | 0x80 将 value 的最后字节的最高 bit 位设置为 1,并取后七位
*target = static_cast<uint8>(value | 0x80);
// 处理完七位,后移,继续处理下一个七位
value >>= 7;
// 指针加一,(数组后移一位)
++target;
}
// 跳出循环,则表示已无后续字节,但还有最后一个字节

// 把最后一个字节放入数组
*target = static_cast<uint8>(value);
// 结束地址指向数组最后一个元素的末尾
return target + 1;
}

// Varint64 同理
inline uint8* CodedOutputStream::WriteVarint64ToArray(uint64 value,
uint8* target) {
while (value >= 0x80) {
*target = static_cast<uint8>(value | 0x80);
value >>= 7;
++target;
}
*target = static_cast<uint8>(value);
return target + 1;
}
在上面已添加详细注释,这里再强调几个关键点。
 
  • value | 0x80:xxx ... xxxx xxxx | 000 ... 1000 0000 的结果其实就是将最后一个字节的第一个 bit(最高位) 置 1,其他位不变,即 xxx ... 1xxx xxxx。注意 target 是 uint8 类型的指针,这意味它只会截断获取最后一个字节,即 1xxx xxxx,这里的 1 意味着什么?这个 1 就是所谓的 msb 了,意味着后续还有字节。之后就是右移 7 位(去掉最后 7 位),处理下一个 7位。
  • 通过这里的代码应该可以体会到为什么 Varints 编码结果是低位排在前面了。


了解了最底层 IO 包中的编码函数,再结合上篇文章介绍的编码原理,对 ProtoBuf 的编码应该有了更深入的认识。

Varints 类型序列化实现

int32、int64、uint32、uint64

int32 类型编码函数对应为 WriteInt32ToArray,源码如下:
// WriteTagToArray 函数将 Tag 部分写入
// WriteInt32NoTagToArray 函数将 Value 部分写入
// WriteTagToArray 和 WriteInt32NoTagToArray 底层
// 均调用 coded_stream.h 中的 WriteVarint32ToArray
//因为 ProtoBuf 中的 Tag 均采用 Varint 编码
// int32 的 Value 部分也采用 Varint 编码
inline uint8* WireFormatLite::WriteInt32ToArray(int field_number, int32 value,
uint8* target) {
target = WriteTagToArray(field_number, WIRETYPE_VARINT, target);
return WriteInt32NoTagToArray(value, target);
}
int64、uint32、uint64 类型与 int32 类型同理,只是处理位数有所不同。


uint32 和 uint64 也是采用 Varint 编码,所以底层编码实现与 int32、int64 一致。


 sint32、sint64

这两种类型编码函数对应为 WriteSInt32ToArray 和 WriteSInt64ToArray 。

在上一篇文章 深入 ProtoBuf - 编码 中我们已经介绍过 Varint 编码在负数的情况下编码效率很低,固对于 sint32、sint64 类型我们会采用 ZigZag 编码将负数映射成正数然后再进行 Varint 编码,而这种映射并非采用存储的 Map,而是使用移位实现。sint32 的 ZigZag 源码实现如下:
inline uint32 WireFormatLite::ZigZagEncode32(int32 n) {
// 右移为算数右移
// 左移时需要先将 n 转成 uint32 类型,防止溢出
// 当 n 为正数时 result = 2 * n
// 当 n 为负数时 result = - (2 * n + 1)
return (static_cast<uint32>(n) << 1) ^ static_cast<uint32>(n >> 31);
}
经过 ZigZagEncode32 编码之后,数字成为一个正数,之后等同于 int32 或 int64 进行完全相同的编码处理。

bool 与 enum

bool 和 enum 本质就是整型,编码处理与 int32、int64 相同。

32-bit、64-bit
fixed32/fixed64

fixed32 类型对应 WriteFixed32ToArray 函数,32-bit、64-bit类型的字段比起上述 Varint 类型则要简单的多,因为每个数字均是固定字节,源码如下:
inline uint8* WireFormatLite::WriteSFixed32ToArray(int field_number,
int32 value, uint8* target) {
target = WriteTagToArray(field_number, WIRETYPE_FIXED32, target);
return WriteSFixed32NoTagToArray(value, target);
}
其中 WriteSFixed32NoTagToArray 源码如下:
inline uint8* WireFormatLite::WriteSFixed32NoTagToArray(int32 value,
uint8* target) {
return io::CodedOutputStream::WriteLittleEndian32ToArray(
static_cast<uint32>(value), target);
}
由此可知,对于位数固定的 sfixed32 是将其转成 uint32 类型,然后使用与 fixed32 相同的函数写入。

sfixed64 与 sfixed32 同理,不赘述。
 
Length delimited 字段序列化

因为其编码结构为 Tag - Length - Value,所以其字段完整的序列化会稍微多出一些过程,其中有一些需要我们进一步整理。现在以一个 string 类型字段的序列化为例,来看看其序列化的完整过程,画出其程序时序图(上文出现过)如下:

6009978-d3f8eaef64fe78e9.png


可对照上述时序图来阅读源码,其序列化实现的几个关键函数为:
 
  • ByteSizeLong:计算对象序列化所需要的空间大小,在内存中开辟相应大小的空间
  • WriteTagToArray:将 Tag 值写入到之前开辟的内存中
  • WriteStringWithSizeToArray:将 Length + Value 值写入到之前开辟的内存中


其序列化代码的重点过程在上图的右下角,先是调用 WriteTagToArray 函数将 Tag 值写入到内存,返回指向下一个字节的指针以便继续写入。调用 WriteStringWithSizeToArray 函数,这个函数主要又执行了两个函数,先是执行 WriteVarint32ToArray 函数(注意 WriteTagToArray 内部调用的也是这个函数,因为 Tag 和 Length 都采用 Varints 编码),此函数的作用是将 Length 写入。执行的第二个函数为 WriteStringToArray,此函数的作用是将 Value(一个 UTF-8 string 值) 写入到内存,其中底层调用了 memcpy() 函数。

综上,对于 Varint 类型的字段自然采用 Varint 编码。

而对于 Length delimited 类型的字段,Tag-Length-Value 中的 Tag 和 Length 依然采用 Varint 编码,Value 若为 String 等类型,则直接进行 memcpy。

另外对于 embedded message 或 packed repeated ,则套用上述规则。底层编码实现实际并是遍历字段下所有内嵌字段,然后递归调用编码函数即可。

作者:404_89_117_101
链接:https://www.jianshu.com/p/62f0238beec8
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

序列化结构数据方法ProtoBuf编码

zkbhj 发表了文章 • 0 个评论 • 308 次浏览 • 2020-04-13 16:26 • 来自相关话题

上一篇《序列化结构数据方法ProtoBuf初探》是对ProtoBuf的简单介绍和特点对比。接下来这篇主要总结的是ProtoBuf的编码方式。
 
编码结构

TLV 格式是我们比较熟悉的编码格式。
 

所谓的 TLV 即 Tag - Length - Value。Tag 作为该字段的唯一标识,Length 代表 Value 数据域的长度,最后的 Value 并是数据本身。


ProtoBuf 编码采用类似的结构,但是实际上又有较大区别,其编码结构可见下图:






我们来一步步解析上图所表达的编码结构。

首先,每一个 message 进行编码,其结果由一个个字段组成,每个字段可划分为 Tag - [Length] - Value,如下图所示:





 

特别注意这里的 [Length] 是可选的,含义是针对不同类型的数据编码结构可能会变成 Tag - Value 的形式,如果变成这样的形式,没有了 Length 我们该如何确定 Value 的边界?答案就是 Varint 编码,在后面将详细介绍。


继续深入 Tag ,Tag 由 field_number 和 wire_type 两个部分组成: 
field_number: message 定义字段时指定的字段编号wire_type: ProtoBuf 编码类型,根据这个类型选择不同的 Value 编码方案。

整个 Tag 采用 Varints 编码方案进行编码,Varints 编码会在后面详细介绍。

Tag 结构如下图所示:






3 bit 的 wire_type 最多可以表达 8 种编码类型,目前 ProtoBuf 已经定义了 6 种,如下图所示:






第一列即是对应的类型编号,第二列为面向最终编码的编码类型,第三列是面向开发者的 message 字段的类型。
 

注意其中的 Start group 和 End group 两种类型已被遗弃。

 
 

另外要特别注意一点,虽然 wire_type 代表编码类型,但是 Varint 这个编码类型里针对 sint32、sint64 又会有一些特别编码(ZigTag 编码)处理,相当于 Varint 这个编码类型里又存在两种不同编码。


重新来看完整的编码结构图,现在我们可以理解一个 message 编码将由一个个的 field 组成,每个 field 根据类型将有如下两种格式:
 
Tag - Length - Value:编码类型表中 Type = 2 即 Length-delimited 编码类型将使用这种结构,Tag - Value:编码类型表中 Varint、64-bit、32-bit 使用这种结构。


其中 Tag 由字段编号 field_number 和 编码类型 wire_type 组成, Tag 整体采用 Varints 编码。

现在来模拟一下,我们接收到了一串序列化的二进制数据,我们先读一个 Varints 编码块,进行 Varints 解码,读取最后 3 bit 得到 wire_type(由此可知是后面的 Value 采用的哪种编码),随后获取到 field_number (由此可知是哪一个字段)。依据 wire_type 来正确读取后面的 Value。接着继续读取下一个字段 field...

Varints 编码

上一节中多次提到 Varints 编码,现在我们来正式介绍这种编码方案。

总结的讲,Varints 编码的规则主要为以下三点: 
在每个字节开头的 bit 设置了 msb(most significant bit ),标识是否需要继续读取下一个字节存储数字对应的二进制补码补码的低位排在前面

先来看一个最为简单的例子:
int32 val = 1; // 设置一个 int32 的字段的值 val = 1; 这时编码的结果如下
原码:0000 ... 0000 0001 // 1 的原码表示
补码:0000 ... 0000 0001 // 1 的补码表示
Varints 编码:0#000 0001(0x01) // 1 的 Varints 编码,其中第一个字节的 msb = 0
编码过程:
数字 1 对应补码 0000 ... 0000 0001(规则 2),从末端开始取每 7 位一组并且反转排序(规则 3),因为 0000 ... 0000 0001 除了第一个取出的 7 位组(即原数列的后 7 位),剩下的均为 0。所以只需取第一个 7 位组,无需再取下一个 7 bit,那么第一个 7 位组的 msb = 0。最终得到0 | 000 0001(0x01) 解码过程:

我们再做一遍解码过程,加深理解。

编码结果为 0#000 0001(0x01)。首先,每个字节的第一个 bit 为 msb 位,msb = 1 表示需要再读一个字节(还未结束),msb = 0 表示无需再读字节(读取到此为止)。

在上面的例子中,数字 1 的 Varints 编码中 msb = 0,所以只需要读完第一个字节无需再读。去掉 msb 之后,剩下的 000 0001 就是补码的逆序,但是这里只有一个字节,所以无需反转,直接解释补码 000 0001,还原即为数字 1。

注意:这里编码数字 1,Varints 只使用了 1 个字节。而正常情况下 int32 将使用 4 个字节存储数字 1。


再看一个需要两个字节的数字 666 的编码:nt32 val = 666; // 设置一个 int32 的字段的值 val = 666; 这时编码的结果如下
原码:000 ... 101 0011010 // 666 的源码
补码:000 ... 101 0011010 // 666 的补码
Varints 编码:1#0011010 0#000 0101 (9a 05) // 666 的 Varints 编码编码过程:
666 的补码为 000 ... 101 0011010,从后依次向前取 7 位组并反转排序,则得到:
0011010 | 0000101加上 msb,则1 0011010 | 0 0000101 (0x9a 0x05)
解码过程:
编码结果为 1#0011010 0#000 0101 (9a 05),与第一个例子类似,但是这里的第一个字节 msb = 1,所以需要再读一个字节,第二个字节的 msb = 0,则读取两个字节后停止。读到两个字节后先去掉两个 msb,剩下:0011010 000 0101将这两个 7-bit 组反转得到补码:
000 0101 0011010然后还原其原码为 666。

注意:这里编码数字 6,Varints 只使用了 2 个字节。而正常情况下 int32 将使用 4 个字节存储数字 666。

 
仔细品味上述的 Varints 编码,我们可以发现 Varints 的本质实际上是每个字节都牺牲一个 bit 位(msb),来表示是否已经结束(是否还需要读取下一个字节),msb 实际上就起到了 Length 的作用,正因为有了 msb(Length),所以我们可以摆脱原来那种无论数字大小都必须分配四个字节的窘境。通过 Varints 我们可以让小的数字用更少的字节表示。从而提高了空间利用和效率。

这里为什么强调牺牲?因为每个字节都拿出一个 bit 做 msb,而原先这个 bit 是可直接用来表示 Value 的,现在每个字节都少了一个 bit 位即只有 7 位能真正用来表达 Value。那就意味这 4 个字节能表达的最大数字为 2的28次 ,而不再是  2的32次  了。
这意味着什么?意味着当数字大于  2的28次  时,采用 Varints 编码将导致分配 5 个字节,而原先明明只需要 4 个字节,此时 Varints 编码的效率不仅不是提高反而是下降。
但这并不影响 Varints 在实际应用时的高效,因为事实证明,在大多数情况下,小于 2的28次 的数字比大于 2的28次 的数字出现的更为频繁。


到目前为止,好像一切都很完美。但是当前的 Varints 编码却存在着明显缺陷。我们的例子好像只给出了正数,我们来看一下负数的 Varints 编码情况。int32 val = -1
原码:1000 ... 0001 // 注意这里是 8 个字节
补码:1111 ... 1111 // 注意这里是 8 个字节
再次复习 Varints 编码:对补码取 7 bit 一组,低位放在前面。
上述补码 8 个字节共 64 bit,可分 9 组且这 9 组均为 1,这 9 组的 msb 均为 1(因为还有最后一组)
最后剩下一个 bit 的 1,用 0 补齐作为最后一组放在最后,最后得到 Varints 编码
Varints 编码:1#1111111 ... 0#000 0001 (FF FF FF FF FF FF FF FF FF 01)
注意,因为负数必须在最高位(符号位)置 1,这一点意味着无论如何,负数都必须占用所有字节,所以它的补码总是占满 8 个字节。你没法像正数那样去掉多余的高位(都是 0)。再加上 msb,最终 Varints 编码的结果将固定在 10 个字节。

为什么是十个字节? int32 不应该是 4 个字节吗?这里是 ProtoBuf 基于兼容性的考虑(比如开发者将 int64 的字段改成 int32 后应当不影响旧程序),而将 int32 扩展成 int64 的八个字节。
为什么之前讲正数的时候没有这种扩展?。请仔细品味 Varints 编码,正数的前提下 int32 和 int64 天然兼容!


所以目前的情况是我们定义了一个 int32 类型的变量,如果将变量值设置为负数,那么直接采用 Varints 编码的话,其编码结果将总是占用十个字节,这显然不是我们希望得到的结果。如何解决?

ZigZag 编码

在上一节中我们提到了 Varints 编码对负数编码效率低的问题。

为解决这个问题,ProtoBuf 为我们提供了 sint32、sint64 两种类型,当你在使用这两种类型定义字段时,ProtoBuf 将使用 ZigZag 编码,而 ZigZag 编码将解决负数编码效率低的问题。

ZigZag 的原理和概念比我们想象的简单易懂,一句话就可概括介绍 ZigZag 编码:
 

ZigZag 编码:有符号整数映射到无符号整数,然后再使用 Varints 编码


如下图所示:






对于 ZigZag 编码的思维不难理解,既然负数的 Varints 编码效率很低,那么就将负数映射到正数,然后对映射后的正数进行 Varints 编码。解码时,解出正数之后再按映射关系映射回原来的负数。

例如我们设置 int32 val = -2。映射得到 3,那么对数字 3 进行 Varints 编码,将结果存储或发送出去。接收方接到数据后进行 Varints 解码,得到数字 3,再将 3 映射回 -2。
 

这里的“映射”是以移位实现的,并非存储映射表。

 Varint 类型

介绍了 Varints 编码和 ZigZag 编码之后,我们就可以继续深入分析每个类型的编码。

在第一节中我们提到了 wire_type 目前已定义 6 种,其中两种已被遗弃(Start group 和 End group),只剩下四种类型: Varint、64-bit、Length-delimited、32-bit。

接下来我们就来一个个详细分析,彻底搞明白 ProtoBuf 针对每种类型的编码策略。

注意,我们在之前已经强调过,与其它三种类型不同,Varint 类型里不止一种编码策略。 除了 int32、int64 等类型的 Varints 编码,还有 sint32、sint64 类型的 ZigZag 编码。

int32、int64、uint32、uint64、bool、enum

当我们使用 int32、int64、uint32、uint64、bool、enum 声明字段类型时,其字段值将使用之前介绍的 Varints 编码。
 

其中 bool 的本质为 0 和 1,enum 本质为整数常量。


在结合本文开头介绍的编码结构: Tag - [Length] - Value,这里的 Value 采用 Varints 编码,因此不需要 Length,则编码结构为 Tag - Value,其中 Tag 和 Value 均采用 Vartins 编码。

int32、int64、uint32、uint64

来看一个最简单的 int32 的小例子:
 
syntax = "proto3";

// message 定义
message Example1 {
int32 int32Val = 1;
}

// 设置字段值 为 1
Example1 example1;
example1.set_int32val(1);
// 编码结果
tag-(Varints)0#0001 000 + value-(Varints)0#000 0001 = 0x08 0x01

// 设置字段值 为 666
Example1 example1;
example1.set_int32val(666);
// 编码结果
tag-(Varints)00001 000 + value-(Varints)1#0011010 0#000 0101 = 0x08 0x9a 0x05

// 设置字段值 为 1
Example1 example1;
example1.set_int32val(-1);
// 编码结果
tag-(Varints)00001 000 + value-(Varints)1#1111111 ... 0#000 0001 = 0x08 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0x01int64、uint32、uint64 与 int32 同理。
 
bool、enum

bool 的例子:
syntax = "proto3";

// message 定义
message Example1 {
bool boolVal = 1;
}

// 设置字段值 为 true
Example1 example1;
example1.set_boolval(true);

// 编码结果
tag-(Varints)00001 000 + value-(Varints)0#000 0001 = 08 01

// 设置字段值 为 false
Example1 example1;
example1.set_boolval(false);

// 编码结果

 

这里有个有意思的现象,当 boolVal = false 时,其编码结果为空,为什么?
这里是 ProtoBuf 为了提高效率做的又一个小技巧:规定一个默认值机制,当读出来的字段为空的时候就设置字段的值为默认值。而 bool 类型的默认值为 false。也就是说将 false 编码然后传递(消耗一个字节),不如直接不输出任何编码结果(空),终端解析时发现该字段为空,它会按照规定设置其值为默认值(也就是 false)。如此,可进一步节省空间提高效率。


enum 的例子:syntax = "proto3";

// message 定义
message Example1 {
enum COLOR {
YELLOW = 0;
RED = 1;
BLACK = 2;
WHITE = 3;
BLUE = 4;
}
// 枚举常量必须在 32 位整型值的范围
// 使用 Varints 编码,对负数不够高效,因此不推荐在枚举中使用负数
COLOR colorVal = 1;
}

// 设置字段值 为 Example1_COLOR_BLUE
Example1 example1;
example1.set_colorval(Example1_COLOR_BLUE);

// 编码结果
tag-(Varints)00001 000 + value-(Varints)0#000 0100 = 08 04sint32、sint64

sint32、sint64 将采用 ZigZag 编码。编码结构依然为 Tag - Value,只不过在编码和解码的过程中多出一个映射的过程,映射后依然采用 Varints 编码。
来看 sint32 的例子:syntax = "proto3";

// message 定义
message Example1 {
sint32 sint32Val = 1;
}

// 设置字段值 为 -1
Example1 example1;
example1.set_colorval(-1);

// 编码结果,1 映射回 -1
tag-(Varints)00001 000 + value-(Varints)0#000 0001 = 08 01

// 设置字段值 为 -2
Example1 example1;
example1.set_colorval(-2);

// 编码结果,3 映射回 -2
编码结果:tag-(Varints)00001 000 + value-(Varints)0#000 0011 = 08 03
sint64 与 sint32 同理。

int、uint 和 sint: 之所以同时出现了这三种类型,是因为历史和代码迭代的结果。ProtoBuf 最初只有 int 类型,由于 int 类型不适合负数(负数编码效率低),所以提供了 sint。因为 sint 的一部分正数其实是表达的负数,所以其正数范围有所减小,所以在一些全是正数场景下需要提供 uint 类型。

64-bit 和 32-bit 类型

64-bit 和 32-bit 比较简单,与 Varints 一样其编码结构为 Tag-Value,不同的是不管数字大小,64-bit 存储 8 字节,32-bit 存储 4 字节。读取时同理,64-bit 直接读取 8 字节,32-bit 直接读取 4 字节。

为什么需要 64-bit 和 32-bit?之前已经分析过了 Varints 编码在一定范围内是有高效的,超过某一个数字占用字节反而更多,效率更低。如果现在有场景是存在大量的大数字,那么使用 Varints 就不太合适了,此时使用 64-bit 和 32-bit 更为合适。具体的,如果数值比 256 大的话,64-bit 这个类型比 uint64 高效,如果数值比 228 大的话,32-bit 这个类型比 uint32 高效。

fixed64、sfixed64、double

来看例子:// message 定义
syntax = "proto3";

message Example1 {
fixed64 fixed64Val = 1;
sfixed64 sfixed64Val = 2;
double doubleVal = 3;
}

// 设置字段值 为 -2
example1.set_fixed64val(1)
example1.set_sfixed64val(-1)
example1.set_doubleval(1.2)

// 编码结果,总是 8 个字节
09 # 01 00 00 00 00 00 00 00
11 # FF FF FF FF FF FF FF FF (没有 ZigZag 编码)
19 # 33 33 33 33 33 33 F3 3Ffixed32、sfixed32、float

与 64-bit 同理。

Length-delimited 类型
string、bytes、EmbeddedMessage、repeated

终于遇到了体现编码结构图中 [Length] 意义的类型了。Length-delimited 类型的编码结构为 Tag - Length - Value

这种编码方式很好理解,来看例子:syntax = "proto3";

// message 定义
message Example1 {
string stringVal = 1;
bytes bytesVal = 2;
message EmbeddedMessage {
int32 int32Val = 1;
string stringVal = 2;
}
EmbeddedMessage embeddedExample1 = 3;
repeated int32 repeatedInt32Val = 4;
repeated string repeatedStringVal = 5;
}

//设置相应值
Example1 example1;
example1.set_stringval("hello,world");
example1.set_bytesval("are you ok?");

Example1_EmbeddedMessage *embeddedExample2 = new Example1_EmbeddedMessage();

embeddedExample2->set_int32val(1);
embeddedExample2->set_stringval("embeddedInfo");
example1.set_allocated_embeddedexample1(embeddedExample2);

example1.add_repeatedint32val(2);
example1.add_repeatedint32val(3);
example1.add_repeatedstringval("repeated1");
example1.add_repeatedstringval("repeated2");

//编码结果
0A 0B 68 65 6C 6C 6F 2C 77 6F 72 6C 64
12 0B 61 72 65 20 79 6F 75 20 6F 6B 3F
1A 10 08 01 12 0C 65 6D 62 65 64 64 65 64 49 6E 66 6F
22 02 02 03[ proto3 默认 packed = true](编码结果打包处理,见下一小节的介绍)
2A 09 72 65 70 65 61 74 65 64 31 2A 09 72 65 70 65 61 74 65 64 32(repeated string 为啥不进行默认 packed ?)读者可对照上面介绍过的编码来理解这段相对复杂的编码结果。(为降低难度,已按字段分行,即第一个字段的编码结果对应第一行,第二个字段对应第二行...)

补充 packed 编码

在 proto2 中为我们提供了可选的设置 [packed = true],而这一可选项在 proto3 中已成默认设置。
 

packed 目前只能用于 primitive 类型。


packed = true 主要使让 ProtoBuf 为我们把 repeated primitive 的编码结果打包,从而进一步压缩空间,进一步提高效率、速度。这里打包的含义其实就是:原先的 repeated 字段的编码结构为 Tag-Length-Value-Tag-Length-Value-Tag-Length-Value...,因为这些 Tag 都是相同的(同一字段),因此可以将这些字段的 Value 打包,即将编码结构变为 Tag-Length-Value-Value-Value...

上一节例子中 repeatedInt32Val 字段的编码结果为:22 | 02 02 03
22 即 00100010 -> wire_type = 2(Length-delimited), field_number = 4(repeatedInt32Val 字段),02 字节长度为 2,则读取两个字节,之后按照 Varints 解码出数字 2 和 3。

原文出处:
作者:404_89_117_101
链接:https://www.jianshu.com/p/73c9ed3a4877
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 查看全部
上一篇《序列化结构数据方法ProtoBuf初探》是对ProtoBuf的简单介绍和特点对比。接下来这篇主要总结的是ProtoBuf的编码方式。
 
编码结构

TLV 格式是我们比较熟悉的编码格式。
 


所谓的 TLV 即 Tag - Length - Value。Tag 作为该字段的唯一标识,Length 代表 Value 数据域的长度,最后的 Value 并是数据本身。



ProtoBuf 编码采用类似的结构,但是实际上又有较大区别,其编码结构可见下图:

QQ截图20200413160739.jpg


我们来一步步解析上图所表达的编码结构。

首先,每一个 message 进行编码,其结果由一个个字段组成,每个字段可划分为 Tag - [Length] - Value,如下图所示:

QQ截图20200413160948.jpg

 


特别注意这里的 [Length] 是可选的,含义是针对不同类型的数据编码结构可能会变成 Tag - Value 的形式,如果变成这样的形式,没有了 Length 我们该如何确定 Value 的边界?答案就是 Varint 编码,在后面将详细介绍。



继续深入 Tag ,Tag 由 field_number 和 wire_type 两个部分组成: 
  • field_number: message 定义字段时指定的字段编号
  • wire_type: ProtoBuf 编码类型,根据这个类型选择不同的 Value 编码方案。


整个 Tag 采用 Varints 编码方案进行编码,Varints 编码会在后面详细介绍。

Tag 结构如下图所示:

QQ截图20200413161046.jpg


3 bit 的 wire_type 最多可以表达 8 种编码类型,目前 ProtoBuf 已经定义了 6 种,如下图所示:

QQ截图20200413161115.jpg


第一列即是对应的类型编号,第二列为面向最终编码的编码类型,第三列是面向开发者的 message 字段的类型。
 


注意其中的 Start group 和 End group 两种类型已被遗弃。


 
 


另外要特别注意一点,虽然 wire_type 代表编码类型,但是 Varint 这个编码类型里针对 sint32、sint64 又会有一些特别编码(ZigTag 编码)处理,相当于 Varint 这个编码类型里又存在两种不同编码。



重新来看完整的编码结构图,现在我们可以理解一个 message 编码将由一个个的 field 组成,每个 field 根据类型将有如下两种格式:
 
  • Tag - Length - Value:编码类型表中 Type = 2 即 Length-delimited 编码类型将使用这种结构,
  • Tag - Value:编码类型表中 Varint、64-bit、32-bit 使用这种结构。



其中 Tag 由字段编号 field_number 和 编码类型 wire_type 组成, Tag 整体采用 Varints 编码。

现在来模拟一下,我们接收到了一串序列化的二进制数据,我们先读一个 Varints 编码块,进行 Varints 解码,读取最后 3 bit 得到 wire_type(由此可知是后面的 Value 采用的哪种编码),随后获取到 field_number (由此可知是哪一个字段)。依据 wire_type 来正确读取后面的 Value。接着继续读取下一个字段 field...

Varints 编码

上一节中多次提到 Varints 编码,现在我们来正式介绍这种编码方案。

总结的讲,Varints 编码的规则主要为以下三点: 
  1. 在每个字节开头的 bit 设置了 msb(most significant bit ),标识是否需要继续读取下一个字节
  2. 存储数字对应的二进制补码
  3. 补码的低位排在前面


先来看一个最为简单的例子:
int32 val =  1;  // 设置一个 int32 的字段的值 val = 1; 这时编码的结果如下
原码:0000 ... 0000 0001 // 1 的原码表示
补码:0000 ... 0000 0001 // 1 的补码表示
Varints 编码:0#000 0001(0x01) // 1 的 Varints 编码,其中第一个字节的 msb = 0

编码过程:
数字 1 对应补码 0000 ... 0000 0001(规则 2),从末端开始取每 7 位一组并且反转排序(规则 3),因为 0000 ... 0000 0001 除了第一个取出的 7 位组(即原数列的后 7 位),剩下的均为 0。所以只需取第一个 7 位组,无需再取下一个 7 bit,那么第一个 7 位组的 msb = 0。最终得到
0 | 000 0001(0x01) 
解码过程:

我们再做一遍解码过程,加深理解。

编码结果为 0#000 0001(0x01)。首先,每个字节的第一个 bit 为 msb 位,msb = 1 表示需要再读一个字节(还未结束),msb = 0 表示无需再读字节(读取到此为止)。

在上面的例子中,数字 1 的 Varints 编码中 msb = 0,所以只需要读完第一个字节无需再读。去掉 msb 之后,剩下的 000 0001 就是补码的逆序,但是这里只有一个字节,所以无需反转,直接解释补码 000 0001,还原即为数字 1。


注意:这里编码数字 1,Varints 只使用了 1 个字节。而正常情况下 int32 将使用 4 个字节存储数字 1。



再看一个需要两个字节的数字 666 的编码:
nt32 val = 666; // 设置一个 int32 的字段的值 val = 666; 这时编码的结果如下
原码:000 ... 101 0011010 // 666 的源码
补码:000 ... 101 0011010 // 666 的补码
Varints 编码:1#0011010 0#000 0101 (9a 05) // 666 的 Varints 编码
编码过程:
666 的补码为 000 ... 101 0011010,从后依次向前取 7 位组并反转排序,则得到:
0011010 | 0000101
加上 msb,则
1 0011010 | 0 0000101 (0x9a 0x05)

解码过程:
编码结果为 1#0011010 0#000 0101 (9a 05),与第一个例子类似,但是这里的第一个字节 msb = 1,所以需要再读一个字节,第二个字节的 msb = 0,则读取两个字节后停止。读到两个字节后先去掉两个 msb,剩下:
0011010  000 0101
将这两个 7-bit 组反转得到补码:
000 0101 0011010
然后还原其原码为 666。


注意:这里编码数字 6,Varints 只使用了 2 个字节。而正常情况下 int32 将使用 4 个字节存储数字 666。


 
仔细品味上述的 Varints 编码,我们可以发现 Varints 的本质实际上是每个字节都牺牲一个 bit 位(msb),来表示是否已经结束(是否还需要读取下一个字节),msb 实际上就起到了 Length 的作用,正因为有了 msb(Length),所以我们可以摆脱原来那种无论数字大小都必须分配四个字节的窘境。通过 Varints 我们可以让小的数字用更少的字节表示。从而提高了空间利用和效率


这里为什么强调牺牲?因为每个字节都拿出一个 bit 做 msb,而原先这个 bit 是可直接用来表示 Value 的,现在每个字节都少了一个 bit 位即只有 7 位能真正用来表达 Value。那就意味这 4 个字节能表达的最大数字为 2的28次 ,而不再是  2的32次  了。
这意味着什么?意味着当数字大于  2的28次  时,采用 Varints 编码将导致分配 5 个字节,而原先明明只需要 4 个字节,此时 Varints 编码的效率不仅不是提高反而是下降。
但这并不影响 Varints 在实际应用时的高效,因为事实证明,在大多数情况下,小于 2的28次 的数字比大于 2的28次 的数字出现的更为频繁。



到目前为止,好像一切都很完美。但是当前的 Varints 编码却存在着明显缺陷。我们的例子好像只给出了正数,我们来看一下负数的 Varints 编码情况。
int32 val = -1
原码:1000 ... 0001 // 注意这里是 8 个字节
补码:1111 ... 1111 // 注意这里是 8 个字节
再次复习 Varints 编码:对补码取 7 bit 一组,低位放在前面。
上述补码 8 个字节共 64 bit,可分 9 组且这 9 组均为 1,这 9 组的 msb 均为 1(因为还有最后一组)
最后剩下一个 bit 的 1,用 0 补齐作为最后一组放在最后,最后得到 Varints 编码
Varints 编码:1#1111111 ... 0#000 0001 (FF FF FF FF FF FF FF FF FF 01)

注意,因为负数必须在最高位(符号位)置 1,这一点意味着无论如何,负数都必须占用所有字节,所以它的补码总是占满 8 个字节。你没法像正数那样去掉多余的高位(都是 0)。再加上 msb,最终 Varints 编码的结果将固定在 10 个字节。


为什么是十个字节? int32 不应该是 4 个字节吗?这里是 ProtoBuf 基于兼容性的考虑(比如开发者将 int64 的字段改成 int32 后应当不影响旧程序),而将 int32 扩展成 int64 的八个字节。
为什么之前讲正数的时候没有这种扩展?。请仔细品味 Varints 编码,正数的前提下 int32 和 int64 天然兼容!



所以目前的情况是我们定义了一个 int32 类型的变量,如果将变量值设置为负数,那么直接采用 Varints 编码的话,其编码结果将总是占用十个字节,这显然不是我们希望得到的结果。如何解决?

ZigZag 编码

在上一节中我们提到了 Varints 编码对负数编码效率低的问题。

为解决这个问题,ProtoBuf 为我们提供了 sint32、sint64 两种类型,当你在使用这两种类型定义字段时,ProtoBuf 将使用 ZigZag 编码,而 ZigZag 编码将解决负数编码效率低的问题。

ZigZag 的原理和概念比我们想象的简单易懂,一句话就可概括介绍 ZigZag 编码:
 


ZigZag 编码:有符号整数映射到无符号整数,然后再使用 Varints 编码



如下图所示:

QQ截图20200413161656.jpg


对于 ZigZag 编码的思维不难理解,既然负数的 Varints 编码效率很低,那么就将负数映射到正数,然后对映射后的正数进行 Varints 编码。解码时,解出正数之后再按映射关系映射回原来的负数。

例如我们设置 int32 val = -2。映射得到 3,那么对数字 3 进行 Varints 编码,将结果存储或发送出去。接收方接到数据后进行 Varints 解码,得到数字 3,再将 3 映射回 -2。
 


这里的“映射”是以移位实现的,并非存储映射表。


 Varint 类型

介绍了 Varints 编码和 ZigZag 编码之后,我们就可以继续深入分析每个类型的编码。

在第一节中我们提到了 wire_type 目前已定义 6 种,其中两种已被遗弃(Start group 和 End group),只剩下四种类型: Varint、64-bit、Length-delimited、32-bit

接下来我们就来一个个详细分析,彻底搞明白 ProtoBuf 针对每种类型的编码策略。

注意,我们在之前已经强调过,与其它三种类型不同,Varint 类型里不止一种编码策略。 除了 int32、int64 等类型的 Varints 编码,还有 sint32、sint64 类型的 ZigZag 编码。

int32、int64、uint32、uint64、bool、enum

当我们使用 int32、int64、uint32、uint64、bool、enum 声明字段类型时,其字段值将使用之前介绍的 Varints 编码。
 


其中 bool 的本质为 0 和 1,enum 本质为整数常量。



在结合本文开头介绍的编码结构: Tag - [Length] - Value,这里的 Value 采用 Varints 编码,因此不需要 Length,则编码结构为 Tag - Value,其中 Tag 和 Value 均采用 Vartins 编码。

int32、int64、uint32、uint64

来看一个最简单的 int32 的小例子:
 
syntax = "proto3";

// message 定义
message Example1 {
int32 int32Val = 1;
}

// 设置字段值 为 1
Example1 example1;
example1.set_int32val(1);
// 编码结果
tag-(Varints)0#0001 000 + value-(Varints)0#000 0001 = 0x08 0x01

// 设置字段值 为 666
Example1 example1;
example1.set_int32val(666);
// 编码结果
tag-(Varints)00001 000 + value-(Varints)1#0011010 0#000 0101 = 0x08 0x9a 0x05

// 设置字段值 为 1
Example1 example1;
example1.set_int32val(-1);
// 编码结果
tag-(Varints)00001 000 + value-(Varints)1#1111111 ... 0#000 0001 = 0x08 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0x01
int64、uint32、uint64 与 int32 同理。
 
bool、enum

bool 的例子:
syntax = "proto3";

// message 定义
message Example1 {
bool boolVal = 1;
}

// 设置字段值 为 true
Example1 example1;
example1.set_boolval(true);

// 编码结果
tag-(Varints)00001 000 + value-(Varints)0#000 0001 = 08 01

// 设置字段值 为 false
Example1 example1;
example1.set_boolval(false);

// 编码结果

 


这里有个有意思的现象,当 boolVal = false 时,其编码结果为空,为什么?
这里是 ProtoBuf 为了提高效率做的又一个小技巧:规定一个默认值机制,当读出来的字段为空的时候就设置字段的值为默认值。而 bool 类型的默认值为 false。也就是说将 false 编码然后传递(消耗一个字节),不如直接不输出任何编码结果(空),终端解析时发现该字段为空,它会按照规定设置其值为默认值(也就是 false)。如此,可进一步节省空间提高效率。



enum 的例子:
syntax = "proto3";

// message 定义
message Example1 {
enum COLOR {
YELLOW = 0;
RED = 1;
BLACK = 2;
WHITE = 3;
BLUE = 4;
}
// 枚举常量必须在 32 位整型值的范围
// 使用 Varints 编码,对负数不够高效,因此不推荐在枚举中使用负数
COLOR colorVal = 1;
}

// 设置字段值 为 Example1_COLOR_BLUE
Example1 example1;
example1.set_colorval(Example1_COLOR_BLUE);

// 编码结果
tag-(Varints)00001 000 + value-(Varints)0#000 0100 = 08 04
sint32、sint64

sint32、sint64 将采用 ZigZag 编码。编码结构依然为 Tag - Value,只不过在编码和解码的过程中多出一个映射的过程,映射后依然采用 Varints 编码。
来看 sint32 的例子:
syntax = "proto3";

// message 定义
message Example1 {
sint32 sint32Val = 1;
}

// 设置字段值 为 -1
Example1 example1;
example1.set_colorval(-1);

// 编码结果,1 映射回 -1
tag-(Varints)00001 000 + value-(Varints)0#000 0001 = 08 01

// 设置字段值 为 -2
Example1 example1;
example1.set_colorval(-2);

// 编码结果,3 映射回 -2
编码结果:tag-(Varints)00001 000 + value-(Varints)0#000 0011 = 08 03
sint64 与 sint32 同理。


int、uint 和 sint: 之所以同时出现了这三种类型,是因为历史和代码迭代的结果。ProtoBuf 最初只有 int 类型,由于 int 类型不适合负数(负数编码效率低),所以提供了 sint。因为 sint 的一部分正数其实是表达的负数,所以其正数范围有所减小,所以在一些全是正数场景下需要提供 uint 类型。


64-bit 和 32-bit 类型

64-bit 和 32-bit 比较简单,与 Varints 一样其编码结构为 Tag-Value,不同的是不管数字大小,64-bit 存储 8 字节,32-bit 存储 4 字节。读取时同理,64-bit 直接读取 8 字节,32-bit 直接读取 4 字节。

为什么需要 64-bit 和 32-bit?之前已经分析过了 Varints 编码在一定范围内是有高效的,超过某一个数字占用字节反而更多,效率更低。如果现在有场景是存在大量的大数字,那么使用 Varints 就不太合适了,此时使用 64-bit 和 32-bit 更为合适。具体的,如果数值比 256 大的话,64-bit 这个类型比 uint64 高效,如果数值比 228 大的话,32-bit 这个类型比 uint32 高效。

fixed64、sfixed64、double

来看例子:
// message 定义
syntax = "proto3";

message Example1 {
fixed64 fixed64Val = 1;
sfixed64 sfixed64Val = 2;
double doubleVal = 3;
}

// 设置字段值 为 -2
example1.set_fixed64val(1)
example1.set_sfixed64val(-1)
example1.set_doubleval(1.2)

// 编码结果,总是 8 个字节
09 # 01 00 00 00 00 00 00 00
11 # FF FF FF FF FF FF FF FF (没有 ZigZag 编码)
19 # 33 33 33 33 33 33 F3 3F
fixed32、sfixed32、float

与 64-bit 同理。

Length-delimited 类型
string、bytes、EmbeddedMessage、repeated

终于遇到了体现编码结构图中 [Length] 意义的类型了。Length-delimited 类型的编码结构为 Tag - Length - Value

这种编码方式很好理解,来看例子:
syntax = "proto3";

// message 定义
message Example1 {
string stringVal = 1;
bytes bytesVal = 2;
message EmbeddedMessage {
int32 int32Val = 1;
string stringVal = 2;
}
EmbeddedMessage embeddedExample1 = 3;
repeated int32 repeatedInt32Val = 4;
repeated string repeatedStringVal = 5;
}

//设置相应值
Example1 example1;
example1.set_stringval("hello,world");
example1.set_bytesval("are you ok?");

Example1_EmbeddedMessage *embeddedExample2 = new Example1_EmbeddedMessage();

embeddedExample2->set_int32val(1);
embeddedExample2->set_stringval("embeddedInfo");
example1.set_allocated_embeddedexample1(embeddedExample2);

example1.add_repeatedint32val(2);
example1.add_repeatedint32val(3);
example1.add_repeatedstringval("repeated1");
example1.add_repeatedstringval("repeated2");

//编码结果
0A 0B 68 65 6C 6C 6F 2C 77 6F 72 6C 64
12 0B 61 72 65 20 79 6F 75 20 6F 6B 3F
1A 10 08 01 12 0C 65 6D 62 65 64 64 65 64 49 6E 66 6F
22 02 02 03[ proto3 默认 packed = true](编码结果打包处理,见下一小节的介绍)
2A 09 72 65 70 65 61 74 65 64 31 2A 09 72 65 70 65 61 74 65 64 32(repeated string 为啥不进行默认 packed ?)
读者可对照上面介绍过的编码来理解这段相对复杂的编码结果。(为降低难度,已按字段分行,即第一个字段的编码结果对应第一行,第二个字段对应第二行...)

补充 packed 编码

在 proto2 中为我们提供了可选的设置 [packed = true],而这一可选项在 proto3 中已成默认设置。
 


packed 目前只能用于 primitive 类型。



packed = true 主要使让 ProtoBuf 为我们把 repeated primitive 的编码结果打包,从而进一步压缩空间,进一步提高效率、速度。这里打包的含义其实就是:原先的 repeated 字段的编码结构为 Tag-Length-Value-Tag-Length-Value-Tag-Length-Value...,因为这些 Tag 都是相同的(同一字段),因此可以将这些字段的 Value 打包,即将编码结构变为 Tag-Length-Value-Value-Value...

上一节例子中 repeatedInt32Val 字段的编码结果为:
22 | 02 02 03

22 即 00100010 -> wire_type = 2(Length-delimited), field_number = 4(repeatedInt32Val 字段),02 字节长度为 2,则读取两个字节,之后按照 Varints 解码出数字 2 和 3。

原文出处:
作者:404_89_117_101
链接:https://www.jianshu.com/p/73c9ed3a4877
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。