在日常写代码的实践中，我们经常用到的基础数据结构最多的就是 Slice（切片），但在 Go 的 API 中却存在另一个有趣的数据结构《链表》(container/list)，但什么时候用链表呢？当时我抱着怀疑的心态网上找了一下资源，有些说是“频繁的插入和删除用 list,频繁的遍历查询选 slice”，还有“随机插入和随机删除方面的性能比数组好得多”，到底哪个对呢？为此我做了一些测试来证明以上的说法是否正确，也正好可以加深对链表的使用。
电脑配置信息如下：
Go 版本为：go1.18.1 darwin/amd64
CPU：cpu: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
内存： 16GB
先验证频繁插入链表是否比 slice 快，测试代码如下：
func BenchmarkListAndSliceInsertA(b *testing.B) { b.ResetTimer() sliceList := make([]int, 0)
for j := 0; j < b.N; j++ { for i := 0; i < 10000; i++ { sliceList = append(sliceList, i) } }
b.StopTimer()}
func BenchmarkListAndSliceInsertB(b *testing.B) { b.ResetTimer() containerList := list.New() for j := 0; j < b.N; j++ { for i := 0; i < 10000; i++ { containerList.PushBack(i) } } b.StopTimer()}
复制代码
以上是对结构数据不断的添加，测试效果如下：
在 slice 频繁插入的过程中，Slice 还是比较有优势的
验证频繁删除是否比 Slice 快，测试代码如下：
func BenchmarkListAndSliceRemoveA(b *testing.B) { num := 100 sliceList := make([]int, 0) for i := 0; i < num; i++ { sliceList = append(sliceList, i) }
b.ResetTimer() for j := 0; j < b.N; j++ { a := sliceList[:] for i := 0; i < num; i++ { a = a[1:len(a)] } } b.StopTimer()}
func BenchmarkListAndSliceRemoveB(b *testing.B) { num := 100 containerList := list.New() for i := 0; i < num; i++ { containerList.PushFront(i) }
b.ResetTimer() for j := 0; j < b.N; j++ { copyContainerList := list.New() copyContainerList.PushBackList(containerList) var prev *list.Element for e := copyContainerList.Back(); e != nil; e = prev { prev = e.Prev() copyContainerList.Remove(e) } } b.StopTimer()}
复制代码
以上是对结构数据不断的复制删除元素，测试效果如下：
在 slice 频繁删除的过程中，也是 Slice 还是比较有优势的
既然随机我就拿索引来做随机数吧，测试代码如下：
func BenchmarkListAndSliceRandomIndexInsertA(b *testing.B) { num := 10000 sliceList := make([]int, 0) for i := 0; i < num; i++ { sliceList = append(sliceList, i) } b.ResetTimer() for j := 0; j < b.N; j++ { l := len(sliceList) rand.Seed(time.Now().UnixNano()) randNum := rand.Intn(l) // random index newSlice := make([]int, l+1) copy(newSlice, sliceList[:randNum]) newSlice[randNum] = randNum copy(newSlice[randNum+1:], sliceList[randNum:]) sliceList = newSlice }
b.StopTimer()}
func BenchmarkListAndSliceRandomIndexInsertB(b *testing.B) { num := 10000 containerList := list.New() for i := 0; i < num; i++ { containerList.PushBack(i) }
b.ResetTimer() for j := 0; j < b.N; j++ { l := containerList.Len() rand.Seed(time.Now().UnixNano()) randNum := rand.Intn(l) // random index
index := 0 for e := containerList.Front(); e != nil; e = e.Next() { if index == randNum { ef := containerList.PushBack(randNum) containerList.MoveBefore(ef, e) break } else { index += 1 } } } b.StopTimer()}
复制代码
测试结果如下：
链表内存分配更少，但性能还是 Slice 比较有优势
继续拿索引来做随机数，测试代码如下：
func BenchmarkListAndSliceRandomIndexRemoveA(b *testing.B) { num := 10000 sliceList := make([]int, 0) for i := 0; i < num; i++ { sliceList = append(sliceList, i) }
b.ResetTimer() for j := 0; j < b.N; j++ { a := sliceList[:]
for i := 0; i < num/2; i++ { l := len(a) rand.Seed(time.Now().UnixNano()) randNum := rand.Intn(l) // random index newSlice := make([]int, l-1) copy(newSlice, a[:randNum]) copy(newSlice[randNum:], a[randNum+1:]) a = newSlice }
} b.StopTimer()}
func BenchmarkListAndSliceRandomIndexRemoveB(b *testing.B) { num := 10000 containerList := list.New() for i := 0; i < num; i++ { containerList.PushBack(i) }
b.ResetTimer() for j := 0; j < b.N; j++ { copyContainerList := list.New() copyContainerList.PushBackList(containerList)
for i := 0; i < num/2; i++ { l := copyContainerList.Len() rand.Seed(time.Now().UnixNano()) randNum := rand.Intn(l) // random index
index := 0 for e := copyContainerList.Front(); e != nil; e = e.Next() { if index == randNum { copyContainerList.Remove(e) break } else { index += 1 } } } } b.StopTimer()}
复制代码
测试结果如下：
链表内存分配更少，但性能还是 Slice 比较有优势
根据以上的数据，明显是 Slice 比较有优势呀，那链表有什么用？
为了证明链表的用处，既然 GO 语言找不到了，那就找找别的编程语言呗，你别说还真给我找到：https://dzone.com/articles/performance-of-array-vs-linked-list-on-modern-comp
根据以上文章的描述，当链表中的元素大于 32bytes 并且执行随机插入或随机删除才是正真发挥威力的时候
在 go 语言中 int 类型是根据电脑的 CPU 位数决定，所以我直接用 int64 占用 8 个字节，一个结构体中包含 5 个 int64 就大于 32bytes 了，测试代码如下：
type IntBig struct { Num1 int64 Num2 int64 Num3 int64 Num4 int64 Num5 int64}
func BenchmarkListAndSliceBigInsertA(b *testing.B) { b.ResetTimer() sliceList := make([]IntBig, 0)
for j := 0; j < b.N; j++ { for i := 0; i < 1000; i++ { sliceList = append(sliceList, IntBig{ Num1: int64(i), Num2: int64(i), Num3: int64(i), Num4: int64(i), Num5: int64(i), }) } }
b.StopTimer()}
func BenchmarkListAndSliceBigInsertB(b *testing.B) { b.ResetTimer() containerList := list.New() for j := 0; j < b.N; j++ { for i := 0; i < 1000; i++ { containerList.PushBack(IntBig{ Num1: int64(i), Num2: int64(i), Num3: int64(i), Num4: int64(i), Num5: int64(i), }) } } b.StopTimer()}
复制代码
测试结果：
连续插入，Slice 还是比较有优势，因为非常容易命中 CPU 缓存
复用上面的结构体，测试代码如下：
type IntBig struct { Num1 int64 Num2 int64 Num3 int64 Num4 int64 Num5 int64}
func BenchmarkListAndSliceBigRandomIndexInsertA(b *testing.B) { num := 10000 sliceList := make([]IntBig, 0) for i := 0; i < num; i++ { sliceList = append(sliceList, IntBig{ Num1: int64(i), Num2: int64(i), Num3: int64(i), Num4: int64(i), Num5: int64(i), }) } b.ResetTimer() for j := 0; j < b.N; j++ { l := len(sliceList) rand.Seed(time.Now().UnixNano()) randNum := int64(rand.Intn(l)) // random index newSlice := make([]IntBig, l+1) copy(newSlice, sliceList[:randNum]) newSlice[randNum] = IntBig{ Num1: randNum, Num2: randNum, Num3: randNum, Num4: randNum, Num5: randNum, } copy(newSlice[randNum+1:], sliceList[randNum:]) sliceList = newSlice }
b.StopTimer()}
func BenchmarkListAndSliceBigRandomIndexInsertB(b *testing.B) { num := 10000 containerList := list.New() for i := 0; i < num; i++ { containerList.PushBack(IntBig{ Num1: int64(i), Num2: int64(i), Num3: int64(i), Num4: int64(i), Num5: int64(i), }) }
b.ResetTimer() for j := 0; j < b.N; j++ { l := containerList.Len() rand.Seed(time.Now().UnixNano()) randNum := int64(rand.Intn(l)) // random index
index := int64(0) for e := containerList.Front(); e != nil; e = e.Next() { if index == randNum { ef := containerList.PushBack(IntBig{ Num1: randNum, Num2: randNum, Num3: randNum, Num4: randNum, Num5: randNum, }) containerList.MoveBefore(ef, e) break } else { index += 1 } } } b.StopTimer()}
复制代码
测试结果：
哇~~，链表的优势终于出来了，当插入的数据越多，链表优势越明显，切片移动元素的成本增长通常高于链表缓存未命中的成本，那么链表会比数组有更好的性能。
*还有连续删除与随机删除这两个例子，有兴趣的同学可以自己实现一下
总结
根据以上的测试结果来看，当链表元素大于 32bytes 并且执行随机插入或随机删除才会使用，通常情况下还是可以用切片实现的。
如果对以上的测试与数据有误，欢迎同学下方留言纠正，谢谢
评论