Golang implémente sauter la table

Skip list est une structure de données basée sur des listes chaînées. En ajoutant des pointeurs supplémentaires à la liste chaînée, l'efficacité de la recherche et du fonctionnement des données est grandement améliorée par rapport aux listes chaînées ordinaires. Les tables de saut ont été proposées à l'origine par William Pugh en 1990 et sont largement utilisées dans les bases de données, les moteurs de recherche et d'autres domaines. Cet article explique comment utiliser le langage Go pour implémenter la structure de données de table ignorée.

1. Aperçu de la liste de sauts

La liste de sauts est une structure de liste chaînée à plusieurs niveaux. Les nœuds de données de chaque niveau de liste chaînée sont répartis entre plusieurs nœuds du niveau suivant de liste chaînée. Chaque nœud de la liste de raccourcis possède un tableau contenant plusieurs pointeurs qui pointent vers le nœud racine et le nœud situé au même emplacement dans la liste chaînée de niveau suivant. Ces pointeurs sont définis de manière aléatoire ou selon certaines règles. Des paramètres incorrects entraîneront la dégénérescence de la liste de sauts en une liste à chaînage unique, la distribution des pointeurs doit donc être définie de manière appropriée.

La table de saut prend en charge les opérations de base telles que l'ajout, la suppression et la recherche. Sa complexité temporelle est O(log n), ce qui équivaut à la complexité temporelle d'un arbre binaire. Étant donné que la structure de la liste de sauts est basée sur une liste chaînée, une certaine quantité d'espace de stockage supplémentaire est requise pour stocker les informations du pointeur.

2. Implémentation de la table de saut

Tout d'abord, nous devons définir la structure des nœuds de la table de saut :

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

La structure du nœud définit la valeur du nœud et le tableau de pointeurs pointant ensuite vers le nœud suivant. Le nombre de nœuds dans la couche suivante est défini de manière aléatoire et généré via la fonction 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
}

Après avoir défini la structure des nœuds et la fonction qui génère le nombre aléatoire de couches, nous pouvons définir la structure de la liste de sauts :

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

La structure de la liste de sauts contient la tête du tableau de pointeurs pointant vers le nœud principal de la liste de sauts et le niveau de profondeur de la liste de sauts actuelle et la longueur du nombre de nœuds de la table de sauts. La profondeur initiale de la table de sauts est de 1 et la profondeur est modifiée en fonction du nombre de niveaux générés par des nombres aléatoires lors de l'ajout de nœuds.

Après avoir défini la structure de la liste de raccourcis, nous pouvons commencer à mettre en œuvre les opérations de base de la liste de raccourcis. La première est l'opération d'insertion :

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

L'opération d'insertion génère d'abord un nombre aléatoire de couches, crée de nouveaux nœuds et utilise le tableau de mise à jour pour enregistrer la position lors de l'insertion de chaque couche dans la table de saut. Commencez ensuite par le niveau supérieur et recherchez vers le bas l'emplacement à insérer, enregistrez le nœud précédent de l'emplacement à insérer, puis mettez à jour les directions du nœud inséré et du nœud précédent dans la table de saut de chaque couche. Enfin, la profondeur et le nombre de nœuds de la table de sauts sont mis à jour.

L'étape suivante est l'opération de suppression :

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

L'opération de suppression trouve d'abord le nœud à supprimer, en enregistrant sa position et la position du nœud précédent. Si le nœud à supprimer est trouvé, le pointeur de nœud est mis à jour, ainsi que la profondeur et le nombre de nœuds de la table de sauts.

La dernière est l'opération de recherche :

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
}

L'opération de recherche est fondamentalement similaire aux opérations d'insertion et de suppression. Elle commence par le niveau supérieur et recherche vers le bas le nœud à trouver, enregistre sa position et renvoie le nœud si. trouvé.

3. Analyse des listes à sauter

La liste à sauter est une structure de données efficace basée sur des listes chaînées. Par rapport à l'arbre binaire équilibré, la complexité temporelle de ses opérations d'insertion et de suppression est la même (O(log n)), mais. la complexité temporelle de l'opération de recherche est La complexité est O(log n), ce qui est plus efficace que la complexité temporelle de recherche O(h) d'un arbre binaire, où h est la hauteur de l'arbre. En raison du paramétrage de couches aléatoires, la hauteur de la table de saut est également aléatoire et l'insertion, la suppression et la recherche sont plus efficaces.

La liste de sauts peut également contrôler sa complexité spatiale en définissant raisonnablement le nombre de nœuds et de pointeurs. Définir plusieurs pointeurs dans la liste de raccourcis et consommer plus d'espace de stockage est un compromis. Afin d'obtenir de meilleures performances, ces frais généraux d'espace supplémentaire sont plus raisonnables dans certains scénarios spécifiques.

4. Résumé

Skip list est une structure de données de liste chaînée efficace qui peut être utilisée pour remplacer l'arborescence équilibrée afin de traiter les problèmes de stockage et de recherche de données de cache à grande échelle. Les fonctionnalités de concurrence et la structure de package plat du langage Go rendent les listes de sauts très pratiques dans les applications Go. La clé pour implémenter une table de saut réside dans la génération aléatoire de niveaux de nœuds, la recherche des emplacements à insérer et à supprimer et la mise à jour des pointeurs de nœuds. Grâce à ces opérations de base, les listes de sauts rendent leur efficacité supérieure à celle des listes chaînées ordinaires, et le nombre de nœuds et de pointeurs peut être raisonnablement défini en fonction de scénarios d'application spécifiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!