个人电子商务网站建设,自己做下载网站,比利时网站的后缀,免费软件资源最近学习redis的zset时候#xff0c;又看到跳表的思想#xff0c;突然对跳表的设置有了新的思考 这是19年设计的跳表#xff0c;在leetcode的执行时间是200ms 现在我对跳表有了新的想法 1、跳表的设计#xff0c;类似二分查找#xff0c;但是不是二分查找#xff0c;比较…最近学习redis的zset时候又看到跳表的思想突然对跳表的设置有了新的思考 这是19年设计的跳表在leetcode的执行时间是200ms 现在我对跳表有了新的想法 1、跳表的设计类似二分查找但是不是二分查找比较像之前遇到的一个面试题使用有限个数鸡蛋确定鸡蛋易损程度 2、跳表无法在设计的时候就达到完美状态而是在操作过程中一直维护较完美状态(动态平衡) 基于以上想法我开始重新进行跳表的设计在leetCode执行时间为14ms 设计思路如下 0、设计节点节点有next和pre两个指针且因为多层结构所以是数组表达 1、设计多层数据结构多层均为有序链表其中第0层包含所有数值 2、初始时只有一层结构先设计为10层结构 3、新增数据时如果发现步数(即执行next次数)过长(大于3倍层高)就进行抬升节点高度行为即节点high值增加
2023-03-04有补充看最下方
最初代码如下 Node类 class Node {Node[] next new Node[10];Node[] pre new Node[10];//节点高度int high 0;//节点值int value;//最近一次走到这个节点的步数int step 0;//这个仅是为了后续show方法使用int k 0;}基础参数及构造器 //头节点Node head;int maxHigh 0;//步数int step 0;public Skiplist() {}查询操作不直接查是否有而是查floor值后与tagert进行比较查floor作用是复用
public boolean search(int target) {if (head null) {return false;}if (head.value target) {return false;}//查询Floorreturn searchFloor(head, maxHigh, target).value target;
}private Node searchFloor(Node node, int high, int target) {//查到了if (node.value target) {return node;}//已经最下层了if (high -1) {return node;}//如果next值小于tagert,就进行next操作while (node.next[high] ! null node.next[high].value target) {//步数增加step;node node.next[high];node.step step;}//向下找return searchFloor(node, high - 1, target);
}新增节点
public void add(int num) {if (head null) {head new Node();head.value num;//没有head好处理return;}if (num head.value) {Node newHead new Node();newHead.value num;//比head还小加上之后充当新headsetNewHead(newHead, head);return;}step 0;Node newNode new Node();newNode.value num;//找到floor就加在floor后面Node node searchFloor(head, maxHigh, num);setNext(node, newNode);if (step 3 * maxHigh) {//需要抬高高度了这个方法很重要类似hashmap的扩容resize(newNode);}
}先把几个简单的方法展示出来 private void setNext(Node pre, Node node) {int high node.high;if (pre.next[high] null) {pre.next[high] node;node.pre[high] pre;} else {Node next pre.next[high];pre.next[high] node;node.pre[high] pre;node.next[high] next;next.pre[high] node;}}private void setNewHead(Node newHead, Node head) {newHead.high head.high;for (int i 0; i newHead.high; i) {newHead.next[i] head;head.pre[i] newHead;}this.head newHead;}重点在resize private void resize(Node node) {if (node.high maxHigh) {//如果当前高度已经是最高高度了将maxHigh增高maxHigh;if (maxHigh 10) {show();}node.high maxHigh;head.high maxHigh;head.next[maxHigh] node;node.pre[maxHigh] head;return;}//找前者Node pre getMoreHighPre(node);//抬高高度node.high;//加入节点(比如开始加在0层这时就记在1层)setNext(pre, node);//更新步数值node.step pre.step 1;//步数还大继续增高if (node.step 3 * (maxHigh 1)) {resize(node);}}private Node getMoreHighPre(Node node) {int high node.high;Node pre node.pre[high];//找到高一层级的上一个节点while (pre.high high) {pre pre.pre[high];}return pre;}删除操作 public boolean erase(int num) {if (head null) {return false;}if (head.value num) {if (head.next[0] ! null head.next[0].value num) {//能不删head尽量不删headremoveNode(head.next[0]);} else {//只能删除headremoveHead();}return true;}//一样找到对应节点Node node searchFloor(head, maxHigh, num);if (node.value num) {//移除removeNode(node);return true;}return false;}private void removeNode(Node node) {for (int i 0; i node.high; i) {//每一层都要删除Node pre node.pre[i];Node next node.next[i];if (next null) {//注意可能没有nextpre.next[i] null;} else {pre.next[i] next;next.pre[i] pre;}}}private void removeHead() {//删除头节点就是把老二当老大用if (head.next[0] null) {head null;}Node node head.next[0];node.high head.high;for (int i 1; i maxHigh; i) {if (head.next[i] ! null head.next[i] ! node) {node.next[i] head.next[i];head.next[i].pre[i] node;}}head node;}以上代码执行后leetCode执行时长为19ms已经远快于19年的代码 但是我发现了问题所在 因为数组高度有限设置的高度为10如果高度不够就会出现数组越界我尝试进行测试写了show方法 private void show() {System.out.println(总数i为出现越界);System.out.println(0级并设置k);head.k 0;int k 0;Node node head;while (node ! null) {node.k k;node node.next[0];}for (int i 1; i 10; i) {System.out.println(i 级间隔);node head;Node next node.next[i];while (next ! null) {System.out.print(next.k - node.k ,);node next;next node.next[i];}System.out.println();}}结果如下 居然一万多数值之后就越界了思考原因所在 应该是抬高的node不应该是插入的那个node应该是node所在层次的中间node调整接口如下
通过middleNode找到需要抬高的node
private void resize(Node node) {if (node.high maxHigh) {//最高层这个可以接受maxHigh;if (maxHigh max) {show();}node.high maxHigh;head.high maxHigh;head.next[maxHigh] node;node.pre[maxHigh] head;return;}//找前人Node pre getMoreHighPre(node);//不应该直接用node升级应该用node区间的中间值node middleNode(pre, node);node.high;//加入节点setNext(pre, node);node.step pre.step 1;if (node.step 3 * (maxHigh 1)) {resize(node);}
}寻找middleNode的代码如下
private Node middleNode(Node pre, Node node) {int high node.high;if (pre.next[high 1] null) {return getLast(node);}Node next pre.next[high 1];int left getLen(pre, node, node.high);int right getLen(node, next, node.high);if (left right) {return node;}if (left right) {return left(node, (left - right) / 2);} else {return right(node, (right - left) / 2);}
}private int getLen(Node left, Node right, int high) {int step 0;while (left ! right) {left left.next[high];step;}return step;
}private Node left(Node node, int step) {if (step 0) {return node;}return left(node.pre[node.high], step - 1);
}private Node right(Node node, int step) {if (step 0) {return node;}return right(node.next[node.high], step - 1);
}private Node getLast(Node node) {int high node.high;while (node.next[high] ! null) {node node.next[high];}return node;
}同时发现最左侧有一些数字极低值优化setNewHead方法 private void setNewHead(Node newHead, Node head) {newHead.high head.high;newHead.next[0] head;head.pre[0] newHead;head.high 0;for (int i 1; i newHead.high; i) {Node next head.next[i];if(nextnull){break;}newHead.next[i] next;next.pre[i] newHead;}this.head newHead;}执行leetCode14ms
使用show方法 结果如下 数据超过我的想象百万级了 当然这不是完美的跳表比如我只在新增时判断是否需要抬高(resize),查询时没有可能出现某些节点运气不好查询就是很慢
完整代码包括test在下方
public class TiaoBIaoNewTest {static int i 0;public static void main(String[] args) {Skiplist skiplist new Skiplist();Random random new Random();for (i 0; i 1000000000; i) {skiplist.add(random.nextInt());}System.out.println();}static class Skiplist {static int max 10;class Node {Node[] next new Node[max];Node[] pre new Node[max];int high 0;int value;//最近一次走到这个节点的步数int step 0;int k 0;}Node head;int maxHigh 0;//1)先分割0级public Skiplist() {}public boolean search(int target) {if (head null) {return false;}if (head.value target) {return false;}Node node searchFloor(head, maxHigh, target);return node.value target;}int step 0;private Node searchFloor(Node node, int high, int target) {if (node.value target) {return node;}if (high -1) {return node;}while (node.next[high] ! null node.next[high].value target) {step;node node.next[high];node.step step;}return searchFloor(node, high - 1, target);}public void add(int num) {if (head null) {head new Node();head.value num;return;}if (num head.value) {Node newHead new Node();newHead.value num;setNewHead(newHead, head);return;}step 0;Node newNode new Node();newNode.value num;Node node searchFloor(head, maxHigh, num);setNext(node, newNode);if (step 3 * maxHigh) {resize(newNode);}}private void setNewHead(Node newHead, Node head) {newHead.high head.high;newHead.next[0] head;head.pre[0] newHead;head.high 0;for (int i 1; i newHead.high; i) {Node next head.next[i];if(nextnull){break;}newHead.next[i] next;next.pre[i] newHead;}this.head newHead;}public boolean erase(int num) {if (head null) {return false;}if (head.value num) {if (head.next[0] ! null head.next[0].value num) {removeNode(head.next[0]);} else {removeHead();}return true;}Node node searchFloor(head, maxHigh, num);if (node.value num) {removeNode(node);return true;}return false;}private void removeNode(Node node) {for (int i 0; i node.high; i) {Node pre node.pre[i];Node next node.next[i];if (next null) {pre.next[i] null;} else {pre.next[i] next;next.pre[i] pre;}}}private void removeHead() {if (head.next[0] null) {head null;}Node node head.next[0];node.high head.high;for (int i 1; i maxHigh; i) {if (head.next[i] ! null head.next[i] ! node) {node.next[i] head.next[i];head.next[i].pre[i] node;}}head node;}private void resize(Node node) {if (node.high maxHigh) {//最高层这个可以接受maxHigh;if (maxHigh max) {show();}node.high maxHigh;head.high maxHigh;head.next[maxHigh] node;node.pre[maxHigh] head;return;}//找前人Node pre getMoreHighPre(node);//不应该直接用node升级应该用node区间的中间值node middleNode(pre, node);node.high;//加入节点setNext(pre, node);node.step pre.step 1;if (node.step 3 * (maxHigh 1)) {resize(node);}}private Node middleNode(Node pre, Node node) {int high node.high;if (pre.next[high 1] null) {return getLast(node);}Node next pre.next[high 1];int left getLen(pre, node, node.high);int right getLen(node, next, node.high);if (left right) {return node;}if (left right) {return left(node, (left - right) / 2);} else {return right(node, (right - left) / 2);}}private int getLen(Node left, Node right, int high) {int step 0;while (left ! right) {left left.next[high];step;}return step;}private Node left(Node node, int step) {if (step 0) {return node;}return left(node.pre[node.high], step - 1);}private Node right(Node node, int step) {if (step 0) {return node;}return right(node.next[node.high], step - 1);}private Node getLast(Node node) {int high node.high;while (node.next[high] ! null) {node node.next[high];}return node;}private Node getMoreHighPre(Node node) {int high node.high;Node pre node.pre[high];while (pre.high high) {pre pre.pre[high];}return pre;}private void setNext(Node pre, Node node) {int high node.high;if (pre.next[high] null) {pre.next[high] node;node.pre[high] pre;} else {Node next pre.next[high];pre.next[high] node;node.pre[high] pre;node.next[high] next;next.pre[high] node;}}private void show() {System.out.println(总数i为出现越界);System.out.println(0级并设置k);head.k 0;int k 0;Node node head;while (node ! null) {node.k k;node node.next[0];}for (int i 3; i max; i) {System.out.println(i 级间隔);node head;Node next node.next[i];while (next ! null) {System.out.print(next.k - node.k ,);node next;next node.next[i];}System.out.println();}}Overridepublic String toString() {String s ;Node node head;while (node ! null) {s node.value ,;node node.next[0];}return s;}}
}2023-03-04补充 今日验证每个节点的搜索路径验证结果如下
总数5445676为出现越界
0级并设置k
9级最大step33
8级最大step35
7级最大step35
6级最大step35
5级最大step35
4级最大step36
3级最大step38
2级最大step39
1级最大step44
0级最大step58
平均step24.20 总数6749752为出现越界
0级并设置k
9级最大step31
8级最大step32
7级最大step34
6级最大step34
5级最大step36
4级最大step37
3级最大step39
2级最大step45
1级最大step47
0级最大step59
平均step24.38总数5829201为出现越界
0级并设置k
9级最大step32
8级最大step33
7级最大step35
6级最大step35
5级最大step37
4级最大step38
3级最大step41
2级最大step46
1级最大step49
0级最大step62
平均step24.40最大step也只是60左右之所以不是30之前也说了是因为没有对查询操作进行提高判断操作(加了判断有可能反而导致查询减慢)个人也觉得没必要平均的查询步骤是24
进行局部修改当出现待提高node的左相邻节点本身高度就够情况下提高左节点(防止较低层级节点密集) 如下 private void resize(Node node) {if (node.high maxHigh) {//最高层这个可以接受maxHigh;if (maxHigh max) {show();}node.high maxHigh;head.high maxHigh;head.next[maxHigh] node;node.pre[maxHigh] head;return;}//找前人Node pre getMoreHighPre(node);//不应该直接用node升级应该用node区间的中间值node middleNode(pre, node);if(pre.next[node.high]node){//升自己不如升preresize(pre);return;}node.high;//加入节点setNext(pre, node);node.step pre.step 1;if (node.step 3 * (maxHigh 1)) {resize(node);}}验证结果如下
总数11386207为出现越界
0级并设置k
9级最大step32
8级最大step32
7级最大step36
6级最大step37
5级最大step38
4级最大step39
3级最大step41
2级最大step42
1级最大step52
0级最大step62
平均step24.78总数13122318为出现越界
0级并设置k
9级最大step30
8级最大step32
7级最大step37
6级最大step38
5级最大step39
4级最大step41
3级最大step42
2级最大step43
1级最大step49
0级最大step63
平均step25.30 总数11352711为出现越界
0级并设置k
9级最大step28
8级最大step30
7级最大step31
6级最大step32
5级最大step35
4级最大step37
3级最大step39
2级最大step42
1级最大step46
0级最大step59
平均step25.09最大步骤没有明显增加平均步骤从24增加至25查询会些许减慢但是可容纳数据量从600w左右提升至1000w以上提升明显 以上只是个人实现的跳表肯定会有问题欢迎大家一起讨论
