2021-11-10
专注于为中小企业提供成都网站设计、成都网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业顺河免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上千多家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。
列表是一种非连续的存储容器，有多个节点组成，节点通过一些变量记录彼此之间的关系
单链表和双链表就是列表的两种方法。丛辩
原理：A、B、C三个人，B懂A的Tel ，C懂B的Tel 只是单方知道号码，这样就形成了一个单链表结构。
如果C把自己的号码给B，B把自己的号码给A，因为是双方都知道对方的号码，这样就形成渗链缺了一个双链表结构
如果B换号码了，他需要通知AC，把自己的号码删了，这个过程就是列表的删除操作。
在Go语言中，列表使用 container/list 包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置的元素插入和删除操作。
列表初始化的两种办法
列表没有给出具体的元素类型的限制，所以列表的元素可以是任意类型的，
例如给列表中放入了一个 interface{} 类型的值，取出值后，如果要将 interface{} 转换为其他类型将会发生宕机。
双链表支持从队列前方或后方插入元素，分别对应的方法是 PushFront 和 PushBack。
列表插入函数的返回值会提供一唤中个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从列表中删除元素时，需要用到这个结构进行快速删除。
遍历完也能看到最后的结果
学习地址：
package main
import (
"encoding/json"
"expvar"
"fmt"
"github点抗 /syndtr/goleveldb/leveldb"
"os"
)
func main() {
leveldb.Batch{}
var a []int
r := json.NewDecoder(os.Stdin)
for {
if !r.More() {
break
}
r.Decode(a)
fmt.Println(minimumMoves(a))
}
}
type List struct {
root Element // 为element而不是*element就是为了init方便
len int
}
// Init initializes or clears list l.
func (l *List) init() *List {
l.root.next = l.root
l.root.prev = l.root
l.len = 0
return l
}
func (l *List) lazyinit() {
if l.root.next == nil {
l.init()
}
}
func (l *List) PushFront(v interface{}) *Element {
l.lazyinit()
return l.insert(Element{v:v}, l.root)
}
func (l *List) Len() int {
return l.len
}
func (l *List) Back() *Element {
return l.root.prev
}
// 检旅厅查是否无需移动，并且list相同才移动帆镇山
func (l *List) MoveToFront(e *Element) {
// move是已经找到，这个时态中候不需要init
if e.l != l || l.root.next == e {
return
}
// see comment in List.Remove about initialization of l
l.move(e, l.root)
}
// move moves e to next to at and returns e.
func (l *List) move(e, at *Element) *Element {
if at == e {
return e
}
e.prev.next = e.next // 更改e的指向
e.next.prev = e.prev
// 插入
return l.insert(e, at)
}
func (l *List) insert(a, b *Element) *Element {
o := b.next
b.next = a
a.prev = b
a.next = o
o.prev = a
a.l = l
l.len++
return a
}
func (l *List) Remove(e *Element) {
// move是已经找到，这个时候不需要init
if e.l != l {
return
}
e.prev.next = e.next
e.next.prev = e.prev
e.next = nil // avoid memory leaks
e.prev = nil // avoid memory leaks
e.l = nil // 重点是go中的避免内存泄漏。。。。。。。。。。。。。。。。。。。。。。。。
l.len--
}
type Element struct {
prev *Element
next *Element
l *List
v interface{}
}
type entry struct {
key interface{}
value interface{}
}
type Cache struct {
maxEntries int
}
// 主要是一个map用于快速查找数据。
// 如果已经存在移到到头部
// 不然添加到头部然后cache缓存
// 如果没有大于最大大小则remove最老的
// 由于remove的时候需要去掉cache，所以存的是key
func (c Cache) Add(key, value interface{}) {
if c == nil { // lazy init
c.ll = NewList()
c.cache = make(map[interface{}] Element, 0)
}
}
func (c *Cache) Get(key interface{}) (value interface{}, ok bool) {
// 注意有名返回值保证直接return
// 又是检查nil的操作
if c.cache == nil {
return
}
}
// 重要的判断指针前判断是否非空
func (c *Cache) RemoveOldest() {
if c == nil {
return
}
ele := c.ll.Back()
if ele != nil {
c.removeElement(ele)
}
}
func (c *Cache) removeElement(e Element) {
c.ll.Remove(e)
kv := e.v.( entry)
delete(c.cache, kv.key)
}
// Clear purges all stored items from the cache.
func (c Cache) Clear() {
if c.OnEvicted != nil {
for _, e := range c.cache {
kv := e.Value.( entry)
c.OnEvicted(kv.key, kv.value)
}
}
c.ll = nil
c.cache = nil
}
基本设计思路：
类型转换、类型断言、动态派发。iface，eface。
反射对象具有的方法：
编译优化：
内部实现：
实现 Context 接口有以下几个类型（空实现就忽略了）：
互斥锁的控制逻辑：
设计思路：
（以上为写被读阻塞，下面是读被写阻塞）
总结，读写锁的设计还是非常巧妙的：
设计思路：
WaitGroup 有三个暴露的函数:
部件：
设计思路：
结构：
Once 只暴露了一个方法：
实现：
三个关键点：
细节：
让多协程任务的开始执行时间可控（按顺序或归一）。（Context 是控制结束时间）
设计思路： 通过一个锁和内置的 notifyList 队列实现，Wait() 会生成票据，并将等待协程信息加入链表中，等待控制协程中发送信号通知一个（Signal()）或所有（Boardcast()）等待者（内部实现是通过票据通知的）来控制协程解除阻塞。
暴露四个函数：
实现细节：
部件：
包： golang.org/x/sync/errgroup
作用：开启 func() error 函数签名的协程，在同 Group 下协程并发执行过程并收集首次 err 错误。通过 Context 的传入，还可以控制在首次 err 出现时就终止组内各协程。
设计思路：
结构：
暴露的方法：
实现细节：
注意问题：
包： "golang.org/x/sync/semaphore"
作用：排队借资源（如肢州钱，有借有还）的一种场景。此包相当于对底层信号量的一种暴露。
设计思路：有一定数量的资源 Weight，每一个 waiter 携带一个 channel 和饥激要借的数量 n。通过队列排队执行借贷。
结构：
暴露方法：
细节：
部件：
细节：
包： "golang.org/x/sync/singleflight"
作用：防击穿。瞬时的相同请求只调用一次，response 被所有相同请求共享。
设计思路：按请求的 key 分组（一烂饥袜个 *call 是一个组，用 map 映射存储组），每个组只进行一次访问，组内每个协程会获得对应结果的一个拷贝。
结构：
逻辑：
细节：
部件：
如有错误，请批评指正。