Go語言list（列表）

2021-11-10

專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)順河免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上千多家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

列表是一種非連續(xù)的存儲(chǔ)容器，有多個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)通過一些變量記錄彼此之間的關(guān)系

單鏈表和雙鏈表就是列表的兩種方法。叢辯

原理：A、B、C三個(gè)人，B懂A的Tel ，C懂B的Tel 只是單方知道號碼，這樣就形成了一個(gè)單鏈表結(jié)構(gòu)。

如果C把自己的號碼給B，B把自己的號碼給A，因?yàn)槭请p方都知道對方的號碼，這樣就形成滲鏈缺了一個(gè)雙鏈表結(jié)構(gòu)

如果B換號碼了，他需要通知AC，把自己的號碼刪了，這個(gè)過程就是列表的刪除操作。

在Go語言中，列表使用 container/list 包來實(shí)現(xiàn)，內(nèi)部的實(shí)現(xiàn)原理是雙鏈表，列表能夠高效地進(jìn)行任意位置的元素插入和刪除操作。

列表初始化的兩種辦法

列表沒有給出具體的元素類型的限制，所以列表的元素可以是任意類型的，

例如給列表中放入了一個(gè) interface{} 類型的值，取出值后，如果要將 interface{} 轉(zhuǎn)換為其他類型將會(huì)發(fā)生宕機(jī)。

雙鏈表支持從隊(duì)列前方或后方插入元素，分別對應(yīng)的方法是 PushFront 和 PushBack。

列表插入函數(shù)的返回值會(huì)提供一喚中個(gè) *list.Element 結(jié)構(gòu)，這個(gè)結(jié)構(gòu)記錄著列表元素的值以及與其他節(jié)點(diǎn)之間的關(guān)系等信息，從列表中刪除元素時(shí)，需要用到這個(gè)結(jié)構(gòu)進(jìn)行快速刪除。

遍歷完也能看到最后的結(jié)果

學(xué)習(xí)地址：

lru如何實(shí)現(xiàn)啊啊啊

package main

import (

"encoding/json"

"expvar"

"fmt"

"github點(diǎn)抗 /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

}

// 檢旅廳查是否無需移動(dòng)，并且list相同才移動(dòng)帆鎮(zhèn)山

func (l *List) MoveToFront(e *Element) {

// move是已經(jīng)找到，這個(gè)時(shí)態(tài)中候不需要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是已經(jīng)找到，這個(gè)時(shí)候不需要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 // 重點(diǎn)是go中的避免內(nèi)存泄漏。。。。。。。。。。。。。。。。。。。。。。。。

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

}

// 主要是一個(gè)map用于快速查找數(shù)據(jù)。

// 如果已經(jīng)存在移到到頭部

// 不然添加到頭部然后cache緩存

// 如果沒有大于最大大小則remove最老的

// 由于remove的時(shí)候需要去掉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

}

Go語言設(shè)計(jì)與實(shí)現(xiàn)（上）

基本設(shè)計(jì)思路：

類型轉(zhuǎn)換、類型斷言、動(dòng)態(tài)派發(fā)。iface，eface。

反射對象具有的方法：

編譯優(yōu)化：

內(nèi)部實(shí)現(xiàn)：

實(shí)現(xiàn) Context 接口有以下幾個(gè)類型（空實(shí)現(xiàn)就忽略了）：

互斥鎖的控制邏輯：

設(shè)計(jì)思路：

（以上為寫被讀阻塞，下面是讀被寫阻塞）

總結(jié)，讀寫鎖的設(shè)計(jì)還是非常巧妙的：

設(shè)計(jì)思路：

WaitGroup 有三個(gè)暴露的函數(shù):

部件：

設(shè)計(jì)思路：

結(jié)構(gòu)：

Once 只暴露了一個(gè)方法：

實(shí)現(xiàn)：

三個(gè)關(guān)鍵點(diǎn)：

細(xì)節(jié)：

讓多協(xié)程任務(wù)的開始執(zhí)行時(shí)間可控（按順序或歸一）。（Context 是控制結(jié)束時(shí)間）

設(shè)計(jì)思路： 通過一個(gè)鎖和內(nèi)置的 notifyList 隊(duì)列實(shí)現(xiàn)，Wait() 會(huì)生成票據(jù)，并將等待協(xié)程信息加入鏈表中，等待控制協(xié)程中發(fā)送信號通知一個(gè)（Signal()）或所有（Boardcast()）等待者（內(nèi)部實(shí)現(xiàn)是通過票據(jù)通知的）來控制協(xié)程解除阻塞。

暴露四個(gè)函數(shù)：

實(shí)現(xiàn)細(xì)節(jié)：

部件：

包： golang.org/x/sync/errgroup

作用：開啟 func() error 函數(shù)簽名的協(xié)程，在同 Group 下協(xié)程并發(fā)執(zhí)行過程并收集首次 err 錯(cuò)誤。通過 Context 的傳入，還可以控制在首次 err 出現(xiàn)時(shí)就終止組內(nèi)各協(xié)程。

設(shè)計(jì)思路：

結(jié)構(gòu)：

暴露的方法：

實(shí)現(xiàn)細(xì)節(jié)：

注意問題：

包： "golang.org/x/sync/semaphore"

作用：排隊(duì)借資源（如肢州錢，有借有還）的一種場景。此包相當(dāng)于對底層信號量的一種暴露。

設(shè)計(jì)思路：有一定數(shù)量的資源 Weight，每一個(gè) waiter 攜帶一個(gè) channel 和饑激要借的數(shù)量 n。通過隊(duì)列排隊(duì)執(zhí)行借貸。

結(jié)構(gòu)：

暴露方法：

細(xì)節(jié)：

部件：

細(xì)節(jié)：

包： "golang.org/x/sync/singleflight"

作用：防擊穿。瞬時(shí)的相同請求只調(diào)用一次，response 被所有相同請求共享。

設(shè)計(jì)思路：按請求的 key 分組（一爛饑襪個(gè) *call 是一個(gè)組，用 map 映射存儲(chǔ)組），每個(gè)組只進(jìn)行一次訪問，組內(nèi)每個(gè)協(xié)程會(huì)獲得對應(yīng)結(jié)果的一個(gè)拷貝。

結(jié)構(gòu)：

邏輯：

細(xì)節(jié)：

部件：

如有錯(cuò)誤，請批評指正。

本文標(biāo)題：go語言實(shí)現(xiàn)LRU隊(duì)列 go語言實(shí)現(xiàn)消息隊(duì)列
網(wǎng)站網(wǎng)址：http://chinadenli.net/article18/dsppgdp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)公司、定制網(wǎng)站、云服務(wù)器、網(wǎng)站導(dǎo)航、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)