dede网站地图路径修改,wordpress硬件接口,网站建设常见问题及解决办法,wordpress导航的设置目录 1.什么是跳表-skiplist
2.skiplist的效率如何保证#xff1f;
3.skiplist的实现
3.1节点和成员设计
3.2查找实现
3.3前置节点查找
3.4插入实现
3.5删除实现
3.6随机层数
3.7完整代码
4.skiplist跟平衡搜索树和哈希表的对比 1.什么是跳表-skiplist
skiplist是由…目录 1.什么是跳表-skiplist
2.skiplist的效率如何保证
3.skiplist的实现
3.1节点和成员设计
3.2查找实现
3.3前置节点查找
3.4插入实现
3.5删除实现
3.6随机层数
3.7完整代码
4.skiplist跟平衡搜索树和哈希表的对比 1.什么是跳表-skiplist
skiplist是由William Pugh发明的最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。 skiplist顾名思义首先它是一个list。实际上它是在有序链表的基础上发展起来的。如果是一个有序的链表查找数据的时间复杂度是O(N)。 William Pugh开始的优化思路 1. 假如我们每相邻两个节点升高一层增加一个指针让指针指向下下个节点如下图b所 示。这样所有新增加的指针连成了一个新的链表但它包含的节点个数只有原来的一半。由 于新增加的指针我们不再需要与链表中每个节点逐个进行比较了需要比较的节点数大概 只有原来的一半。 2. 以此类推我们可以在第二层新产生的链表上继续为每相邻的两个节点升高一层增加一个指针从而产生第三层链表。如下图c这样搜索效率就进一步提高了。 如图b中查找8从头结点出发6比8小向右走跳跃到68比9小当前节点向下走从下面指针出发7比8小跳转到78比9小向下走走不了了链表中不存在8.
如图c中查找19,比9大向右走跳跃到9比21小向下走比17大向右走跳跃到17比17大向右走跳跃到17比21小向下走跟19相等找到了。 3. skiplist正是受这种多层链表的想法的启发而设计出来的。实际上按照上面生成链表的方 式上面每一层链表的节点个数是下面一层的节点个数的一半这样查找过程就非常类似 二分查找使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时 候有很大的问题插入或者删除一个节点之后就会打乱上下相邻两层链表上节点个数严格 的2:1的对应关系。如果要维持这种对应关系就必须把新插入的节点后面的所有节点也 包括新插入的节点重新进行调整这会让时间复杂度重新蜕化成O(n)。 4. skiplist的设计为了避免这种问题做了一个大胆的处理不再严格要求对应比例关系而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数这样就好处理多了按时插入删除我们仍然需要考虑其他节点对应层指针的连接问题。细节过程入下图 2.skiplist的效率如何保证
上面我们说到skiplist插入一个节点时随机出一个层数听起来怎么这么随意如何保证搜索时 的效率呢 这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限 制其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图 在Redis的skiplist实现中这两个参数的取值为
p 1/4
maxLevel 32
根据前面randomLevel()的伪码我们很容易看出产生越高的节点层数概率越低。定量的分析 如下 节点层数至少为1。而大于1的节点层数满足一个概率分布。 节点层数恰好等于1的概率为1-p。 节点层数大于等于2的概率为p而节点层数恰好等于2的概率为p(1-p)。 节点层数大于等于3的概率为p^2而节点层数恰好等于3的概率为p^2*(1-p)。 节点层数大于等于4的概率为p^3而节点层数恰好等于4的概率为p^3*(1-p)。 …… 因此一个节点的平均层数也即包含的平均指针数目计算如下 现在很容易计算出 当p1/2时每个节点所包含的平均指针数目为2 当p1/4时每个节点所包含的平均指针数目为1.33。 跳表的平均时间复杂度为O(logN) 这个推导的过程较为复杂需要有一定的数据功底有兴趣的可以参考以下文章中的讲解
铁蕾大佬的博客http://zhangtielei.com/posts/blog-redis-skiplist.html
William_Pugh大佬的论文ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
3.skiplist的实现
1206. 设计跳表 - 力扣LeetCode 3.1节点和成员设计 跳表因为每个节点是层数是随机的所以我们使用vector容器存储对应指针。
对于一开始的同节点我们这里设计成一层高减少后续不必要遍历消耗。
struct SkiplistNode
{int _val;vectorSkiplistNode* _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};
class Skiplist {typedef SkiplistNode Node;
public:Skiplist() {//为了后续层数随机这里提供种子srand(time(0));// 头节点层数是1_head new SkiplistNode(-1, 1);}private:Node* _head; // 头节点size_t _maxLevel 32;//层数的最大高度double _p 0.25;/多增加一层的概率p
};
3.2查找实现 依照跳表的设计当我们查找一个数时如果当前层的指针指向的数比要查找的数大那我们就需要向下走因为链表是有序的比较小的数一定在前面而且层高一定没有当前层指向节点高如果搞就指向这个更小的数了。所以我们要找比当前层指向节点小的数需要向下层走。
反之如果比当前层指向节点值比要查找的数小说明要查找的数在后面我们直接沿当前层指针往后跳转。 bool search(int target) {Node* cur _head;int level _head-_nextV.size() - 1;while (level 0){// 目标值比下一个节点值要大向右走// 下一个节点是空(尾)目标值比下一个节点值要小向下走if (cur-_nextV[level] cur-_nextV[level]-_val target){// 向右走cur cur-_nextV[level];}else if (cur-_nextV[level] nullptr || cur-_nextV[level]- _val target){// 向下走--level;}else{return true;}}return false;}
3.3前置节点查找 因为跳表中节点的层高没有严格的比例关系因此一个节点可能由于层高较高与前后多个节点有关系如上图中6有4层0层上3指向它6指向71层上头结点指向6,6指向92层上头结点指向6,6指向253层上头结点指向6,6指向nullptr。
因此当我们删除或者增加一个节点我们就需要建立它每一层上指针与其他节点间关系同时也需要修改其他其他节点。
这就意味着当前要插入/删除节点就需要从整个跳表中找到每一层指针对应的上一个节点更新指针指向。
解决的思想是利用查找节点过程因为当一层指针指向空或者比要查找的值大的值时我们向下走这同时也意味着此时这层节点就是当前要插入节点的当前层的上一层节点同时这届指针指向的下层节点也就是插入节点指针要指向的下一个节点。我们通过查找节点不断向下走的过程就能找到插入节点每一层的上一个节点和要指向的下一层节点。
需要注意的是当查找节点比当前节点大直接跳转的过程我们不能更新上一层节点的记录因为这是只是同层节点间的跳转我们不能确定插入节点当前层的上一个节点。
vectorNode* FindPrevNode(int num){Node* cur _head;int level _head-_nextV.size() - 1;// 插入位置每一层前一个节点指针vectorNode* prevV(level 1, _head);while (level 0){// 目标值比下一个节点值要大向右走// 下一个节点是空(尾)目标值比下一个节点值要小向下走if (cur-_nextV[level] cur-_nextV[level]-_val num){// 向右走cur cur-_nextV[level];}else if (cur-_nextV[level] nullptr|| cur-_nextV[level]-_val num){// 更新level层前一个prevV[level] cur;// 向下走--level;}}return prevV;}
3.4插入实现
当我们能找到插入节点的每一层对应上一个节点我们插入节点只需要更新对应的指向上一个指针指向它插入节点指向下一个节点。
这里需要注意的是插入节点的层数我们封装一个函数来给在最大范围内的随机值跳表的头结点需要确保是跳表中最高的节点这样才不会出现无法跳转更高层的问题所以如果当前的随机值如果比头节点高我们就需要更新下头结点高度。 void add(int num) {vectorNode* prevV FindPrevNode(num);int n RandomLevel();//随机层数Node* newnode new Node(num, n);// 如果n超过当前最大的层数那就升高一下_head的层数if (n _head-_nextV.size()){_head-_nextV.resize(n, nullptr);prevV.resize(n, _head);}// 链接前后节点for (size_t i 0; i n; i){newnode-_nextV[i] prevV[i]-_nextV[i];prevV[i]-_nextV[i] newnode;}// Print();}
3.5删除实现 删除节点后我们需要根据找到的每一层的上一个节点更新一下对应指针将删除节点上一个节点和指向下一个节点相连。
这里加入删除的节点是最高点我们更新一下头结点的高度避免每次从很高的位置向下遍历不过就几层相对来说影响不大。 bool erase(int num) {vectorNode* prevV FindPrevNode(num);// 第一层下一个不是valval不在表中if (prevV[0]-_nextV[0] nullptr || prevV[0]-_nextV[0]-_val !num){return false;}else{Node* del prevV[0]-_nextV[0];// del节点每一层的前后指针链接起来for (size_t i 0; i del-_nextV.size(); i){prevV[i]-_nextV[i] del-_nextV[i];}delete del;// 如果删除最高层节点把头节点的层数也降一下int i _head-_nextV.size() - 1;while (i 0){if (_head-_nextV[i] nullptr)--i;elsebreak;}_head-_nextV.resize(i 1);return true;}}
3.6随机层数 //产生随机层数int RandomLevel(){size_t level 1;//每一个节点最少一层。// 因为rand() -[0, RAND_MAX]之间所以RAND_MAX * _p的数出现概率就是p// 可以视作rand()/RAND_MAX pwhile (rand() RAND_MAX * _p level _maxLevel){level;}return level;}//C中的随机函数库使用比较麻烦/*int RandomLevel(){static std::default_random_enginegenerator(std::chrono::system_clock::now().time_since_epoch().count());static std::uniform_real_distributiondouble distribution(0.0,1.0);size_t level 1;while (distribution(generator) _p level _maxLevel){level;}return level;}*/
3.7完整代码
struct SkiplistNode
{int _val;vectorSkiplistNode* _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};
class Skiplist {typedef SkiplistNode Node;
public:Skiplist() {srand(time(0));// 头节点层数是1_head new SkiplistNode(-1, 1);}bool search(int target) {Node* cur _head;int level _head-_nextV.size() - 1;while (level 0){// 目标值比下一个节点值要大向右走// 下一个节点是空(尾)目标值比下一个节点值要小向下走if (cur-_nextV[level] cur-_nextV[level]-_val target){// 向右走cur cur-_nextV[level];}else if (cur-_nextV[level] nullptr || cur-_nextV[level] - _val target){// 向下走--level;}else{return true;}}return false;}vectorNode* FindPrevNode(int num){Node* cur _head;int level _head-_nextV.size() - 1;// 插入位置每一层前一个节点指针vectorNode* prevV(level 1, _head);while (level 0){// 目标值比下一个节点值要大向右走// 下一个节点是空(尾)目标值比下一个节点值要小向下走if (cur-_nextV[level] cur-_nextV[level]-_val num){// 向右走cur cur-_nextV[level];}else if (cur-_nextV[level] nullptr|| cur-_nextV[level]-_val num){// 更新level层前一个prevV[level] cur;// 向下走--level;}}return prevV;}void add(int num) {vectorNode* prevV FindPrevNode(num);int n RandomLevel();Node* newnode new Node(num, n);// 如果n超过当前最大的层数那就升高一下_head的层数if (n _head-_nextV.size()){_head-_nextV.resize(n, nullptr);prevV.resize(n, _head);}// 链接前后节点for (size_t i 0; i n; i){newnode-_nextV[i] prevV[i]-_nextV[i];prevV[i]-_nextV[i] newnode;}// Print();}bool erase(int num) {vectorNode* prevV FindPrevNode(num);// 第一层下一个不是valval不在表中if (prevV[0]-_nextV[0] nullptr || prevV[0]-_nextV[0]-_val !num){return false;}else{Node* del prevV[0]-_nextV[0];// del节点每一层的前后指针链接起来for (size_t i 0; i del-_nextV.size(); i){prevV[i]-_nextV[i] del-_nextV[i];}delete del;// 如果删除最高层节点把头节点的层数也降一下int i _head-_nextV.size() - 1;while (i 0){if (_head-_nextV[i] nullptr)--i;elsebreak;}_head-_nextV.resize(i 1);return true;}}int RandomLevel(){size_t level 1;// rand() -[0, RAND_MAX]之间while (rand() RAND_MAX * _p level _maxLevel){level;}return level;}/*int RandomLevel(){static std::default_random_enginegenerator(std::chrono::system_clock::now().time_since_epoch().count());static std::uniform_real_distributiondouble distribution(0.0,1.0);size_t level 1;while (distribution(generator) _p level _maxLevel){level;}return level;}*/private:Node* _head; // 头节点size_t _maxLevel 32;double _p 0.25;
};
4.skiplist跟平衡搜索树和哈希表的对比 1. skiplist相比平衡搜索树(AVL树和红黑树)对比都可以做到遍历数据有序时间复杂度也差 不多。skiplist的优势是a、skiplist实现简单容易控制。平衡树增删查改遍历都更复杂。 b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链平衡因子/颜色等消耗。 skiplist中p1/2时每个节点所包含的平均指针数目为2skiplist中p1/4时每个节点所包 含的平均指针数目为1.33 2. skiplist相比哈希表而言就没有那么大的优势了。相比而言a、哈希表平均时间复杂度是 O(1)比skiplist快。b、哈希表空间消耗略多一点。skiplist优势如下a、遍历数据有序 b、skiplist空间消耗略小一点哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损 耗。d、哈希表再极端场景下哈希冲突高效率下降厉害需要红黑树补足接力。
