Golang implementiert eine Skip-Tabelle

Skip-Liste ist eine Datenstruktur, die auf verknüpften Listen basiert. Durch das Hinzufügen einiger zusätzlicher Zeiger zur verknüpften Liste wird die Effizienz der Datensuche und -operation im Vergleich zu gewöhnlichen verknüpften Listen erheblich verbessert. Sprungtabellen wurden ursprünglich 1990 von William Pugh vorgeschlagen und werden häufig in Datenbanken, Suchmaschinen und anderen Bereichen verwendet. In diesem Artikel wird erläutert, wie Sie mithilfe der Go-Sprache die Datenstruktur für übersprungene Tabellen implementieren.

1. Übersicht über die Sprungliste

Die Sprungliste ist eine mehrstufige verknüpfte Listenstruktur. Die Datenknoten jeder Ebene der verknüpften Liste werden auf mehrere Knoten der nächsten Ebene der verknüpften Liste verteilt. Jeder Knoten in der Sprungliste verfügt über ein Array mit mehreren Zeigern, die auf den Wurzelknoten und den Knoten an derselben Position in der verknüpften Liste der nächsten Ebene verweisen. Diese Zeiger werden zufällig oder nach bestimmten Regeln gesetzt. Falsche Einstellungen führen dazu, dass die Sprungliste zu einer einfach verknüpften Liste degeneriert, daher muss die Zeigerverteilung entsprechend eingestellt werden.

Die Sprungtabelle unterstützt grundlegende Operationen wie Addition, Löschung und Suche. Ihre zeitliche Komplexität beträgt O(log n), was der zeitlichen Komplexität eines Binärbaums entspricht. Da die Struktur der Sprungliste auf einer verknüpften Liste basiert, ist zum Speichern von Zeigerinformationen eine gewisse Menge zusätzlicher Speicherplatz erforderlich.

2. Implementierung der Sprungtabelle

Zunächst müssen wir die Knotenstruktur der Sprungtabelle definieren:

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

Die Knotenstruktur definiert den Wert des Knotens und des Zeigerarrays, das als Nächstes auf den nächsten Knoten zeigt. Die Anzahl der Knoten in der nächsten Ebene wird zufällig festgelegt und über die Funktion rand.Intn() generiert.

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
}

Nachdem wir die Knotenstruktur und die Funktion definiert haben, die die zufällige Anzahl von Ebenen generiert, können wir die Struktur der Sprungliste definieren:

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

Die Sprunglistenstruktur enthält den Zeiger-Array-Kopf, der auf den Kopfknoten der Sprungliste zeigt und die aktuelle Sprungliste, Tiefenstufe und Anzahl der Sprungtabellenknoten, Länge. Die anfängliche Tiefe der Sprungtabelle beträgt 1, und die Tiefe ändert sich entsprechend der Anzahl der Ebenen, die beim Hinzufügen von Knoten durch Zufallszahlen generiert werden.

Nachdem wir die Sprunglistenstruktur definiert haben, können wir mit der Implementierung der Grundoperationen der Sprungliste beginnen. Die erste ist die Einfügeoperation:

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++
}

Die Einfügeoperation generiert zunächst eine zufällige Anzahl von Ebenen, erstellt neue Knoten und zeichnet beim Einfügen jeder Ebene in die Sprungtabelle die Position mithilfe des Aktualisierungsarrays auf. Beginnen Sie dann auf der obersten Ebene und suchen Sie nach unten nach dem einzufügenden Ort, zeichnen Sie den vorherigen Knoten des einzufügenden Ortes auf und aktualisieren Sie dann die Richtung des eingefügten Knotens und des vorherigen Knotens in der Sprungtabelle jeder Ebene. Abschließend werden die Tiefe und die Anzahl der Knoten der Sprungtabelle aktualisiert.

Der nächste Schritt ist der Löschvorgang:

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--
    }
}

Der Löschvorgang findet zunächst den zu löschenden Knoten und zeichnet seine Position und die Position des vorherigen Knotens auf. Wenn der zu löschende Knoten gefunden wird, wird der Knotenzeiger aktualisiert und die Tiefe und Anzahl der Knoten der Sprungtabelle werden aktualisiert.

Der letzte ist der Suchvorgang:

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
}

Der Suchvorgang ähnelt im Wesentlichen den Einfüge- und Löschvorgängen. Er beginnt auf der obersten Ebene und sucht nach unten nach dem zu findenden Knoten, zeichnet seine Position auf und gibt den Knoten zurück, wenn gefunden.

3. Sprunglistenanalyse

Die Sprungliste ist eine effiziente Datenstruktur, die auf verknüpften Listen basiert. Im Vergleich zum ausgeglichenen Binärbaum ist die zeitliche Komplexität ihrer Einfüge- und Löschvorgänge gleich (O(log n)), aber Die zeitliche Komplexität der Suchoperation beträgt Die Komplexität beträgt O (log n), was effizienter ist als die Suchzeitkomplexität O (h) eines Binärbaums, wobei h die Höhe des Baums ist. Aufgrund der Einstellung zufälliger Ebenen ist auch die Höhe der Sprungtabelle zufällig und das Einfügen, Löschen und Suchen ist effizienter.

Die Sprungliste kann ihre Raumkomplexität auch steuern, indem sie die Anzahl der Knoten und Zeiger angemessen festlegt. Das Setzen mehrerer Zeiger in der Sprungliste und der Verbrauch von mehr Speicherplatz sind ein Kompromiss. Um eine bessere Leistung zu erzielen, ist dieser zusätzliche Speicherplatzaufwand in einigen bestimmten Szenarien sinnvoller.

4. Zusammenfassung

Die Skip-Liste ist eine effiziente verknüpfte Listendatenstruktur, die als Ersatz für den ausgeglichenen Baum verwendet werden kann, um große Cache-Datenspeicher- und Suchprobleme zu lösen. Die Parallelitätsfunktionen und die flache Paketstruktur der Go-Sprache machen Sprunglisten in Go-Anwendungen sehr praktisch. Der Schlüssel zur Implementierung einer Skip-Tabelle liegt in der zufälligen Generierung von Knotenebenen, dem Finden der einzufügenden und zu löschenden Orte und dem Aktualisieren von Knotenzeigern. Durch diese Grundoperationen ist die Effizienz von Sprunglisten höher als die von gewöhnlichen verknüpften Listen, und die Anzahl der Knoten und Zeiger kann entsprechend spezifischer Anwendungsszenarien angemessen festgelegt werden.

Das obige ist der detaillierte Inhalt vonGolang implementiert eine Skip-Tabelle. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!