Loading...
墨滴

盘胧

2021/08/19  阅读:31  主题:全栈蓝

golang-链/列表

container包中的那些容器

Go语言的链表实现在标准库的container/list代码包中。这个代码包中有两个公开的程序实体——ListElement,List 实现了一个双向链表(以下简称链表),而 Element 则代表了链表中元素的结构。

自定义Element类型值传给链表

看下LIST已经实现的内置方法

func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)

func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)
  • MoveBefore方法和MoveAfter方法,它们分别用于把给定的元素移动到另一个元素的前面后面

  • MoveToFront方法和MoveToBack方法,分别用于把给定的元素移动到链表的最前端最后端

“给定的元素”都是*Element类型的,*Element类型是Element类型的指针类型,*Element的值就是元素的指针

如果我们自己生成这样的值,然后把它作为“给定的元素”传给链表的方法,那么会发生什么?链表会接受它吗?

不能这样做。这些方法将不会对链表做出任何改动。因为我们自己生成的Element值并不在链表中,所以也就谈不上“在链表中移动元素”。更何况链表不允许我们把自己生成的Element值插入其中。

问题解析

List包含的方法中,用于插入新元素的那些方法都只接受interface{}类型的值。这些方法在内部会使用Element值,包装接收到的新元素

这样做正是为了避免直接使用我们自己生成的元素,主要原因是避免链表的内部关联,遭到外界破坏,这对于链表本身以及我们这些使用者来说都是有益的。

List的方法还有下面这几种:

  • Front和Back方法分别用于获取链表中最前端和最后端的元素
  • InsertBefore和InsertAfter方法分别用于在指定的元素之前和之后插入新元素
  • PushFront和PushBack方法则分别用于在链表的最前端和最后端插入新元素。

代码如下:

func (l *List) Front() *Element
func (l *List) Back() *Element

func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element

func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element

这些方法都会把一个Element值的指针作为结果返回,它们就是链表留给我们的安全“接口”。拿到这些内部元素的指针,我们就可以去调用前面提到的用于移动元素的方法了。

为什么链表可以做到开箱即用?

List和Element都是结构体类型。结构体类型有一个特点,那就是它们的零值都会是拥有特定结构,但是没有任何定制化内容的值,相当于一个空壳。值中的字段也都会被分别赋予各自类型的零值

广义来讲,所谓的零值就是只做了声明,但还未做初始化的变量被给予的缺省值。每个类型的零值都会依据该类型的特性而被设定。比如,经过语句var a [2]int声明的变量a的值,将会是一个包含了两个0的整数数组。又比如,经过语句var s []int声明的变量s的值将会是一个[]int类型的、值为nil的切片。

那么经过语句var l list.List声明的变量l的值将会是什么呢?[1] 这个零值将会是一个长度为0的链表。这个链表持有的根元素也将会是一个空壳,其中只会包含缺省的内容。那这样的链表我们可以直接拿来使用吗?

答案是,可以的。这被称为“开箱即用”。Go 语言标准库中很多结构体类型的程序实体都做到了开箱即用。这也是在编写可供别人使用的代码包(或者说程序库)时,我们推荐遵循的最佳实践之一。那么,语句var l list.List声明的链表l可以直接使用,这是怎么做到的呢?

关键在于它的“延迟初始化”机制。——还记得python的生成器,惰性加载么?

所谓的延迟初始化,你可以理解为把初始化操作延后,仅在实际需要的时候才进行。延迟初始化的优点在于“延后”,它可以分散初始化操作带来的计算量和存储空间消耗

例如,如果我们需要集中声明非常多的大容量切片的话,那么那时的 CPU 和内存空间的使用量肯定都会一个激增,并且只有设法让其中的切片及其底层数组被回收,内存使用量才会有所降低。

如果数组是可以被延迟初始化的,那么计算量和存储空间的压力就可以被分散到实际使用它们的时候。这些数组被实际使用的时间越分散,延迟初始化带来的优势就会越明显。

实际上,Go 语言的切片就起到了延迟初始化其底层数组的作用,你可以想一想为什么会这么说的理由。延迟初始化的缺点恰恰也在于“延后”。你可以想象一下,如果我在调用链表的每个方法的时候,它们都需要先去判断链表是否已经被初始化,那这也会是一个计算量上的浪费。在这些方法被非常频繁地调用的情况下,这种浪费的影响就开始显现了,程序的性能将会降低。

在这里的链表实现中,一些方法是无需对是否初始化做判断的。比如Front方法和Back方法,一旦发现链表的长度为0, 直接返回nil就好了。

又比如,在用于删除元素、移动元素,以及一些用于插入元素的方法中,只要判断一下传入的元素中指向所属链表的指针,是否与当前链表的指针相等就可以了。

如果不相等,就一定说明传入的元素不是这个链表中的,后续的操作就不用做了。反之,就一定说明这个链表已经被初始化了。

原因在于,链表的PushFront方法、PushBack方法、PushBackList方法以及PushFrontList方法总会先判断链表的状态,并在必要时进行初始化,这就是延迟初始化。

而且,我们在向一个空的链表中添加新元素的时候,肯定会调用这四个方法中的一个,这时新元素中指向所属链表的指针,一定会被设定为当前链表的指针。所以,指针相等是链表已经初始化的充分必要条件

明白了吗?List利用了自身以及Element在结构上的特点,巧妙地平衡了延迟初始化的优缺点,使得链表可以开箱即用,并且在性能上可以达到最优。

Ring与List的区别在哪儿?

container/ring包中的Ring类型实现的是一个循环链表,也就是我们俗称的环。其实List在内部就是一个循环链表。它的根元素永远不会持有任何实际的元素值,而该元素的存在就是为了连接这个循环链表的首尾两端

也可以说,List的零值是一个只包含了根元素,但不包含任何实际元素值的空链表。那么,既然Ring和List在本质上都是循环链表,那它们到底有什么不同呢?

  • Ring类型的数据结构仅由它自身即可代表,而List类型则需要由它以及Element类型联合表示。这是表示方式上的不同,也是结构复杂度上的不同。
  • 一个Ring类型的值严格来讲,只代表了其所属的循环链表中的一个元素,而一个List类型的值则代表了一个完整的链表。这是表示维度上的不同。--我们实现链表的时候,也是准备一个class Linlisk再准备一个class Node,返回一个node,其实返回的是一个Linklist对象
  • 在创建并初始化一个Ring值的时候,我们可以指定它包含的元素的数量,但是对于一个List值来说却不能这样做(也没有必要这样做)。循环链表一旦被创建,其长度是不可变的。这是两个代码包中的New函数在功能上的不同,也是两个类型在初始化值方面的第一个不同。
  • 仅通过var r ring.Ring语句声明的r将会是一个长度为1的循环链表,而List类型的零值则是一个长度为0的链表。别忘了List中的根元素不会持有实际元素值,因此计算长度时不会包含它。这是两个类型在初始化值方面的第二个不同。
  • Ring值的Len方法的算法复杂度是 O(N) 的,而List值的Len方法的算法复杂度则是 O(1) 的。这是两者在性能方面最显而易见的差别。

其他的不同基本上都是方法方面的了。比如,循环链表也有用于插入、移动或删除元素的方法,不过用起来都显得更抽象一些,等等。

总结

  • List的底层实现其实是一个带哨兵的链表结构,new出来的零值list,长度为1,len的复杂度为1,拥有链表和节点的概念
  • Ring初始化出来长度为0, 它只具有元素的概念

1. 为什么go语言会出现list这个包

首先一个语言或者新技术的出现肯定是为了解决一些疑难杂症 在go语言中数组的特点非常鲜明 固定不可变 访问方便,但是如果不适合动态增长,所以出现了slice切片 切片是对数组的一层封装为了解决数组动态扩容问题, 但是实际上底层依赖的还是数组,但是问题来了 如果slice切片 在添加或者删除元素的时候如果没一个好的策略 扩容或者缩容过后旧的切片没有释放 则会造成内存泄漏 就是c语言的malloc 久而久之 内存越来越少 程序就会崩溃, 而List的出现就是为了解决动态扩容或者缩容的后遗症 因为依赖指针这个东西 所以删除和增加都非常方便

2. 延迟初始化机制

延迟初始化机制 主要是为了解决像数组这种 声明的时候就分配了内存空间的问题,有的时候我们只需要声明,但还不需要使用它,这个时候没有必要分配内存空间,再如文中提到的 在同一时刻声明大量的内存空间的话 那么cpu的使用和内存空间的使用将会激增

所以我们需要延迟初始化机制(设计模式中的单例模式也提到了延迟初始化问题,避免声明出来没人使用的尴尬局面)

  1. list关于延迟初始化机制的一些处理 延迟初始化机制的缺点就在于在使用的时候需要判断是否已经初始化了,如果使用比较频繁的话,就会造成大量的计算浪费(cpu浪费) 所以list当中关于延迟初始化机制的处理方案如下:

    3.1 在插入新元素时 需要检查是否已经初始化好了

    3.2 在移动 或者将已有元素再修改位置插入时 需要判断元素身上的链表是否和要操作的链表的指针相同 如果不相同说明元素不存在该链表中 如果相同则说明这个链表肯定已经初始化好了

4. ring包和list包的区别

首先从源码来看

type Ring struct {
       next, prev *Ring
       Value
   }

type Element struct {
       next, prev *Element
       list *List //它所属的链表的指针
       Value interface{}
  }

type List struct {
       root element
       len int
   }
  • 从源码的定义分析得出 ring 的元素就是ring结构体(只代表了一个元素) 而list的元素 是list+element(代表了一个链表)
  • list在创建的时候不需要指定元素也没有必要,因为它会不停的增长 而ring的创建需要指定元素个数 且不再增长
  • 并且list的还存在一个没有实际意义的根元素 该根元素还可以用来连接首位两端 使其成为一个循环链表
  • ring包从实现来分析得出 适合用来执行长度固定的循环事件
  • heap包 则适合用来做堆排序 求第k大 第k小等问题 还有就是优先调度问题--首先维护一个堆 然后针对每个要调度的事件 分配一个优先级 然后从下到上执行堆化过程 让优先级(最低或者最高的放到堆的顶部) 当处理完成之后 再把堆尾部的事件放到堆顶部 然后执行从上往下进行堆化维护好堆的顺序 再执行逻辑

盘胧

2021/08/19  阅读:31  主题:全栈蓝

作者介绍

盘胧