Golang melaksanakan jadual langkau

Skip list ialah struktur data berdasarkan senarai terpaut Dengan menambahkan beberapa petunjuk tambahan pada senarai terpaut, kecekapan carian dan operasi data bertambah baik berbanding senarai terpaut biasa. Jadual lompat pada asalnya dicadangkan oleh William Pugh pada tahun 1990 dan digunakan secara meluas dalam pangkalan data, enjin carian dan medan lain. Artikel ini akan memperkenalkan cara menggunakan bahasa Go untuk melaksanakan struktur data jadual langkau.

1. Gambaran keseluruhan senarai langkau

Senarai lompat ialah struktur senarai terpaut berbilang peringkat Nod data setiap peringkat senarai terpaut diedarkan di antara beberapa nod peringkat senarai terpaut yang seterusnya . Setiap nod dalam senarai lompatan mempunyai tatasusunan yang mengandungi berbilang penunjuk yang menghala ke nod akar dan nod di lokasi yang sama dalam senarai terpaut peringkat seterusnya. Penunjuk ini ditetapkan secara rawak atau mengikut peraturan tertentu.

Jadual langkau menyokong operasi asas seperti penambahan, pemadaman dan carian Kerumitan masanya ialah O(log n), yang bersamaan dengan kerumitan masa pokok binari. Memandangkan struktur senarai langkau adalah berdasarkan senarai terpaut, sejumlah ruang storan tambahan diperlukan untuk menyimpan maklumat penunjuk.

2. Pelaksanaan senarai lompat

Pertama, kita perlu mentakrifkan struktur nod senarai lompat:

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

Struktur nod mentakrifkan nilai nod dan menunjuk ke lapisan seterusnya Tatasusunan penunjuk nod seterusnya. Bilangan nod dalam lapisan seterusnya ditetapkan secara rawak dan dijana melalui fungsi 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
}

Selepas mentakrifkan struktur nod dan fungsi yang menjana nombor rawak lapisan, kita boleh menentukan struktur senarai langkau:

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

Struktur senarai langkau mengandungi nod yang menghala ke kepala senarai langkau Kepala tatasusunan penunjuk, tahap kedalaman jadual langkau semasa dan bilangan panjang nod jadual langkau. Kedalaman awal jadual lompat ialah 1, dan kedalaman diubah mengikut bilangan tahap yang dijana oleh nombor rawak apabila menambah nod.

Selepas mentakrifkan struktur senarai lompatan, kita boleh mula melaksanakan operasi asas senarai lompatan. Yang pertama ialah operasi sisipan:

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

Operasi sisipan mula-mula menjana nombor rawak lapisan, mencipta nod baharu dan menggunakan tatasusunan kemas kini untuk merekodkan kedudukan apabila memasukkan setiap lapisan ke dalam jadual lompat. Kemudian mulakan dari peringkat atas dan cari ke bawah untuk lokasi yang hendak disisipkan, rekodkan nod sebelumnya lokasi yang hendak disisipkan, dan kemudian kemas kini arah nod yang disisipkan dan nod sebelumnya dalam jadual lompatan setiap lapisan. Akhirnya, kedalaman dan bilangan nod jadual lompat dikemas kini.

Langkah seterusnya ialah operasi pemadaman:

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

Operasi pemadaman mula-mula mencari nod untuk dipadamkan dan merekodkan kedudukannya dan kedudukan nod sebelumnya. Jika nod yang hendak dipadam ditemui, penunjuk nod dikemas kini dan kedalaman serta bilangan nod jadual lompat dikemas kini.

Yang terakhir ialah operasi carian:

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
}

Operasi carian pada asasnya serupa dengan operasi sisipan dan pemadaman Ia bermula dari peringkat atas dan mencari ke bawah untuk mencari nod, rekod kedudukannya, dan mengembalikan nod jika ia ditemui.

3. Langkau senarai analisis

Langkau senarai ialah struktur data yang cekap berdasarkan senarai terpaut Berbanding dengan pepohon binari seimbang, kerumitan masa operasi pemasukan dan pemadamannya adalah sama (O(. log n )), tetapi kerumitan masa operasi carian ialah O(log n), yang lebih cekap daripada kerumitan masa carian pokok binari O(h), dengan h ialah ketinggian pokok. Oleh kerana penetapan lapisan rawak, ketinggian jadual lompat juga rawak, dan sisipan, pemadaman dan carian adalah lebih cekap.

Senarai langkau juga boleh mengawal kerumitan ruangnya dengan menetapkan bilangan nod dan penunjuk secara munasabah. Menetapkan berbilang petunjuk dalam senarai lompatan dan menggunakan lebih banyak ruang storan adalah satu pertukaran Untuk mendapatkan prestasi yang lebih baik, overhed ruang tambahan ini lebih munasabah dalam beberapa senario tertentu.

4. Ringkasan

Langkau senarai ialah struktur data senarai terpaut yang cekap yang boleh digunakan untuk menggantikan pepohon seimbang untuk menangani masalah penyimpanan data cache dan carian berskala besar. Ciri konkurensi dan struktur pakej rata bagi bahasa Go menjadikan senarai langkau sangat praktikal dalam aplikasi Go. Kunci untuk melaksanakan jadual langkau terletak pada penjanaan rawak tahap nod, mencari lokasi untuk dimasukkan dan dipadamkan, dan mengemas kini penunjuk nod. Melalui operasi asas ini, langkau senarai menjadikan kecekapannya lebih tinggi daripada senarai terpaut biasa, dan bilangan nod dan penunjuk boleh ditetapkan secara munasabah mengikut senario aplikasi tertentu.

Atas ialah kandungan terperinci Golang melaksanakan jadual langkau. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!