Golang はスキップテーブルを実装します

スキップリストはリンクリストをベースにしたデータ構造で、リンクリストにポインタを追加することで、通常のリンクリストに比べてデータの検索や操作の効率が大幅に向上します。ジャンプ テーブルは、1990 年に William Pugh によって最初に提案され、データベース、検索エンジン、その他の分野で広く使用されています。この記事ではGo言語を使ってスキップテーブルのデータ構造を実装する方法を紹介します。

1. スキップ リストの概要

スキップ リストは、複数レベルのリンク リスト構造であり、リンク リストの各レベルのデータ ノードは、次のレベルのリンク リストの複数のノードに分散されます。リスト。ジャンプ リストの各ノードには、ルート ノードと次のレベルのリンク リストの同じ位置にあるノードを指す複数のポインタを含む配列があります。これらのポインタはランダムまたは一定のルールに従って設定されますが、設定を誤るとジャンプ リストが単一リンク リストに変質してしまうため、ポインタの配分を適切に設定する必要があります。

スキップ テーブルは、追加、削除、検索などの基本的な操作をサポートしており、その時間計算量は O(log n) であり、これは 2 分木の時間計算量と同等です。スキップ リスト構造はリンク リストに基づいているため、ポインタ情報を格納するにはある程度の追加の記憶領域が必要です。

2. ジャンプ テーブルの実装

最初に、ジャンプ テーブルのノード構造を定義する必要があります:

type skipListNode struct {
    Val       int                            // 节点值
    next      []*skipListNode               // 指向下一层节点的指针数组
}

ノード構造はノードの値を定義し、次の層 次のノードのポインター配列。次の層のノードの数はランダムに設定され、rand.Intn() 関数によって生成されます。

func newNode(val int, level int) *skipListNode {
    node := &skipListNode{Val: val, next: make([]*skipListNode, level+1)}
    return node
}

func randLevel() int {
    level := 1
    for rand.Float32() < 0.5 {
        level++
    }
    return level
}

ノード構造と乱数のレイヤーを生成する関数を定義した後、スキップ テーブルの構造を定義できます。

type skipList struct {
    head   []*skipListNode              // 指向跳表头节点的指针数组
    level  int                           // 当前跳表深度
    length int                          // 跳表节点数量
}

スキップ テーブル構造には、スキップ テーブルのヘッド ポインタ配列のヘッド、現在のスキップ テーブルの深さレベル、およびスキップ テーブル ノードの長さの数。ジャンプテーブルの初期深さは1であり、ノード追加時に乱数により生成されるレベル数に応じて深さが変更されます。

ジャンプ リスト構造を定義した後、ジャンプ リストの基本操作の実装を開始できます。 1 つ目は挿入操作です。

func (sl *skipList) insert(val int) {
    level := randLevel()                   // 生成随机层数
    node := newNode(val, level)            // 创建新节点
    update := make([]*skipListNode, level+1) // 用于更新每层跳表的节点指针
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {       // 从最高层开始向下查找
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找插入位置
            cur = cur.next[i]
        }
        update[i] = cur                      // 更新每层跳表要插入的位置
    }
    for i := 0; i <= level; i++ {            // 更新每层跳表插入节点
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    }
    // 更新跳表深度和节点数
    if level > sl.level {
        sl.level = level
    }
    sl.length++
}

挿入操作では、最初に乱数のレイヤーを生成し、新しいノードを作成し、更新配列を使用して各レイヤーをジャンプ テーブルに挿入するときの位置を記録します。次に、最上位から開始して挿入する位置を下方向に検索し、挿入する位置の前のノードを記録し、各層のジャンプ テーブルで挿入されたノードと前のノードの方向を更新します。最後に、ジャンプテーブルの深さとノード数が更新されます。

次のステップは削除操作です。

func (sl *skipList) delete(val int) {
    update := make([]*skipListNode, sl.level+1) // 用于更新每层跳表的节点指针
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找要删除的节点位置
            cur = cur.next[i]
        }
        if cur.next[i] != nil && cur.next[i].Val == val { // 找到要删除的节点
            update[i] = cur
        } else {
            update[i] = nil
        }
    }
    if update[0] != nil && update[0].next[0].Val == val { // 更新节点指针
        node := update[0].next[0]
        for i := 0; i <= sl.level && update[i].next[i] == node; i++ {
            update[i].next[i] = node.next[i]
        }
        // 更新跳表深度和节点数
        for sl.level > 0 && len(sl.head[sl.level].next) == 0 {
            sl.level--
        }
        sl.length--
    }
}

削除操作では、まず削除するノードを見つけて、その位置と前のノードの位置を記録します。削除すべきノードが見つかった場合には、ノードポインタを更新し、ジャンプテーブルの深さとノード数を更新する。

最後は検索操作です:

func (sl *skipList) search(val int) *skipListNode {
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找要查找的节点位置
            cur = cur.next[i]
        }
    }
    if cur.next[0] != nil && cur.next[0].Val == val { // 找到要查找的节点
        return cur.next[0]
    }
    return nil // 没有找到节点，返回nil
}

検索操作は基本的に挿入操作と削除操作に似ています。最上位から開始して、検索するノード、レコードを下方向に検索します。その位置を調べ、ノードが見つかった場合はそのノードを返します。

3. スキップ リスト分析

スキップ リストは、リンク リストに基づいた効率的なデータ構造です。バランスの取れた二分木と比較して、その挿入および削除操作の時間計算量は同じです ( O(log n )) ですが、検索操作の時間計算量は O(log n) であり、二分木の検索時間計算量 O(h) (h は木の高さ) よりも効率的です。ランダムレイヤーの設定により、ジャンプテーブルの高さもランダムになり、挿入、削除、検索の効率も高くなります。

スキップ テーブルは、ノードとポインターの数を合理的に設定することによって、その空間の複雑さを制御することもできます。ジャンプ リストに複数のポインターを設定し、より多くのストレージ領域を消費することはトレードオフです。パフォーマンスを向上させるために、特定のシナリオでは、これらの追加領域のオーバーヘッドがより合理的です。

4. 概要

スキップ リストは、大規模なキャッシュ データ ストレージと検索の問題に対処するためにバランス ツリーの代わりに使用できる効率的なリンク リスト データ構造です。 Go 言語の同時実行機能とフラット パッケージ構造により、スキップ リストは Go アプリケーションで非常に実用的になります。スキップ テーブルを実装する鍵は、ノード レベルのランダムな生成、挿入および削除される位置の検索、およびノー​​ド ポインターの更新にあります。これらの基本操作により、スキップ リストは通常​​のリンク リストよりも効率が高く、特定のアプリケーション シナリオに応じてノードとポインタの数を合理的に設定できます。

以上がGolang はスキップテーブルを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。