企业网站怎做如何做网站淘宝客

当前位置： 首页 > news >正文

企业网站怎做,如何做网站淘宝客,安徽省建设局网站,wordpress后台菜单加入页面目录

1. Skiplist跳表的概念
2. Skiplist跳表的效率
3. Skiplist跳表的实现 3.1 力扣1206. 设计跳表 3.2 Skiplist的初始化和查找 3.3 Skiplist的增加和删除 3.4 Skiplist的源码和OJ测试
4. 跳表和平衡搜索树/哈希表的对比 本篇完。 1. Skiplist跳表的概念 skiplist是…目录
5. Skiplist跳表的概念 2. Skiplist跳表的效率
6. Skiplist跳表的实现 3.1 力扣1206. 设计跳表 3.2 Skiplist的初始化和查找 3.3 Skiplist的增加和删除 3.4 Skiplist的源码和OJ测试 4. 跳表和平衡搜索树/哈希表的对比 本篇完。 1. Skiplist跳表的概念 skiplist是由美国计算机科学家William Pugh威廉 普格于1989年发明。skiplist本质上是一种查找结构用于解决算法中的查找问题跟平衡搜索树和哈希表的价值是 一样的可以作为key或者key/value的查找模型。skiplist顾名思义首先它是一个list。实际上它是在有序链表的基础上发展起来的。我们知道在对一个有序链表进行查找它的时间复杂度为O(N)。 William Pugh开始了他的优化思路 假如我们每相邻两个节点升高一层增加一个指针让指针指向下下个节点如下图所示 这样新增的一层指针通过连接可以形成新的链表它包含了整个链表节点的一半由此需要在这一层进行比较、筛除的个数也就降低了一半。 以此类推继续增加一层指针新链表的节点数下降查找的效率自然而然也就提高了。按照上述每增加一层节点数就少一半其查找的过程类似于二分查找使得查找的时间复杂度可以降低到OlogN。 上述查找的前提是一个有序的链表。无论是对其中的链表新增节点还是删除节点都可能打乱原有维持的指针连接从而导致跳表失效。如果要维持这种对应关系就必须把新插入的节点后面的所有节点也包括新插入的节点重新进行调整这会让时间复杂度重新退化成ON。 随机层数: 为了避免这种情况skiplist的设计不再严格要求对应比例关系而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数。 2. Skiplist跳表的效率 那么skiplist在引入随机层数后如何保证其查找效率呢首先这个随机层数会有一个限制这里把它叫做maxLevel其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图 在Redis的skiplist实现中这两个参数的取值为p 1/4maxLevel 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)。…… 最终可以得到这样一个数学式用于计算一个节点的平均层数: 有了这个公式我们可以很容易计算出: 当 p  1/2 时: 每个节点所包含的平均指针数目为2。 当 p  1/4 时: 每个节点所包含的平均指针数目为1.33。                  至于跳表的平均时间复杂度为OlogN的证明这推导的过程较为复杂下面的两篇中英文章有详细讲解 铁蕾大佬的博客Redis内部数据结构详解(6)——skiplist - 铁蕾的个人博客 William_Pugh大佬的论文http://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf 3. Skiplist跳表的实现 力扣上有一道实现跳表的题可以在这上面完成跳表的测试 3.1 力扣1206. 设计跳表
7. 设计跳表 难度 困难 不使用任何库函数设计一个 跳表 。 跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树其功能与性能相当并且跳表的代码长度相较下更短其设计思想与链表相似。 例如一个跳表包含 [30, 40, 50, 60, 70, 90] 然后增加 80、45 到跳表中以下图的方式操作 跳表中有很多层每一层是一个短的链表。在第一层的作用下增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))空间复杂度是 O(n)。 了解更多 : 跳表 - OI Wiki 在本题中你的设计应该要包含这些函数 bool search(int target) : 返回target是否存在于跳表中。void add(int num): 插入一个元素到跳表。bool erase(int num): 在跳表中删除一个值如果 num 不存在直接返回false. 如果存在多个 num 删除其中任意一个即可。 注意跳表中可能存在多个相同的值你的代码需要处理这种情况。 示例 1: 输入 [Skiplist, add, add, add, search, add, search, erase, erase, search] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] 输出 [null, null, null, null, false, null, true, false, true, false]解释 Skiplist skiplist new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // 返回 false skiplist.add(4); skiplist.search(1); // 返回 true skiplist.erase(0); // 返回 false0 不在跳表中 skiplist.erase(1); // 返回 true skiplist.search(1); // 返回 false1 已被擦除提示: 0 num, target 2 * 10^4调用search, add,  erase操作次数不大于 5 * 10^4  class Skiplist { public:Skiplist() {}bool search(int target) {}void add(int num) {}bool erase(int num) {} };/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj new Skiplist();* bool param_1 obj-search(target);* obj-add(num);* bool param_3 obj-erase(num);/ 3.2 Skiplist的初始化和查找 Skiplist的初始化 跳表不仅仅是要存储数据 _data还需要有next指针当然这些next指针也不止一个 这取决于当前节点的层数。 结合此图就可以知道next指针应该在一个数组中 class SkiplistNode { public:int _val;vectorSkiplistNode _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){} };class Skiplist { private:typedef SkiplistNode Node;Node* _head;size_t _maxLevel 32;double _p 0.5; public:Skiplist(){_head new SkiplistNode(-1, 1); // 头节点层数是1} } Skiplist的search查找 查找的过程查找是要和下一个节点的值相比并不是和当前节点的值相比一开始cur在哨兵位头节点的最高层 head开始进行比较。设要查找的值为target如果下一个节点为空或者下一个节点的值比target大那么cur需要向下一层走如果下一个节点的值比targe小那么cur向右走。重复上述过程直至找到或者没找到没找到的话cur会到第-1层层数是从第0层开始的 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 Skiplist的增加和删除 Skiplist的add增加 假设要增加17要怎么操作 获得这个结点的层数RandomLevel( );找到这个结点的前后链接关系此过程就像查找这个结点每一层的前一个结点后面的删除结点也需要用到所以封装成一个FindPrevNode函数比如查找17的话就是prev_val 17 next_val需要从头结点开始找记录每一层的前一个指针。 Skiplist(){srand(time(nullptr)); // 构造函数种下随机数种子_head new SkiplistNode(-1, 1); // 头节点层数是1}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){prevV[level] cur; // 更新level层前一个–level; //下一个节点是空(尾)目标值比下一个节点值要小向下走}}return prevV;}void add(int num){vectorNode* prevV FindPrevNode(num);int n RandomLevel();Node* newnode new Node(num, n);if (n _head-_nextV.size()) // 如果n超过当前最大的层数那就升高一下_head的层数{_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;}}int RandomLevel(){size_t level 1; // rand() -[0, RAND_MAX]之间while (rand() RAND_MAX * _p level _maxLevel){level;}return level;} 这里的RandomLevel()是以一种巧妙的方式完成的 通过_p可以控制最终值产生范围的概率。如_p是0.5的话生成的随机数小于RAND_MAX的一半才可能增加层数。 Skiplist的erase删除 删除怎么操作假设现在要删除17 删除的操作和增加的操作几乎一样通过FindPrevNode找到该结点的所有前驱结点让所有前驱结点指向被删除结点的next即可。 bool erase(int num){vectorNode* prevV FindPrevNode(num);if (prevV[0]-_nextV[0] nullptr || prevV[0]-_nextV[0]-_val ! num){return false; // 第一层下一个不是valval不在表中}else{Node* del prevV[0]-_nextV[0];for (size_t i 0; i del-_nextV.size(); i) // del节点每一层的前后指针链接起来{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.4 Skiplist的源码和OJ测试 class SkiplistNode { public:int _val;vectorSkiplistNode* _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){} };class Skiplist { private:typedef SkiplistNode Node;Node* _head;size_t _maxLevel 32;double _p 0.5; public:Skiplist(){srand(time(nullptr)); // 构造函数种下随机数种子_head new SkiplistNode(-1, 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){prevV[level] cur; // 更新level层前一个–level; //下一个节点是空(尾)目标值比下一个节点值要小向下走}}return prevV;}void add(int num){vectorNode* prevV FindPrevNode(num);int n RandomLevel();Node* newnode new Node(num, n);if (n _head-_nextV.size()) // 如果n超过当前最大的层数那就升高一下_head的层数{_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;}}int RandomLevel(){size_t level 1; // rand() -[0, RAND_MAX]之间while (rand() RAND_MAX * _p level _maxLevel){level;}return level;}bool erase(int num){vectorNode* prevV FindPrevNode(num);if (prevV[0]-_nextV[0] nullptr || prevV[0]-_nextV[0]-_val ! num){return false; // 第一层下一个不是valval不在表中}else{Node* del prevV[0]-_nextV[0];for (size_t i 0; i del-_nextV.size(); i) // del节点每一层的前后指针链接起来{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;}} };/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj new Skiplist();* bool param_1 obj-search(target);* obj-add(num);* bool param_3 obj-erase(num);*/ 4. 跳表和平衡搜索树/哈希表的对比 跳表和平衡搜索树的对比 跳表相比平衡搜索树AVL树和红黑树对比都可以做到遍历数据有序时间复杂度也差不多都是OlogN。不过跳表与平衡搜索树相比跳表的优势在于 跳表实现简单容易控制。平衡树增删查改遍历都更复杂。跳表的额外空间消耗更低。平衡树节点存储每个值有三叉链平衡因子/颜色等消耗。可是跳表可以通过p来调整每个节点的指针个数那是个可接受的数量。 跳表和哈希表的对比 跳表相比哈希表而言跳表在查找效率上更差一点。哈希表平均时间复杂度是O1比跳表的OlogN快。 skiplist与哈希表相比skiplist的优势在于 遍历数据有序。skiplist空间消耗略小一点哈希表存在链接指针和表空间消耗。哈希表在极端场景下哈希冲突高效率下降厉害需要红黑树补足接力。 本篇完。 高阶数据结构到这先暂告一段落了。