Go双方向チェーンテーブルの実現

この文書では、チェーンテーブルとは何か、一般的なチェーンテーブルとは何かを紹介し、チェーンテーブルというデータ構造がどのような場所で使用できるか、Redisキューが最下位の実装であるか、Redisキューにどのような機能があるかを小さな例で示し、最後にGoによって双方向チェーンテーブルを実現します.
目次

1、チェーンテーブル

1.1説明

1.2一方向チェーンテーブル

1.3循環チェーンテーブル

1.4双方向チェーンテーブル

2、redisキュー

2.1説明

2.2アプリケーションシーン

2.3デモ

3、Go双方向チェーンテーブル

3.1説明

3.2

を実現

4、総括

5、参考文献

1、チェーンテーブル
1.1説明
チェーンテーブル(Linked list)は一般的な基礎データ構造であり、線形テーブルであるが、線形の順序でデータを格納するのではなく、各ノードに次のノードに格納するポインタ(Pointer)である.順番に格納する必要がないため、チェーンテーブルは挿入時にO(1)の複雑さに達し、別の線形テーブルの順序テーブルよりもずっと速いが、1つのノードを検索したり、特定の番号のノードにアクセスしたりするにはO(n)の時間が必要であり、順序テーブルに対応する時間の複雑さはそれぞれO(logn)とO(1)である.
チェーンテーブルには、一方向チェーンテーブル、双方向チェーンテーブル、ループチェーンテーブルなど、さまざまなタイプがあります.

メリット:

配列チェーンテーブルが予めデータサイズを知る必要があるという欠点を克服することができ、チェーンテーブル構造はコンピュータのメモリ空間を十分に利用し、柔軟なメモリ動態管理を実現することができる.チェーンテーブルでは、テーブル上の任意の場所のノードを挿入および削除できます.

劣勢:

チェーンテーブルにノードポインタが追加されたため、スペースオーバーヘッドが大きい.チェーンテーブルは、一般的にデータを検索するときに、最初のノードから次のノードにアクセスするたびに、必要な場所にアクセスするまで、データの検索が遅い必要があります.

用途:

組織の取得が少なく、削除、追加、遍歴が多いデータによく使用されます.
ファイルシステム、LRU cache、Redisリスト、メモリ管理など.
1.2一方向チェーンテーブル
チェーンテーブルの中で最も簡単なのは一方向チェーンテーブルです.
1つの一方向チェーンテーブルのノードは2つの部分に分かれている.2つのドメイン、1つの情報ドメイン、および1つのポインタドメインが含まれます.第1の部分はノードに関する情報を保存または表示し、第2の部分は次のノードのアドレスを格納し、最後のノードは空の値を指します.一方向チェーンテーブルは一方向にのみ遍歴できます.
単一チェーンテーブルにはヘッダノードheadがあり、チェーンテーブルのメモリのヘッダアドレスを指します.チェーンテーブル内の各ノードのデータ型は構造体タイプであり、ノードには2つのメンバーがあります.整数メンバー(実際に保存する必要があるデータ)と、次の構造体タイプノードへのポインタである次のノードのアドレス(実際には、この単一チェーンテーブルは整数データを格納するための動的配列です).チェーンテーブルこの構造による各ノードへのアクセスは、チェーンテーブルのヘッダから開始する必要があり、後続のノードのアドレスは現在のノードによって与えられる.テーブルでどのノードにアクセスするかにかかわらず、チェーンテーブルのヘッダから順に後方に検索する必要があります.チェーンテーブルの末尾ノードは後続ノードがないため、ポインタドメインが空で、NULLとして書きます.
1.3循環チェーンテーブル
ループチェーンテーブルは、一方向チェーンテーブルと同様にチェーン式の記憶構造であり、異なるのは、ループチェーンテーブルの最後のノードのポインタが、そのループチェーンテーブルの最初のノードまたはヘッダノードを指し、環状のチェーンを構成することである.
ループチェーンテーブルの演算は、単一チェーンテーブルの演算とほぼ一致します.違いは以下の点です.
1.循環チェーンテーブルを作成する場合、単一チェーンテーブルのようにNULLにするのではなく、最後のノードのポインタをテーブルヘッダノードに向けなければならない.
2.末尾に到達したか否かを判断する場合は、そのノードのチェーンドメインの値がヘッダノードであるか否かを判断し、チェーンドメインの値がヘッダポインタに等しい場合は、末尾に到達したことを説明する.単一チェーンテーブルのようにチェーンドメインの値がNULLであるか否かを判断するのではない.
1.4双方向チェーンテーブル
双方向チェーンテーブルは、単一チェーンテーブルの改良であり、単一チェーンテーブルを操作するときに、ノードの直接前駆体を操作する場合があります.また、テーブルの先頭から検索する必要があります.これは、単一チェーンテーブルノードの構造によって制限されます.単一チェーンテーブルの各ノードには直接後継ノードアドレスを格納するチェーンドメインが1つしかないので、直接後継ノードアドレスを格納するチェーンドメインと、直接前駆ノードアドレスを格納するチェーンドメインとを定義できるのではないでしょうか.これが双方向チェーンテーブルです.
双方向チェーンテーブルでは、ノードにはデータドメインのほかに2つのチェーンドメインがあり、1つは直接後続のノードアドレスを格納し、一般的に右チェーンドメインと呼ばれている(この「接続」が最後の「接続」の場合、空の値または空のリストを指す).直接前駆ノードアドレスを格納します.一般的に左チェーンドメインと呼ばれます(この「接続」が最初の「接続」の場合、空の値または空のリストを指します).
2.redisキュー
2.1説明
Redisリストは単純な文字列リストで、挿入順に並べ替えられています.リストのヘッダー(左)または末尾(右)に要素を追加できます.
Redisリストは、最下位の実装として2つのデータ構造を使用します.両端リスト(linkedlist)、圧縮リスト(ziplist)です.
プロファイル(list-max-ziplist-entries、list-max-ziplist-value)からどのインプリメンテーションを選択するか
データ量が少ない場合は、両端チェーンテーブルと圧縮リストのパフォーマンスの差は大きくありませんが、圧縮リストを使用するとメモリスペースが節約されます.
redisチェーンテーブルの実装ソースコードredis src/adlist.h
2.2シーンの適用
メッセージキュー、秒殺アイテム
秒殺項目:
事前に必要な商品コード情報をRedisキューに格納し、買い占めの際に各ユーザーがRedisキューから商品コードを取得する.Redisは単一スレッドであると同時に1つの商品コードしか取り出せないため、商品コードを取得したユーザーは購入に成功し、Redis性能が高く、大きなユーザー圧力に耐えられる.
2.3プレゼンテーション
どのようにしてRedisキューで同時販売の場合の商品の超過販売を防止するか.
仮定:
サイトには3つの商品が販売されており、Redisキューにデータを格納しています.
1、三つの商品コード(10001、10002、10003)をRedis列に入れる

#     
RPUSH commodity:queue 10001 10002 10003

2、預け入れ後、データが予想通りかどうかを調べる

#       
LRANGE commodity:queue 0 -1

#        
LLEN commodity:queue

3、買い占め開始、商品コードを取得し、商品コードを奪ったユーザーは購入できる(Redisは単一スレッドであるため、同じ商品コードは一度しか取られない)

#   
LPOP commodity:queue

ここではRedisリストがどのように使用されているかを理解し,以下ではGo言語で双方向チェーンテーブルを実現してこれらの機能を実現する.
3、Go双方向チェーンテーブル
3.1説明
ここではただGo言語で双方向チェーンテーブルを実現し、チェーンテーブルの長さを問い合わせる、チェーンテーブルの右端にデータを挿入する、左端にデータを取る、指定区間のノードを取るなどの機能(RedisリストのRPUSH、LRANGE、LPOP、LLEN機能に類似)を実現する.
3.2実装

ノード定義

双方向チェーンテーブルには、前のノードと後のノードをそれぞれ指す2つのポインタがあります.
チェーンテーブルヘッダprevのポインタは空、チェーンテーブルヘッダnextのポインタは空

//        
type ListNode struct {
    prev  *ListNode //      
    next  *ListNode //      
    value string    //   
}

//       
func NewListNode(value string) (listNode *ListNode) {
    listNode = &ListNode{
        value: value,
    }

    return
}

//           
func (n *ListNode) Prev() (prev *ListNode) {
    prev = n.prev

    return
}

//           
func (n *ListNode) Next() (next *ListNode) {
    next = n.next

    return
}

//       
func (n *ListNode) GetValue() (value string) {
    if n == nil {

        return
    }
    value = n.value

    return
}

チェーンテーブル

を定義する
チェーンテーブルは操作を容易にするために、構造体を定義し、表の頭、表の尾から直接アクセスすることができ、属性lenを定義し、チェーンテーブルの長さを直接返すことができ、チェーンテーブルの長さを直接問い合わせると、時間の複雑さをO(n)からO(1)まで遍歴する必要はありません.

//   
type List struct {
    head *ListNode //     
    tail *ListNode //     
    len  int       //      
}


//        
func NewList() (list *List) {
    list = &List{
    }
    return
}

//        
func (l *List) Head() (head *ListNode) {
    head = l.head

    return
}

//        
func (l *List) Tail() (tail *ListNode) {
    tail = l.tail

    return
}

//       
func (l *List) Len() (len int) {
    len = l.len

    return
}

チェーンテーブルの右側に要素

を挿入する

//             
func (l *List) RPush(value string) {

    node := NewListNode(value)

    //        
    if l.Len() == 0 {
        l.head = node
        l.tail = node
    } else {
        tail := l.tail
        tail.next = node
        node.prev = tail

        l.tail = node
    }

    l.len = l.len + 1

    return
}

チェーンテーブルの左側からノード

を取り出す.

//            
func (l *List) LPop() (node *ListNode) {

    //     
    if l.len == 0 {

        return
    }

    node = l.head

    if node.next == nil {
        //     
        l.head = nil
        l.tail = nil
    } else {
        l.head = node.next
    }
    l.len = l.len - 1

    return
}

インデックス検索ノード

ノードはインデックスで検索され、インデックスが負の場合はテーブルの最後から検索されます.
自然数と負数のインデックスは、それぞれ2つの方法でノードを検索し、指定したインデックスを見つけるか、チェーンテーブルがすべて検索されると検索が完了します.

//         
//          
func (l *List) Index(index int) (node *ListNode) {

    //             
    if index < 0 {
        index = (-index) - 1
        node = l.tail
        for true {
            //    
            if node == nil {

                return
            }

            //     
            if index == 0 {

                return
            }

            node = node.prev
            index--
        }
    } else {
        node = l.head
        for ; index > 0 && node != nil; index-- {
            node = node.next
        }
    }

    return
}

は、指定区間の要素

を返す.

//          
func (l *List) Range(start, stop int) (nodes []*ListNode) {
    nodes = make([]*ListNode, 0)

    //      
    if start < 0 {
        start = l.len + start
        if start < 0 {
            start = 0
        }
    }

    if stop < 0 {
        stop = l.len + stop
        if stop < 0 {
            stop = 0
        }
    }

    //     
    rangeLen := stop - start + 1
    if rangeLen < 0 {

        return
    }

    startNode := l.Index(start)
    for i := 0; i < rangeLen; i++ {
        if startNode == nil {
            break
        }

        nodes = append(nodes, startNode)
        startNode = startNode.next
    }

    return
}

4、まとめ

ここまでチェーンテーブルの使用は終了しており、チェーンテーブルがどのようなものであるか(一方向チェーンテーブル、双方向チェーンテーブルおよび循環チェーンテーブル)を紹介し、チェーンテーブルの応用シーン(Redisリストはチェーンテーブルをベースとして実装している)も紹介し、最後にGoで双方向チェーンテーブルを実現し、チェーンテーブルがGo言語でどのように使用されているかを実証し、プロジェクトでより現実的に使用できるようになった.

5、参考文献
ウィキペディアチェーン
github redis
プロジェクトアドレス:go実装キュー
https://github.com/link1st/li...