关于golang:对比Python学习Go-高级数据结构

本篇是「比照 Python 学习 Go」系列的第四篇，本篇文章咱们来看下 Go 的高级数据结构，因文章偏长分为两篇，此为上篇。本系列的其余文章可到「比照 Python 学习 Go」- 开篇 查看，上面咱们开始明天的分享。

Python 数据结构底层齐全依赖解释器的实现形式，没有非凡说明文中数据结构对应默认解释器 CPython。

从数据结构上来讲，有「数组」和「链表」两种根本的数据结构，还有很多基于他们的高级数据结构如栈、队列、散列表等等。作为编程语言，Go 和 Python 是如何定义本人的数据结构的呢？依据数据结构的个性，咱们大抵能够将 Go 和 Python 的数据结构分如下几个类型：

• 「类数组的构造」，具备数组的一些个性，但不齐全是数组。
• 「哈希类型」，即 key-value 类型或叫 map 类型。
• 语言本人特有的一些高级构造。

下边咱们来逐个介绍。

类数组构造

数组，它是一个线性表的构造。它有如下个性：

• 应用一组 间断 的内存空间来存储数据。
• 存储的数据具备 雷同类型。

回顾了数组的个性，咱们来看下 Go 和 Python 中有哪些类数组的数据结构。

Go

在 Go 语言中，有「数组」和「切片」两个类数组数据结构。

数组

Go 的数组个性可总结如下：

• 固定长度：这意味着数组不可增长、不可缩减。想要扩大数组，只能创立新数组，将原数组的元素复制到新数组。
• 内存间断 ：这意味着能够通过下标的形式(arr[index]) 索引数组中的元素。
• 固定类型：固定类型意味着限度了每个数组元素能够寄存什么样的数据，以及每个元素能够寄存多少字节的数据。

数组的初始化和操作如下：

 
package main
 
import "fmt"
 
func main() {// 类型 [n]T 是一个有 n 个类型为 T 的值的数组
    // 先申明，后赋值
    var a [2]string
    a[0] = "Hello"
    a[1] = "World"
 
    // 申明时，间接赋值
    b := [5]int{10,20,30,40,50}
 
    // 可间接通过下标来拜访数组
    fmt.Println(a)
    fmt.Println(a[0], a[1])
    fmt.Println(b)
    fmt.Println(b[1], b[2])
 
    // 通过 len()函数可获取数组长度
    fmt.Println(len(a))
    fmt.Println(len(b))
 
    // 数组元素赋值
    b[1] = 25
    fmt.Println(b)
    fmt.Println(b[1])
 
}

除了一般数组之外，还有多维数组，即数组的数组。

// 申明一个二维整型数组，两个维度别离存储 4 个元素和 2 个元素
var arr [4][2]int
arr[0] = [2]int{10, 11}
arr[0][1] = 15
 
// 申明时，间接赋值
arr1 := [4][2]int{{10, 11}, {20, 21}, {30, 31}, {40, 41}}
 
// 申明时，应用下标赋值
arr2 := [4][2]int{1: {20, 21}, 3: {40, 41}}
arr3 := [4][2]int{1: {0: 20}, 3: {1: 41}}
 
// 应用数组类初始化数组
var arr4 [2]int = arr1[1]
// 应用数组元素来赋值一般元素
var value int = arr1[1][0]
 
// 应用索引获取数组值
fmt.Println(arr)
fmt.Println(arr1)
fmt.Println(arr1[0][1])
fmt.Println(arr2)
fmt.Println(arr3)
fmt.Println(arr4)
fmt.Println(value)
 
// [[10 15] [0 0] [0 0] [0 0]]
// [10 15]
// [[10 11] [20 21] [30 31] [40 41]]
// 11
// [[0 0] [20 21] [0 0] [40 41]]
// [[0 0] [20 0] [0 0] [0 41]]
// [20 21]
// 20

数组中未被初始化的元素，会主动初始化为各类型对应的「零值」。

切片

Go 的数组长度是固定的，内存空间中存储了数据值，当存储的量特地大的时候，应用起来极不不便。在 Go 语言中，除了数组还定义了一个类数组构造，叫做「切片（slice）」。

切片是数组段的描述符。它由一个指向底层 数组的指针 ，数组段 长度 及其 容量（段的最大长度）组成。切片更像是数组的援用类型，而数组则是值类型。其构造如下：

在 Go 的编程中，因为数组的各种局限性，对数据汇合类型的操作解决时，切片是首选的数据结构。切片的底层数据存储还是数组，所以数组的一些个性切片也有。

// 切片应用 make(slice, len, cap) 申明, cap 可省略，省略时，等于 len
sli := make([]int, 2, 3)
fmt.Println(sli)  // 未赋值时，各元素为对应的零值
fmt.Printf("%p %v %v \n", sli, len(sli), cap(sli))
 
// 申明时，初始化
nums := []int{10, 20, 30, 40}
fmt.Println(nums)
fmt.Printf("%p %v %v \n", nums, len(nums), cap(nums))
 
// nil 切片，指针为空，长度和容量为 0
var nums1 []int
fmt.Println(nums1)
 
// 空切片，指针为指向一个空数组，长度和容量为 0
var nums2 = make([]int, 0)
nums3 := []int{}
fmt.Println(nums2)
fmt.Println(nums3)
 
nums[0] = 12
fmt.Println(nums)
 
// 从切片创立切片
fmt.Println(nums)
fmt.Println(nums[1:2]) // 长度为 2 -1 =1，容量 1
fmt.Println(nums[1:2:4]) // 长度为 2 -1=1，容量为 4 -1=3
//slice[i:]  // 从 i 切到最尾部
//slice[:j]  // 从最结尾切到 j(不蕴含 j)
//slice[:]   // 从头切到尾，等价于复制整个 slice
 
// 切片的追加, 应用内建函数 append(src, item) 返回 新的切片
nums = append(nums, 10) // 增加一个
nums = append(nums, 10, 20) // 同时增加多个
newNums := append(nums, nums1...)  // 合并两个切片
fmt.Println(newNums)
fmt.Println(nums)
 
// 切片的复制, 应用内建函数 copy(dst, src) 返回复制的元素个数
// 赋值时，接管的切片容量须要大于原切片，否则复制失败，且不会报错
copyNums := make([]int, 5)
count := copy(copyNums, nums)
fmt.Println(count)
fmt.Println(copyNums)
fmt.Println(nums)

下面说到，Go 的切片归根接地是一个数据段的描述符。底层是援用的数组构造，当多个切片同时援用一个数组时，应用下标来批改切片，则会互相的影响，应用时，肯定要留神。

// 数组共享的切片
sli := make([]int, 3)  // 定义一个长度，大小都为 3 的切片
sli1 := sli[:2]  // 由切片再创立切片，sli 和 sli1 底层援用同一个数组
// slice: 0xc0000160c0 ,len: 3 ,cap: 3
fmt.Printf("slice: %p ,len: %v ,cap: %v \n", sli, len(sli), cap(sli))
// slice1: 0xc0000160c0 ,len: 2 ,cap: 3
fmt.Printf("slice1: %p ,len: %v ,cap: %v \n", sli1, len(sli1), cap(sli1))
 
 
sli[0] = 10
fmt.Println(sli)   // [10 0 0]
fmt.Println(sli1)  // [10 0]

切片的容量，可在应用中动静增长。切片的动静增长是通过内置函数 append() 来实现的，它会主动的解决好切片扩缩容的所有细节。扩容长度通常是原来切片容量的一倍，当容量大于 1024 时，增长变为原来容量的 1/4 倍。

// 切片扩容
fmt.Printf("%p %v %v \n", sli, len(sli), cap(sli)) // 0xc0000160c0 3 3
sli = append(sli, 1)
sli = append(sli, 2)
fmt.Println(sli)  // [10 0 0 1 2]
fmt.Printf("%p %v %v \n", sli, len(sli), cap(sli)) // 0xc00001a0c0 5 6

上边代码中 sli 长度为 3，容量为 3。append 元素之后，因为容量曾经被占满，所以主动扩容了一倍的容量，通过两次 append 之后，长度变为 5，容量为 6。除了长度和容量外，大家可能发现了，数组地址变了，这阐明 append 函数在扩容的时候，会创立一个新的底层数组，而并非在原数组上进行间接追加扩容。

append 函数扩容创立新数组，这时候再通过下标来批改数据或继续执行 append 是不会笼罩原底层数组的，因为曾经不是一个数组了。这个特点常常被用在从一个切片创立另一个切片时，避免切片赋值相互影响。

sli := make([]int, 3)  // 定义一个长度，大小都为 3 的切片
fmt.Println(sli)  // [0 0 0]
sli1 := sli[:3:3]  // sli1 长度 3 -0=3，容量为 3 -0=3
fmt.Println(sli1)  // [0 0 0]
fmt.Printf("%p %v %v \n", sli, len(sli), cap(sli))  // 0xc0000160c0 3 3
fmt.Printf("%p %v %v \n", sli1, len(sli1), cap(sli1))  // 0xc0000160c0 3 3
sli1 = append(sli1, 2)  // 容量已满，新创建底层数组
fmt.Printf("%p %v %v \n", sli1, len(sli1), cap(sli1))  // 0xc00001a0c0 4 6

Python

Python 中的类数组数据结构，为列表（List）和元组（tuple）。

List

列表，与数组相比，更为高级，列表的底层构造如下：

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

抛去公共的头部变量 PyObject_VAR_HEAD，列表由一个指针数组ob_item，和一个容量allocated 组成。构造如下：

列表中，并未存储理论的数值，而是存储了数值的援用地址，援用地址能够指向任意类型的数据，也就能够了解为什么列表中能够有任意类型的元素了。另一个，列表中援用地址的大小雷同，保留在一个间断的存储空间，也就有了数组的一些个性，能够通过下标疾速定位。

依据列表底层构造和 Python 官网文档 How are lists implemented in CPython? 总结 List 有如下个性：

• 列表元素能够应用下标索引取值，各元素是有地位程序的，底层为间断的存储空间。
• 列表中存储的是数据的内存地址，并非实在数据。所以从下层构造看，list 列表能够存储任意类型，即列表元素中的内存地址能够是指向任意类型的。
• 能够任意增加新元素，要能一直地增加新元素，其应用了「动静裁减」的策略。扩容策略的增长倍数大抵是这样的：0, 4, 8, 16, 24, 32, 40, 52, 64, 76…，参考源码 listobject.c。

列表的初始化及操作如下：

# 列表的初始化
l1 = []  # 举荐，更疾速
l2 = list()
l3 = [1,2,3,4]
 
# 列表相加
print(l1+l2)
print(l1*2)  # 可应用 * 来复制列表
 
l3 += l1
print(l3)
 
# 列表取值
print(l1[2])
print(l3[1:2])  # 从下标 1 到下标 2
print(l3[1:])  # 到结尾
print(l3[:2])  # 从 0 开始
 
# 列表的长度
print(len(l1))
 
# 删除索引为 3 的元素
del l1[3]

Python 的列表作为内建的高级数据结构，实现了一系列的操作性能函数。

dir(list)
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__',
 '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__',
 '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__',
 '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__',
 '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__',
 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']
 
l1 = [1, 2, 3, 4, 5]
l2 = [6, 7, 8, 9, 10]
 
# 列表追加
l3 = l1.append(6)
 
# 列表合并
l4 = l1.extend(l2)
 
# 列表元素的索引
print(l1.index(2))  # 2 在 l1 列表中的索引
 
# 插入列表元素
print(l1)  # [1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10]
l1.insert(2, 12)  # 在索引为 2 的地位插入值 12，原值及后边的值后移。print(l1)  # [1, 2, 12, 3, 4, 5, 6, 6, 7, 8, 9, 10]
 
# 弹出列表指定索引的元素
num = l1.pop()  # 默认为最大索引
print(num)  # 10
print(l1)  # [1, 2, 12, 3, 4, 5, 6, 6, 7, 8, 9]
num = l1.pop(3)  # 弹出索引为 3 的元素，后边的元素前移
print(l1)  # [1, 2, 12, 4, 5, 6, 6, 7, 8, 9]
 
# 删除指定值的元素
print(l1)  # [1, 2, 12, 4, 5, 6, 6, 7, 8, 9]
l1.remove(2)  # 删除值为 2 的元素, 后边的元素前移
print(l1)  # [1, 12, 4, 5, 6, 6, 7, 8, 9]
 
# 清空列表
print(l1)  # [1, 12, 4, 5, 6, 6, 7, 8, 9]
l1.clear()  # 清空列表 l1
print(l1)  # []
 
# 列表排序
print(l2)  # [6, 7, 8, 9, 10]
l2.sort()
print(l2)  # [6, 7, 8, 9, 10]
l2.reverse()
print(l2)  # [6, 7, 8, 9, 10]

除了列表自带的一些操作，还实用一些内建的函数。

# sorted 排序函数
print(l2)
l21 = sorted(l2, key=lambda x: x, reverse=False)
print(l21)

元组

Python 中除了列表，还有元组比拟像数组。元组和列表类似，只是不能减少、删除、批改。底层构造如下：

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];
} PyTupleObject;

除了头字段，只有一个指针数组。没有想列表一样的容量字段allocated，这正映了元组的不可变个性。除了元素的不可变个性外，其余和列表一样，是列表类型的一个子集。

你可能会有这样的疑难，都有列表了，元组存在的意义在哪里？元组相比于列表，有以下几点劣势：

• 1. 因为元素不可变性，它能够作为哈希类型的 key 值。这样使的 key 的形容意义更丰盛，更易了解。
• 1. 对于元组，解释器会缓存一些小的动态变量应用的内存，这样在初始化时，就比列表快。

元组的初始化及罕用操作：

 
# 元组的初始化
a = (1, 2, 3)
b = ('1', [2, 3])
c = ('1', '2', (3, 4))
d = ()
e = (1,)  # 元组中只有一个元素时，须要应用逗号结尾
 
print(a, b, c, d, e)
# (1, 2, 3) ('1', [2, 3]) ('1', '2', (3, 4)) () (1,)
 
# 下标获取值
print(a[1])  # 2
 
# 元组合并
print(a+b)  # (1, 2, 3, '1', [2, 3])
 
# 内建函数应用
# 元组长度
print(len(a))  # 3
 
# 应用 * 是复制指针
f = a*2
print(f)  # (1, 2, 3, 1, 2, 3)
print(id(f[0]))  # 4376435920
print(id(a[0]))  # 4376435920
print(id(f[3]))  # 4376435920
 
 
# 无奈更新编辑
# a[0] = 1
# Traceback (most recent call last):
#   File "/Users/deanwu/projects/01_LearnDocs/learn_codes/python/python_list.py", line 15, in <module>
#     a[0] = 1
# TypeError: 'tuple' object does not support item assignment
 
# 无奈删除
# del a[0]
# Traceback (most recent call last):
#   File "/Users/deanwu/projects/01_LearnDocs/learn_codes/python/python_list.py", line 21, in <module>
#     del a[0]
# TypeError: 'tuple' object doesn't support item deletion

总结

本篇咱们我学习了 Go 和 Python 的高级数据结构中类数组的构造，它们都有一些数组的个性，但又都有本人语言的特点。Go 的切片和 Python 的列表，底层都基于数组，但 Go 的切片更像是数组的描述符指针，而 Python 的列表，则是应用地址和数据离开存储，援用地址应用间断空间存储，继承数组疾速查找的长处，内部存储实现任意类型元素存储。整体下来，甚是奇妙。

不论何种语言，咱们在应用时，既要理解构造的根本用法，还要理解其底层的逻辑构造，能力防止在应用时的一些莫名的坑。

扩大浏览

• Golang slice
• python 中的 list 类型
• CPython 中 list 的实现
• listobject.c

我是 DeanWu，一个致力成为真正 SRE 的人。

关注公众号「码农吴先生」, 可第一工夫获取最新文章。回复关键字「go」「python」获取我收集的学习材料，也可回复关键字「小二」，加我 wx 拉你进技术交换群，聊技术聊人生~