跳表(SkipList)的c++实现和性能测试

已于 2022-02-28 17:13:58 修改
阅读量2k 收藏 5
点赞数 2
分类专栏： 算法系列专题 文章标签： skipList 跳表 跳表性能测试 跳表c++实现 跳表概率因子
于 2022-02-28 16:25:57 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_40438165/article/details/123184655
版权

\quad 跳表的理论参考这个PPT，本文主要介绍跳表的实现，以及跳表的性能随着概率因子变化而变化的情况，从而发现最优概率因子的范围。

一、跳表的实现

\quad 跳表节点需要两个指针，一个指向右侧节点，一个指向下方节点，节点定义如下：

struct Node{
    int val;
    Node *next;  // 右边节点
    Node *down;  // 下方节点
    Node(int x){
        val = x;
        next = down = NULL;
    }
};

\quad 定义跳表类SkipList，跳表需要一个头节点，表示最高层最左侧的节点，该节点初始化为最小值。跳表还需要指定一个超参数——概率因子prob，表明以prob的概率向上生成新的一层，相同节点数目下，prob越大跳表深度越深。

class SkipList{
public:
    Node *head;
    double prob;  // 以prob的概率向上生成新的一层，prob越大跳表深度越深
    SkipList(double _prob=0.5){
        prob = _prob;
        head = new Node(INT32_MIN);  // 初始化头节点为最小值
    }
}

\quad 接下来完善跳表类中的查询、删除和插入代码，如下：

bool search(int x){  // 查看跳表中是否存在值为x的节点
    Node *p = head;
    while (p){
        if(p->val == x) return true;
        else if(p->next == NULL) p = p->down;  // 右侧节点为空，只能往下走
        else if(p->next->val > x) p = p->down;  // 右侧节点值大于x，往下走
        else p = p->next;  // 右侧节点值小于x，往右走
    }
    return false;  // p为空还没找到，则不存在
}

void erase(int x){  // 删除跳表中值为x的节点
    Node *p = head;
    while (p){
        if(p->next == NULL) p = p->down;
        else if(p->next->val > x) p = p->down;
        else if(p->next->val == x){
            p->next = p->next->next;  // 删除右侧值为x的节点
            p = p->down;
        }else p = p->next;
    }
}

void insert(int x){  // 往跳表中插入节点
    if(search(x)) return;  // 避免重复插入
    stack<Node *> st;  // 记录向下走过的节点，这一列节点后面可以插入x
    Node *p = head;
    while (p){
        if(p->next == NULL || p->next->val > x){
            st.push(p);  // 右侧没有节点或者右侧节点值更大， 说明新节点应该加在当前节点与右侧节点之间
            p = p->down;
        }else p = p->next;
    }
    Node *down = NULL;  // 保存最后一个插入的节点，如果最后需要额外新增一层时需要用到
    bool f = true;  // 用于保证最下方一层一定能插入新节点
    while (!st.empty()){
        Node *pre = st.top();  // 当前节点右侧用于插入新节点
        st.pop();
        double num = 1.0 * rand() / RAND_MAX;  // 取一个[0, 1)之间的随机数作为概率

        if(f || num < prob){  // 如果是最下面一层或者概率超过prob，则插入节点
            f = false;
            Node *t = new Node(x);
            if(pre->next == NULL) pre->next = t;
            else{
                t->next = pre->next;  // 插入新节点
                pre->next = t;
            }
            t->down = down;
            down = t;
        }else return;
    }
    // 通过随机数判断是否再上升一层
    double num = 1.0 * rand() / RAND_MAX;
    if(num < prob){  // 上升一层需要更新新的head节点
        Node *t = new Node(x);
        Node *minNode = new Node(INT32_MIN);
        minNode->down = head;
        minNode->next = t;
        t->down = down;
        head = minNode;
    }
}

\quad 接着可以给出一些辅助方法，即打印出该跳表和统计该跳表的最大深度、节点数和平均深度等信息，用于后续性能测试：

void show(){
    Node *p = head;
    while (p){
        Node *node = p->next;
        cout << "head";
        while (node){
            cout << "-->" << node->val;
            node = node->next;
        }
        cout << "-->NULL" << endl;
        p = p->down;
    }
}

void info(){  // 统计跳表最大深度，节点个数和节点平均深度
    int maxDepth = 0;  // 最大深度
    unordered_map<Node*, int> level; // 所有节点的深度
    Node *p = head;
    while (p) {
        maxDepth ++;
        Node *node = p->next;
        while (node){
            level[node] = maxDepth;
            node = node->next;
        }
        p = p->down;
    }
    cout << "max depth=" << maxDepth << endl;
    int NodeNum = level.size();  // 节点数目
    int s = 0;
    for(auto it: level) s += it.second;
    double avgLevel = s * 1.0 / NodeNum;  // 平均深度
    unordered_set<int> H;
    for(auto it: level) H.insert(it.first->val);
    double repeatRatio = 1.0 * NodeNum / H.size();
    cout << "node num=" << NodeNum << ", avg level=" << avgLevel << endl;
    cout << "different val num=" << H.size() << ", repeat ratio=" << repeatRatio << endl;
}

二、性能测试

\quad 我们随机产生100万个不同的整数插入进跳表，再依次查询这100万个数，统计在不同概率因子下程序耗时，完整地代码如下：

#include <iostream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <vector>
using namespace std;

struct Node{
    int val;
    Node *next;  // 右边节点
    Node *down;  // 下方节点
    Node(int x){
        val = x;
        next = down = NULL;
    }
};

class SkipList{
public:
    Node *head;
    double prob;  // 以prob的概率向上生成新的一层，prob越大跳表深度越深
    SkipList(double _prob=0.5){
        prob = _prob;
        head = new Node(INT32_MIN);  // 初始化头节点为最小值
    }

    bool search(int x){  // 查看跳表中是否存在值为x的节点
        Node *p = head;
        while (p){
            if(p->val == x) return true;
            else if(p->next == NULL) p = p->down;  // 右侧节点为空，只能往下走
            else if(p->next->val > x) p = p->down;  // 右侧节点值大于x，往下走
            else p = p->next;  // 右侧节点值小于x，往右走
        }
        return false;  // p为空还没找到，则不存在
    }

    void erase(int x){  // 删除跳表中值为x的节点
        Node *p = head;
        while (p){
            if(p->next == NULL) p = p->down;
            else if(p->next->val > x) p = p->down;
            else if(p->next->val == x){
                p->next = p->next->next;  // 删除右侧值为x的节点
                p = p->down;
            }else p = p->next;
        }
    }

    void insert(int x){  // 往跳表中插入节点
        if(search(x)) return;  // 避免重复插入
        stack<Node *> st;  // 记录向下走过的节点，这一列节点后面可以插入x
        Node *p = head;
        while (p){
            if(p->next == NULL || p->next->val > x){
                st.push(p);  // 右侧没有节点或者右侧节点值更大， 说明新节点应该加在当前节点与右侧节点之间
                p = p->down;
            }else p = p->next;
        }
        Node *down = NULL;  // 保存最后一个插入的节点，如果最后需要额外新增一层时需要用到
        bool f = true;  // 用于保证最下方一层一定能插入新节点
        while (!st.empty()){
            Node *pre = st.top();  // 当前节点右侧用于插入新节点
            st.pop();
            double num = 1.0 * rand() / RAND_MAX;  // 取一个[0, 1)之间的随机数作为概率

            if(f || num < prob){  // 如果是最下面一层或者概率超过prob，则插入节点
                f = false;
                Node *t = new Node(x);
                if(pre->next == NULL) pre->next = t;
                else{
                    t->next = pre->next;  // 插入新节点
                    pre->next = t;
                }
                t->down = down;
                down = t;
            }else return;
        }
        // 通过随机数判断是否再上升一层
        double num = 1.0 * rand() / RAND_MAX;
        if(num < prob){  // 上升一层需要更新新的head节点
            Node *t = new Node(x);
            Node *minNode = new Node(INT32_MIN);
            minNode->down = head;
            minNode->next = t;
            t->down = down;
            head = minNode;
        }
    }

    void show(){
        Node *p = head;
        while (p){
            Node *node = p->next;
            cout << "head";
            while (node){
                cout << "-->" << node->val;
                node = node->next;
            }
            cout << "-->NULL" << endl;
            p = p->down;
        }
    }

    void info(){  // 统计跳表最大深度，节点个数和节点平均深度
        int maxDepth = 0;  // 最大深度
        unordered_map<Node*, int> level; // 所有节点的深度
        Node *p = head;
        while (p) {
            maxDepth ++;
            Node *node = p->next;
            while (node){
                level[node] = maxDepth;
                node = node->next;
            }
            p = p->down;
        }
        cout << "max depth=" << maxDepth << endl;
        int NodeNum = level.size();  // 节点数目
        int s = 0;
        for(auto it: level) s += it.second;
        double avgLevel = s * 1.0 / NodeNum;  // 平均深度
        unordered_set<int> H;
        for(auto it: level) H.insert(it.first->val);
        double repeatRatio = 1.0 * NodeNum / H.size();
        cout << "node num=" << NodeNum << ", avg level=" << avgLevel << endl;
        cout << "different val num=" << H.size() << ", repeat ratio=" << repeatRatio << endl;
    }
};

void testTime(vector<int> &nums, double prob){
    clock_t start, end;
    start = clock();
    auto sp = new SkipList(prob);
    for(int num: nums){
        sp->insert(num);
    }
    for(int num: nums){
        sp->search(num);
    }
    end = clock();
    cout << "test size=" << nums.size() << ", prob=" << prob << endl;
    cout << "cost time=" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    sp->info();
    cout << "--------------------------------" << endl;
}
int main(){
    int n = 1000000;
    unordered_set<int> nums;
    while (nums.size() < n){
        nums.insert(rand() * rand());
    }
    vector<int> arr(nums.begin(), nums.end());

    for(int i = 1; i <= 9; i ++ ){
        testTime(arr, i * 1.0 / 10);
    }
}

在这里插入图片描述
\quad 如上图所示，当概率因子为0.2时耗费时间3.4s，效率最高，此时跳表最大深度为6，平均深度为5.8892，跳表中节点个数为111w，意味着平均每个数被重复1.11次。下表给出了各个概率因子下的各具体参数：

概率因子0.10.20.30.40.50.60.70.80.9
耗费时间(s)4.2293.4023.4583.6643.8333.9964.3765.2247.481
跳表最大深度69111718273555109
跳表中节点数目111119812507731428339166724919984152500761333072049944329997933
跳表中节点的平均深度5.88928.7488910.571916.33217.001325.499132.670451.007299.9984
跳表中节点的重复率1.11121.250771.428341.667251.998422.500763.330724.994439.99793

\quad 经过更细粒度的实验，得到概率因子最佳值为0.27，此时耗时3s左右，最大深度11，平均深度10.63。
\quad 使用相同的数据和测试方法，使用set耗时2.2s，使用unordered_set耗时0.6s，使用map耗时2s，使用unordered_map耗时0.7s。由此可见，c++自带的set和map性能更优，原因在于其不存在重复节点的情况。跳表主要是实现简单，其实性能和空间占用都比c++ stl更差。

三、Java版SkipList

import java.util.*;

public class SkipList {
    private class Node{
        int val;
        Node next;
        Node down;
        Node(int x){
            this.val = x;
            this.next = this.down = null;
        }
    }
    private Node head;
    private double prob;  // 概率因子
    SkipList(double prob){
        this.prob = prob;
        this.head = new Node(Integer.MIN_VALUE);
    }
    public boolean search(int x){
        Node p = head;
        while (p != null){
            if(p.val == x) return true;
            if(p.next == null || p.next.val > x) p = p.down;
            else p = p.next;
        }
        return false;
    }

    public void erase(int x){
        Node p = head;
        while (p != null){
            if(p.next == null || p.next.val > x) p = p.down;
            else if(p.next.val == x){
                p.next = p.next.next;
                p = p.down;
            }else p = p.next;
        }
    }

    public void insert(int x){
        if(search(x)) return;
        Stack<Node> st = new Stack<>();
        Node p = head;
        while (p != null){
            if(p.next == null || p.next.val > x){
                st.add(p);
                p = p.down;
            }else p = p.next;
        }
        Node down = null;
        boolean f = true;
        while(!st.isEmpty()){
            Node pre = st.pop();
            double num = Math.random();
            if(f || num < this.prob){
                f = false;
                Node t = new Node(x);
                if(pre.next == null) pre.next = t;
                else{
                    t.next = pre.next;
                    pre.next = t;
                }
                t.down = down;
                down = t;
            }else return;
        }
        double num = Math.random();
        if(num < this.prob){
            Node t = new Node(x);
            Node minNode = new Node(Integer.MIN_VALUE);
            minNode.down = head;
            minNode.next = t;
            t.down = down;
            head = minNode;
        }
    }

    public void print(){
        Node p = head;
        while (p != null){
            Node node = p.next;
            System.out.print("head");
            while (node != null){
                System.out.print("-->" + node.val);
                node = node.next;
            }
            System.out.println("-->NULL");
            p = p.down;
        }
    }

    public static void main(String[] args) {
        int n = 1000000;
        Set<Integer> st = new HashSet<>();
        while (st.size() < n){
            st.add((int)(Math.random() * 1000000000));
        }
        ArrayList<Integer> arr = new ArrayList<>();
        for(Integer num: st){
            arr.add(num);
        }
        long start = System.currentTimeMillis();
        SkipList sp = new SkipList(0.27);
        for(Integer num: arr){
            sp.insert(num);
        }
        for(Integer num: arr){
            sp.search(num);
        }
        long end = System.currentTimeMillis();
        System.out.println("SkipList cost time=" + (end - start) / 1000.0 + "s");

        start = System.currentTimeMillis();
        Set<Integer> set = new TreeSet<>();
        for(Integer num: arr){
            set.add(num);
        }
        for(Integer num: arr){
            set.contains(num);
        }
        end = System.currentTimeMillis();
        System.out.println("TreeSet cost time=" + (end - start) / 1000.0 + "s");
    }
}
《 C++ 修炼全景指南：二十七 》不止是链表升级！跳表的核心原理与超强性能解析
Lenyiin
11-16 5549
这篇博客全面解析了跳表 (Skip List) 作为一种高效的链表数据结构的特性和应用。跳表以多层链表和随机化策略实现 O(log n) 的查找、插入和删除性能，简化了平衡树结构中常见的复杂旋转操作。通过剖析跳表的结构设计和核心操作，我们探讨了其在范围查询和动态更新中的优势，分析了跳表在空间复杂度、缓存性能及并发控制上的局限性。特别地，博客深入介绍了跳表的性能优化策略，包括空间利用率提升、缓存优化与多线程支持，展示了跳表在大数据应用和数据库索引中的潜在应用价值。最后，结合磁盘友好性需求，展望了跳表的未来发展
跳表的C++实现
Castria的博客
11-07 2803
跳表(Skip List)是在链表基础上进行改进的一种有序的数据结构，它为了便于查找，在插入过程中随机地将一些元素提升为高度为1~r的索引，以此来加快之后的操作。索引可以分为多层，一般而言，层数越高的索引个数越少。下面的图是一个跳表示例（隐去表头，上面的为高层） 为了方便下面对代码实现的说明，先给出各数据类型的定义。 template<typename T> class skiplist { private: static constexpr int MAX_LEVEL = 16; s
skiplist跳表C++实现
03-04
skiplist的C++实现，包含test程序
跳表 （Skip List） C++ 实现
木牛的博客
05-24 1085
跳表 （Skip List） C++ 实现 跳表原理 跳表 c++ 实现 SkipNode SkipList 随机层数 结点最大层数 基本操作 打印 主函数 输出结果 在学习 C++ 中的过程中，找个算法作为练习。 仅供参考。 跳表原理 跳表原理讲解请参考 https://lotabout.me/2018/skip-list/ 为了节约时间，这里只是简单说明，原文如上。 跳表(skip list) 对标的是平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O ( l o g n ) O
skiplist 跳表C++实现
10-08
skiplist 跳表C++实现,资料参考 en.wikipedia.org/wiki/Skip_list
C++【跳表】
芊樱烛渊的博客
12-29 1531
skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是一样的，可以作为key或者key/value的查找模型。skiplist是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A对细节感兴趣的同学可以下载论文原文来阅读。skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。如果是一个有序的链表，查找数据的时间复杂度是O(N)。假如我们每相邻两个节点升高一层，增加一个指针。
跳表--C++实现
weixin_46120107的博客
03-04 1436
为何要学习跳表？为了快，为了更快，为了折磨自己.....
(源码)基于C++的无锁跳表实现.zip
最新发布
02-25
本项目实现了一个基于C++的无锁跳表（LockFree Skiplist）数据结构，支持高效的并发读写操作。跳表是一种有序的数据结构，通过多层链表实现快速查找、插入和删除操作。本项目通过使用memory order语义实现了无锁化的...
C++课程作业基于跳表实现的轻型键值型数据库源码+项目说明.zip
08-10
- skiplist.h 存储引擎核心 - main.cpp 使用控制台进行数据操作 - bin文件夹 生成可执行文件目录（.main 和 .stress） - makefile 编译脚本 - store文件夹 生成数据落盘文件（dumpFile） - stress_test_start.sh ...
数据结构-C++之17-skiplist.zip
09-23
在文件“数据结构-C++之17-skiplist.zip”中，可以预期包含了与C++实现跳表相关的文件和代码。这类文件一般包含以下几个方面： 1. 跳表的定义和数据表示：包括节点结构的设计，以及不同层级的链接如何表示。 2. ...
跳跃表 C++实现
11-23
跳跃表的C++实现版本。 提供与红黑树的测试用例。
C++跳表的实现
03-03
用C++实现跳表的创建、添加、查找、删除等操作
c++如何实现跳表（skiplist）
12-17
引言 二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。 定义 跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。性能上和红黑树，AVL树不相上下，但跳表的原理非常简单，目前Redis和LevelDB中都有用到。 跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡，而不是严格平衡。因此，跟平衡二叉树相比，跳表的插入和删除操作要简单得多
c++如何实现跳表
08-18
主要介绍了c++如何实现跳表，帮助大家更好的理解和学习，感兴趣的朋友可以了解下
skiplist数据结构简介
chuixieli7527的博客
10-03 506
skiplist数据结构简介 skiplist本质上也是一种查找结构，用于解决算法中的查找问题（Searching），即根据给定的key，快速查到它所在的位置（或者对应的value）。 一般查找问题的解法分为两个大类：一个是基于各种平衡树，一个是基于哈希表。但skiplist却比较特殊，它没法...
C++ SkipList简单实现
xupeng1644的博客
11-11 2286
SkipList.h： #pragma once #include <vector> struct SkipListNode { SkipListNode(int data, int level); int m_data; std::vector<SkipListNode*> m_forward; }; class SkipList { public: Ski...
跳表-skiplist的简单实现
冯同学的博客
10-03 2661
跳表-skiplist的简单实现
[C++]跳表
mzman的博客
01-02 496
跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表是有序链表，当一个新节点加入跳表时，会按照一定的概率分布获得一个索引等级，高等级的产生几率小于低等级。每个节点有一组next指针，各个等级的节点构成各个等级的链表，每个节点不同的next指针用于不同等级的链表，高等级的节点也都会出现在低等级的链表中，即高等级链表是低等级链表的子集。 例如二分跳表，所有节点都出现在0级链表中，而只有1/2的节点出现在1级链表中，有1/8的节点出现在2级链表中……设相邻等级高等级与低等级出现率的比值为p,(
跳表c++实现
weixin_44866921的博客
10-07 592
原理：https://blog.csdn.net/u013011841/article/details/39158585 一.跳表结构 1.节点 //节点 class node { int val; int level;//节点的高度(层次) node* forword[MAXLEVEL];//指向node*的数组 }; 2.skiplist（管理整个表的一个数据结构） class skiplist { private: node* head;//指向跳表的头结点 int max_length
C++实现跳表基本功能及搜索测试示例
对于跳过列表的实现，需要定义节点（Node）结构体和跳过列表类（SkipList）。 - 节点结构体通常包含数据域和指针域。指针域指向同级的前一个节点和后一个节点，以及下一级的对应节点。 - 跳过列表类包含多个方法，...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值