4.5 实战演练——Ordered Map
我们已经知道,字典类型的值有一个共同特点,即其中的元素值的迭代顺序是不确定的。但是在一些应用场景下,我们是需要固定的元素迭代顺序的。
我们在前面的章节中多次提到过,如果要使元素可排序就需要让数据类型实现sort.Interface
接口类型。该接口类型中的方法Len
、Less
和Swap
的含义分别是获取元素的数量、比较相邻元素的大小以及交换它们的位置。我们在基于数组类型或切片类型的自定义数据类型之上可以非常轻松地实现这几个方法。但是,对于基于字典类型的扩展数据类型来说,实现它们可就不那么容易了。因为字典类型值中的元素值是无序的。我们没有任何方法可以确定它们的位置以及与它们相邻的元素值。
因此,要想自定义一个有序字典类型,仅基于Go语言的字典类型是不可能实现的。我们应该使用一个元素有序的数据类型值作为辅助。依据这一思路,我声明了一个名为OrderedMap
的结构体类型:
type OrderedMap struct {
keys []interface{}
m map[interface{}]interface{}
}
可以看到,该类型的基本结构中,除了一个字典类型的字段,还有一个切片类型的字段。为了让OrderedMap
类型实现sort.Interface
接口类型,我们需要为它添加如下几个方法:
func (omap *OrderedMap) Len() int {
return len(omap.keys)
}
func (omap *OrderedMap) Less(i, j int) bool {
// 省略若干条语句
}
func (omap *OrderedMap) Swap(i, j int) {
omap.keys[i], omap.keys[j] = omap.keys[j], omap.keys[i]
}
这样,*OrderedMap
类型(注意,不是OrderedMap
类型)就是一个sort.Interface
接口类型的实现类型了。可以看到,我们在这些方法中操作的实际上都是OrderedMap
类型中的字段keys
的值。在Len
方法中,我们以keys
字段的值的长度作为结果值。而在Swap
方法中,我们使用平行赋值语句交换的两个元素值也都是在keys
字段的值中的。这就意味着,我们会使用字段keys
的值的元素迭代顺序全权代表字段m
的值的元素迭代顺序。
为了达到这个目的,我们就必须要在添加和删除字段m
的值中的键值对的时候对字段keys
的值进行完全同步的操作。在编写相关方法之前,我们先来关注一下刚刚提到却被省略实现的Less
方法。
方法Less
的功能是比较相邻的两个元素值的大小并返回判断结果。我们在上一章讲值的可比性与有序性的时候介绍过各种数据类型值的比较方法。已知,只有当值的类型具备有序性的时候,它才可能与其他的同类型值比较大小。Go语言规定,字典类型的键类型的值必须是可比的(即可判定两个该类型的值是否相等)。然而,在具有可比性的数据类型中只有一部分同时具备有序性。也就是说,我们只依靠Go语言本身对字典类型的键类型的约束是不够的。在Go语言中,具备有序性的预定义数据类型只有整数类型、浮点数类型和字符串类型。
类型OrderedMap
中的字段keys
是[]interface{}类型的。也就是说,我们总是需要比较两个interface{}
类型值的大小。这显然是不可行的,因为接口类型的值只具有可比性而不具备有序性。所以,我们刚才声明的OrderedMap
类型是不可用的。如果把keys
字段的元素类型改为某一个具体的数据类型(整数类型、浮点数类型或字符串类型),虽然可以轻松编写出比较各个元素值大小的代码,但是这样做却会使OrderedMap
类型的应用价值大打折扣。
总之,我们还需要重新审视一下将要创建的这个类型。
首先,我们先要对OrderedMap
类型的主要功能需求进行收集和整理。实际上,这些需求都集中在对字段keys
的值的操作上,如下所示。
字段
keys
的值中的元素值应该都是有序的。我们应该可以方便地比较它们之间的大小。字段
keys
的值的元素类型不应该是一个具体的类型。我们应该可以在运行时再确定它的元素类型。我们应该可以方便地对字段
keys
的值进行添加元素值、删除元素值以及获取元素值等操作,就像对待一个普通的切片值那样。字段
keys
的值中的元素值应该可以被依照固定的顺序获取。字段
keys
的值中的元素值应该能够被自动地排序。由于字段
keys
的值中的元素值总是已排序的,所以我们应该能够确定某一个元素值的具体位置。既然我们可以在运行时决定字段
keys
的值的元素类型,那么也应该可以在运行时获知这个元素类型。我们应该可以在运行时获取到被用于比较
keys
的值中的不同元素值的大小的具体方法。
根据上面这些需求,我们有了这样一个接口类型声明:
type Keys interface {
sort.Interface
Add(k interface{}) bool
Remove(k interface{}) bool
Clear()
Get(index int) interface{}
GetAll() []interface{}
Search(k interface{}) (index int, contains bool)
ElemType() reflect.Type
CompareFunc() func(interface{}, interface{}) int8
}
在Keys
接口类型中嵌入sort.Interface
接口类型,就意味着Keys
类型的值一定是可排序的。Add
、Remove
、Clear
和Get
这4个方法使得我们可以对Keys
的值进行添加、删除、清除和获取元素值的操作。GetAll
方法让我们可以获取到一个与Keys
类型值有着相同的元素值集合和元素迭代顺序的切片值。Search
、ElemType
和CompareFunc
方法分别体现了需求列表中第6项、第7项和第8项所描述的功能。其中,ElemType
方法返回一个reflect.Type
类型的结果值。我们在之前提到过reflect
代码包,但是并没有对它进行说明。实际上,reflect
包中的程序实体为我们提供了Go语言运行时的反射机制。通过它们,我们可以编写出一些代码来动态的操纵任意类型的对象。比如,其中TypeOf
函数用于获取一个interface{}
类型的值的动态类型信息。在本小节,我们会展示它的用法。
细心的读者可能会发现,在Keys
接口类型的声明中并没有体现出需求列表中的第1、2、5项所描述的功能。不用着急,我们会在Keys
接口类型的实现类型中实现它们。既然Keys
接口类型的值必是sort.Interface
接口的一个实现,那么我们使用sort
代码包中的程序实体应该不难实现元素自动排序的功能。因此,我们编码的重点就落在了实现第1项和第2项中的功能上。
为了能够动态地决定元素类型,我们不得不在这个Keys
的实现类型中声明一个[]interface{}类型的字段,以作为存储被添加到Keys
类型值中的元素值的底层数据结构:
container []interface{}
由于Go语言本身并没有对自定义泛型的提供支持,所以只有这样我们才能够用这个字段的值存储某一个数据类型的元素值。但是,我们前面提到的那个问题又出现了——接口类型的值不具备有序性,不可能比较它们的大小。不过,也许把这个问题抛出去并让使用这个Keys
的实现类型的编程人员来解决它是一个可行的方案。因为他们应该知道添加到Keys
类型值中的元素值的实际类型并知道应该怎样比较它们。所以,我们还应该有这样的一个字段:
compareFunc func(interface{}, interface{}) int8
这是一个函数类型的字段。就像我们刚才说的,Keys
的实现的使用者应该知道需要对作为该函数参数的那两个元素值进行怎样的类型转换以及怎样比较它们。这个函数返回一个int8
类型的结果值。我们在这里做出如下规定。
当第一个参数值小于第二个参数值时,结果值应该小于0。
当第一个参数值大于第二个参数值时,结果值应该大于0。
当第一个参数值等于第二个参数值时,结果值应该等于0。
现在,通过把比较两个元素值大小的问题抛给使用者,我们既解决了需要动态确定元素类型的问题,又明确了比较两个元素值大小的解决方式。不过还有一个问题,由于container
字段是[]interface{}类型的,所以我们常常不能够很方便地在运行时获取到它的实际元素类型(比如在它的值中还没有任何元素值的时候)。因此,我们还需要一个明确container
字段的实际元素类型的字段。这个字段的值所代表的类型也应该是当前的Keys
类型值的实际元素类型。
综上所述,这个Keys
接口类型的实现类型的声明应该是这样的:
type myKeys struct {
container []interface{}
compareFunc func(interface{}, interface{}) int8
elemType reflect.Type
}
其中compareFunc
和elemType
字段的值应该是相对应的。比如,如果我们想使用一个*myKeys
类型的值来存储int64
类型的元素值,那么我就应该这样来初始化它:
int64Keys := &myKeys{
container: make([]interface{}, 0),
compareFunc: func(e1 interface{}, e2 interface{}) int8 {
k1 := e1.(int64)
k2 := e2.(int64)
if k1 < k2 {
return -1
} else if k1 > k2 {
return 1
} else {
return 0
}
},
elemType: reflect.TypeOf(int64(1))}
注意,compareFunc
字段的值中的那两个类型断言表达式的目标类型一定要与elemType
字段的值所代表的类型保持一致。在这里,elemType
字段的值所代表的类型其实就是调用reflect.TypeOf
函数时传入的那个参数值的类型,即int64
。这与前面在e1
和e2
上应用的类型断言表达式中的类型字面量是相对应的。只有存在这样的对应关系才能够保证在对变量int64Keys
的使用过程中不会出现问题。我们会在编写myKeys
类型的方法的过程中逐渐体现出如此设计的真正含义。
我们已经在前面的内容中多次讲过怎样实现sort.Interface
接口类型中的那几个方法。不过,在这里,由于元素值之间的比较方法是由int64Keys
的值的创建者确定的,所以其中的Less
方法的实现会稍有不同。这些被用于实现sort.Interface
接口类型的方法的声明如下:
func (keys *myKeys) Len() int {
return len(keys.container)
}
func (keys *myKeys) Less(i, j int) bool {
return keys.compareFunc(keys.container[i], keys.container[j]) == -1
}
func (keys *myKeys) Swap(i, j int) {
keys.container[i], keys.container[j] = keys.container[j], keys.container[i]
}
在Less
方法中,我们把比较两个元素值的操作全权交给了compareFunc
字段所代表的那个函数(以下简称compareFunc
函数)。如果当前值是按照我们上面所说的正确的方式来初始化的话,那么这种比较方式应该总是有效的。另外,请注意,这3个方法的接收者类型都是myKeys
,所以实现sort.Interface
接口类型的类型是myKeys
而不是myKeys
。
现在我们来看Add
方法怎样实现。在真正向字段container
的值添加元素值之前,我们应该先判断这个元素值的类型是否符合要求。这需要使用到字段elemType
的值,因为它代表了可接受的元素值的类型。由于我们在很多地方都会用到这种判断,所以我们应该把实现这一功能的代码独立为一个方法,像这样:
func (keys *myKeys) isAcceptableElem(k interface{}) bool {
if k == nil {
return false
}
if reflect.TypeOf(k) != keys.elemType {
return false
}
return true
}
因为Add
方法的参数的类型是interface{}
类型的,所以isAcceptableElem
方法的参数类型也应该是interface{}
的。我们先使用reflect.TypeOf
函数确定参数k
的实际类型,再让它与当前值的elemType
字段的值进行比较。由于reflect.Type
是一个接口类型,所以我们使用比较操作符!=
来判定它们的相等性是合法的。
在Add
方法中,我们首先使用isAcceptableElem
方法来判定元素值的类型是否可被接收。如果结果是否定的,那么我们就直接返回false
。如果结果是肯定的,那么我们就向container
字段的值添加这个元素值。在添加之后,我们应该对container
的值中的元素值进行一次排序。这需要用到sort
代码包中的排序函数sort.Sort
。sort.Sort
函数的声明是这样的:
func Sort(data Interface) {
// 省略若干条语句
}
函数sort.Sort
的签名中的参数类型Interface
其实就是接口类型sort.Interface
。由于这两个程序实体处在同一个代码包中,所以在该参数类型的名称中并不用加入所属代码包名称和“.”(也就是限定前缀)。
值得一提的是,sort.Sort
函数使用的排序算法是一种由三向切分的快速排序算法、堆排序算法和插入排序算法组成的混合算法。虽然快速排序是最快的通用排序算法,但在元素值很少的情况下它比插入排序要慢一些。而堆排序的空间复杂度是常数级别的,且它的时间复杂度在大多数情况下只略逊于其他两种排序算法。所以在快速排序中的递归达到一定深度的时候,切换至堆排序来节约空间是值得的。
这样的算法组合使得sort.Sort
函数的时间复杂度在最坏的情况下是O(N*logN)
的,并且能够有效地控制对空间的使用。但是,请注意,它并不提供稳定性的保证。稳定性是指在排序过程中能够保留数组(这里是切片值)中重复元素的相对位置。如果我们对稳定性没有特殊要求,那么选用sort.Sort
函数提供的排序算法往往是最佳选择。
我们在这里选择使用sort.Sort
函数对Add
方法的接收者值(实际上是字段container
的值)中的元素值进行排序是在算法特性和代码量之间进行权衡的结果。如果我们在使用过程中发现它的某些方面(时间复杂度、空间复杂度、稳定性等)并没有满足要求,也可以使用其他排序算法(组合)来替换对sort.Sort
函数。
另一方面,由于*myKeys
类型是sort.Interface
接口类型的一个实现类型,所以我们可以直接使用Add
方法的接收者值来作为sort.Sort
的参数值。
按照上面的描述和分析,我们编写出了Add方法的声明:
func (keys *myKeys) Add(k interface{}) bool {
ok := keys.isAcceptableElem(k)
if !ok {
return false
}
keys.container = append(keys.container, k)
sort.Sort(keys)
return true
}
正是有了isAcceptableElem
方法的保证,我们才能够放心大胆地使用sort.Sort
函数对当前值进行排序。sort.Sort
函数会通过对keys
的值的Len
、Less
和Swap
方法的调用来完成排序。而在Less
方法中,我们是通过那个compareFunc
函数对相邻的元素值进行比较的。
这样一来,我们就真正地把elemType
和compareFunc
函数间接地关联了起来。换句话说,如果一个值能够通过isAcceptableElem
方法的检查并被添加到container
的值当中,那么这个元素值就肯定能够在compareFunc
函数中被正确地比较。因此,我们在初始化myKeys
类型值的时候,就必须保证这两个字段的值在类型设定方面的一致性。否则,在我们比较两个元素值的过程中就会引发运行时恐慌。
我们在从container
中删除一个指定元素值之前先要找到它所处的位置。所以,我们在实现Remove
方法之前先来看看Search
方法应该怎样编写。在Search
方法中,我们要搜索参数k
代表的值在container
中对应的索引值。由于k
的类型是interface{}
的,所以我们同样需要先使用isAcceptableElem
方法对它进行判定。如果结果是否定的,我们就在把该方法的结果声明中的contains
赋值为false
之后直接返回。如果结果是肯定的,那么我就需要在container
中搜索该元素值。我们可以通过调用sort.Search
函数来实现搜索元素值的核心逻辑。sort.Search
函数的声明如下:
func Search(n int, f func(int) bool) int {
// 省略若干条语句
}
由于sort.Search
函数使用二分查找算法在切片值中搜索指定的元素值。这种搜索算法有着稳定的O(logN)
的时间复杂度,但它要求被搜索的数组(这里是切片值)必须是有序的。因此,我们必须确保container
字段的值中的元素值是已被排过序的。幸好我们在添加元素值的时候保证了这一点。
从上面的声明可知,sort.Search
函数有两个参数。第一个参数接受的应该是欲排序的切片值的长度,而第二个参数接受的是一个函数值。这个函数值的含义是:对于一个给定的索引值,判定与之对应的元素值是否等于欲查找的元素值或者应该排在欲查找的元素值的右边。由此,参数f
的值应该是这样的:
func(i int) bool { return keys.compareFunc(keys.container[i], k) >= 0 }
与Less
方法相同,我们在这里也是通过compareFunc
函数对两个元素值进行比较的。
这个参数f
的值到底意味着什么呢?假设我们有这样一个切片值:
[]int{1, 3, 5, 7, 9, 11, 13, 15}
且要查找的元素值是7
。依据二分查找算法,sort.Search
函数内部会在第三次折半的时候使用7
的索引值3
作为函数f
的参数值。这时,函数f
的结果值应该是true
。同时,由于已经没有可以被折半的目标子序列了,所以sort.Search
函数的执行会结束并返回7
的索引值3
作为它的结果值。显然,这个结果值对应的元素值就是我们要查找的。
另一种情况,我们要查找的元素值根本就不在这个切片值里,比如是6
或8
。这时,sort.Search
函数的执行也会在f(3)
被求值之后结束,且它的结果值会是4
或3
。但是,这两个结果值对应的元素值都不是我们要查找的。
总之,sort.Search
函数的结果值总会在[0, n]的范围内,但结果值并不一定就是欲查找的元素值所对应的索引值。因此,我们还需要在得到调用sort.Search
函数的结果值之后再进行一次判断。代码如下:
if index < keys.Len() && keys.container[index] == k {
contains = true
}
其中index
代表了sort.Search
函数的结果值。我们需要先检查结果值是否在有效的索引范围之内,然后还要判断它所对应的元素值是否就是我们要查找的。
经过前面这一系列的分析,相信读者已经能够自己实现*myKeys
类型的Search
函数了。现在就把它编写出来吧。
等这个函数被实现之后,我们再来看Remove
函数。首先,我们需要调用*myKeys
类型的Search
函数,以获取欲删除的元素值对应的索引值和它是否被包含在container
中的判断结果。如果第二个结果值是false
,那么就直接忽略剩余的操作并直接返回false
,否则就从container
中删除掉这个元素值。从切片值中删除一个元素值有很多种方式,比如使用for
语句、copy
函数或append
函数,等等。我们在这里选择用append
函数来实现,因为它可以在不增加时间复杂度和空间复杂度的情况下使用更少的代码来完成功能,且不降低可读性。下面这行代码实现了删除一个元素值的功能:
keys.container = append(keys.container[0:index], keys.container[index+1:]...)
这行代码充分地使用了切片表达式和append
函数。首先,我们使用切片表达式
keys.container[0:index]
和
keys.container[index+1:]
分别把container
字段的值中的、在预删除元素值之前和之后的子元素序列提取出来。然后,我们再把这两个元素子序列拼接起来。还记得吗?append
是一个可变参函数。所以,我们可以在第二个参数值之后添加“…”以表示把第二个参数值中的每个元素值都作为传给append
函数的独立参数。这样,我们就把第二个子序列中的所有元素值逐个追加到了第一个子序列的尾部。最后,我们把拼接后的元素序列赋值给了container
字段。
根据上面的描述,请读者自行编写出Remove
函数。
通过在上一小节中对HashSet
类型的实现,我们已经了解了Clear
方法的编写手法。其声明如下:
func (keys *myKeys) Clear() {
keys.container = make([]interface{}, 0)
}
又由于container
字段本身就是切片类型的,所以Get
方法也是相当好实现的。它的声明如下:
func (keys *myKeys) Get(index int) interface{} {
if index >= keys.Len() {
return nil
}
return keys.container[index]
}
方法GetAll
的编写方式与*HashSet
类型的Elements
方法基本一致。唯一要注意的地方就是切片值的第一个迭代变量(左边的)代表了元素值的索引值,而第二个迭代变量(右边的)才代表了元素值本身。GetAll
方法的声明如下:
func (keys *myKeys) GetAll() []interface{} {
initialLen := len(keys.container)
snapshot := make([]interface{}, initialLen)
actualLen := 0
for _, key := range keys.container {
if actualLen < initialLen {
snapshot[actualLen] = key
} else {
snapshot = append(snapshot, key)
}
actualLen++
}
if actualLen < initialLen {
snapshot = snapshot[:actualLen]
}
return snapshot
}
至于ElemType
和CompareFunc
方法的实现就更不用多说了,我们直接把字段elemType
和compareFunc
字段的值分别作为它们的结果值就可以了:
func (keys *myKeys) ElemType() reflect.Type {
return keys.elemType
}
func (keys *myKeys) CompareFunc() CompareFunction {
return keys.compareFunc
}
作为一个可选的方法,String
方法被用于生成可读性更好的接收者值的字符串表示形式。读者可以仿照*HashSet
类型的String
方法完成这一方法的编写。
至此,我们已经完成了myKeys
类型以及相关方法的编写。不过按照Go
语言的惯例,我们还应该编写一个用于初始化*myKeys
类型值的函数。由于当前只有一个Keys
接口类型的实现,所以我们就把这个函数定名为NewKeys
,并把它的结果的类型设定为Keys
。下面就是这个函数的声明:
func NewKeys(
compareFunc func(interface{}, interface{}) int8,
elemType reflect.Type) Keys {
return &myKeys{
container: make([]interface{}, 0),
compareFunc: compareFunc,
elemType: elemType,
}
}
可以看到,在NewKeys
函数的参数声明列表中没有与container
字段相对应的参数声明。原因是container
字段的值总应该是一个长度为0的[]interface{}类型值。因此它不必由NewKeys
函数的调用方提供。另外,NewKeys
函数的compareFunc
参数和elemType
参数之间的关系,也应该满足我们在讲怎样初始化myKeys
类型值的时候所提及的约束条件。最后,由于只有myKeys
类型的方法集合中才包含了Keys
接口类型中声明的所有方法,所以在NewKeys
函数中返回的是一个myKeys
类型值,而不是一个myKeys
类型值。
好了,我们已经编写完成了OrderedMap
类型所需要用到的最核心的数据类型Keys
和myKeys
。并且,在这个过程中,我们不仅对Go语言的很多基础知识进行了复习,还了解到了一些与元素排序和运行时反射有关的知识。下面,我们再回过头来看OrderedMap
类型。
由于有了Keys
接口类型,OrderedMap
类型的声明被修改为:
type myOrderedMap struct {
keys Keys
elemType reflect.Type
m map[interface{}]interface{}
}
是的,我们更改了该类型的名称,这是因为我们要声明一个接口类型来描述有序字典类型所提供的功能。OrderedMap
更适合作为这个接口类型的名称。OrderedMap
接口类型的声明如下:
type OrderedMap interface {
// 获取给定键值对应的元素值。若没有对应元素值则返回nil。
Get(key interface{}) interface{}
// 添加键值对,并返回与给定键值对应的旧的元素值。若没有旧元素值则返回(nil, true)。
Put(key interface{}, elem interface{}) (interface{}, bool)
// 删除与给定键值对应的键值对,并返回旧的元素值。若没有旧元素值则返回nil。
Remove(key interface{}) interface{}
// 清除所有的键值对
Clear()
// 获取键值对的数量
Len() int
// 判断是否包含给定的键值
Contains(key interface{}) bool
// 获取第一个键值。若无任何键值对则返回nil。
FirstKey() interface{}
// 获取最后一个键值。若无任何键值对则返回nil。
LastKey() interface{}
// 获取由小于键值toKey的键值所对应的键值对组成的OrderedMap类型值。
HeadMap(toKey interface{}) OrderedMap
// 获取由小于键值toKey且大于等于键值fromKey的键值所对应的键值对组成的OrderedMap类型值。
SubMap(fromKey interface{}, toKey interface{}) OrderedMap
// 获取由大于等于键值fromKey的键值所对应的键值对组成的OrderedMap类型值。
TailMap(fromKey interface{}) OrderedMap
// 获取已排序的键值所组成的切片值
Keys() []interface{}
// 获取已排序的元素值所组成的切片值
Elems() []interface{}
// 获取已排序的键值对所组成的字典值
ToMap() map[interface{}]interface{}
// 获取键的类型
KeyType() reflect.Type
// 获取元素的类型
ElemType() reflect.Type
}
我们要使myOrderedMap
类型成为OrderedMap
接口类型的实现类型。虽然OrderedMap
接口类型中的方法声明很多,但是有了之前编写HashSet
类型和myKeys
类型的经验,我们实现myOrderedMap
类型的这些方法应该难度不大。读者能试着把这些方法的完整声明编写出来吗?请记得再编写一个NewOrderedMap
函数,并把初始化好的myOrderedMap
类型值作为结果值返回。
别担心,完整的myOrderedMap
类型以及相关方法的声明连同本小节所提及的所有代码都被放到了goc2p项目的basic/omap
代码包中。在必要时读者可以把它们作为参考。但是,千万不要只动眼不动手。
另外,有些读者可能会认为,这样实现出来的有序字典类型的时间复杂度和空间复杂度都比较高。当然,我们也可以使用基于B树(及其衍生数据结构)或跳跃表来实现有序字典类型。在通过这两个小节的复习和训练之后,读者应该在Go语言基础语法的运用上已经基本没有什么障碍了。那么读者是否可以试着使用Go语言来实现更高效的有序字典类型呢?