- 2020-07-13 05:43
*views 7*- Data structure and algorithm
- Java
- NOSQL

I want to introduce jump watch to you naturally .

think , We

1） Search for a number in an ordered sequence

2） Or insert a number in the right place

How to do it ?

Is it simple

For the first operation , We can compare one by one , In an array, we can divide it into two parts , It's faster than a linked list

For the second operation , There's no use in two , Because to find the position, we have to move the position one by one in the array , The time complexity is still o(n).

So how can we invent a structure that can search and insert faster ?

You can put some marks on it ：

So we connect the markers , When searching for a number, start with the tag. If the next tag is larger than itself, go down , Because it's not going to meet the requirements .

For example, we need to search 18：

Because it can span many numbers at a time , Naturally, it's faster .

Since you can mark it , We can improve it , Choose some numbers and mark them again ：

So we search 20 That's true ：

In the end, we can mark many layers , We start at the top , You can skip a lot of numbers at a time （ It's still on the right. When it's big, go down ）.

For example, search 26：

Best case scenario , That is, the marks on each layer are reduced by half , So you get to the top and search down , In fact, it's no different from two points , We linked the bottom with a list , Inserting an element does not require moving the element , The so-called watch skipping is more than half done .

Now the problem is , We have a new number , How many layers should it be marked ?

（ At first, there was not a single number , So it solved the problem , We can always update it with this strategy ）

The answer is ..... iQuarters , Look at your face .

I was a little surprised , I thought there would be some very strong mathematical algorithms , Can guarantee a very good search efficiency , I think too much .

We have a new number , There's half the probability of a mark , There's a half chance you can't play .

For a number with a layer of marks , We are still this way , It has a half chance of marking up again , Cycle in turn .

So the probability of reaching each layer is less than half .

The number of nodes in each layer can be maintained in good efficiency （ The most perfect is to achieve a two-point effect ）

Analyze it again , In fact, for the same number ：

wait ..

There's no need to use pointers all the time , Because we know , Finding a number through a pointer is much slower than subscript .

So all the marks of the same number , There's no need to use a pointer , Low efficiency, not easy to maintain , Use one list Save it .

such , We design a structure of all the marks of a number ：

public static class SkipListNode { public Integer value;// Value of itself public

ArrayList<SkipListNode> nextNodes; // An array of nodes pointing to the next element , The length depends on the face . public

SkipListNode(Integer value) { this.value = value; nextNodes = new

ArrayList<SkipListNode>(); } }

take integer Compare the operation of encapsulation ：

private boolean lessThan(Integer a, Integer b) { return a.compareTo(b) < 0; }

private boolean equalTo(Integer a, Integer b) { return a.compareTo(b) == 0; }

Find the node that should turn down in this layer ：

// Returns the node at a given level with highest value less than e private

SkipListNode findNext(Integer e, SkipListNode current, int level) {

SkipListNode next = current.nextNodes.get(level); while (next != null) {

Integer value = next.value; if (lessThan(e, value)) { // e < value break; }

current = next; next = current.nextNodes.get(level); } return current; }

In this way, we can write down a method to find them layer by layer , And packaged into find(Integer e) The form of ：

// Returns the skiplist node with greatest value <= e private SkipListNode

find(Integer e) { return find(e, head, maxLevel); } // Returns the skiplist

node with greatest value <= e // Starts at node start and level private

SkipListNode find(Integer e, SkipListNode current, int level) { do { current =

findNext(e, current, level); } while (level-- > 0); return current; }

The method just now is to find the maximum value less than or equal to the target , If the value found is equal to the target , This target exists in the skip table . Otherwise it doesn't exist .

public boolean contains(Integer value) { SkipListNode node = find(value);

return node != null && node.value != null && equalTo(node.value, value); }

Now we can add a new point , Pay attention to the marking of each layer ：

public void add(Integer newValue) { if (!contains(newValue)) { size++; int

level = 0; while (Math.random() < PROBABILITY) { level++;// How many layers can you see } while

(level > maxLevel) {// Greater than the current maximum number of layers head.nextNodes.add(null);// Direct connect system maximum maxLevel++; }

SkipListNode newNode = new SkipListNode(newValue); SkipListNode current =

head;// Previous node , That is to say, the goal should be inserted current after do {// Each layer can be marked before it goes down , It is to insert a new node into the linked list current =

findNext(newValue, current, level); newNode.nextNodes.add(0,

current.nextNodes.get(level)); current.nextNodes.set(level, newNode); } while

(level-- > 0); } }

The same is true of deletion

public void delete(Integer deleteValue) { if (contains(deleteValue)) {

SkipListNode deleteNode = find(deleteValue); size--; int level = maxLevel;

SkipListNode current = head; do {// It is an operation of deleting nodes in a linked list current =

findNext(deleteNode.value, current, level); if (deleteNode.nextNodes.size() >

level) { current.nextNodes.set(level, deleteNode.nextNodes.get(level)); } }

while (level-- > 0); } }

As a container ,Iterator Is that necessary , There must be something in it hasNext and next bar ?

public static class SkipListIterator implements Iterator<Integer> { SkipList

list; SkipListNode current; public SkipListIterator(SkipList list) { this.list

= list; this.current = list.getHead(); } public boolean hasNext() { return

current.nextNodes.get(0) != null; } public Integer next() { current =

current.nextNodes.get(0); return current.value; } }

We're done with this watch skipping .

What about real work , We don't normally let it go to infinite levels , If there is a number, its popularity explosion, random number rush to 10000 layers ?

So it includes redis Some hop table implementation in , There is a maximum number of layers .

There seems to be nothing else .

Finally, post all the codes .

import java.util.ArrayList; import java.util.Iterator; public SkipListDemo {

public static class SkipListNode { public Integer value; public

ArrayList<SkipListNode> nextNodes; public SkipListNode(Integer value) {

this.value = value; nextNodes = new ArrayList<SkipListNode>(); } } public

static class SkipListIterator implements Iterator<Integer> { SkipList list;

SkipListNode current; public SkipListIterator(SkipList list) { this.list =

list; this.current = list.getHead(); } public boolean hasNext() { return

current.nextNodes.get(0) != null; } public Integer next() { current =

current.nextNodes.get(0); return current.value; } } public static class

SkipList { private SkipListNode head; private int maxLevel; private int size;

private static final double PROBABILITY = 0.5; public SkipList() { size = 0;

maxLevel = 0; head = new SkipListNode(null); head.nextNodes.add(null); } public

SkipListNode getHead() { return head; } public void add(Integer newValue) { if

(!contains(newValue)) { size++; int level = 0; while (Math.random() <

PROBABILITY) { level++; } while (level > maxLevel) { head.nextNodes.add(null);

maxLevel++; } SkipListNode newNode = new SkipListNode(newValue); SkipListNode

current = head; do { current = findNext(newValue, current, level);

newNode.nextNodes.add(0, current.nextNodes.get(level));

current.nextNodes.set(level, newNode); } while (level-- > 0); } } public void

delete(Integer deleteValue) { if (contains(deleteValue)) { SkipListNode

deleteNode = find(deleteValue); size--; int level = maxLevel; SkipListNode

current = head; do { current = findNext(deleteNode.value, current, level); if

(deleteNode.nextNodes.size() > level) { current.nextNodes.set(level,

deleteNode.nextNodes.get(level)); } } while (level-- > 0); } } // Returns the

skiplist node with greatest value <= e private SkipListNode find(Integer e) {

return find(e, head, maxLevel); } // Returns the skiplist node with greatest

value <= e // Starts at node start and level private SkipListNode find(Integer

e, SkipListNode current, int level) { do { current = findNext(e, current,

level); } while (level-- > 0); return current; } // Returns the node at a given

level with highest value less than e private SkipListNode findNext(Integer e,

SkipListNode current, int level) { SkipListNode next =

current.nextNodes.get(level); while (next != null) { Integer value =

next.value; if (lessThan(e, value)) { // e < value break; } current = next;

next = current.nextNodes.get(level); } return current; } public int size() {

return size; } public boolean contains(Integer value) { SkipListNode node =

find(value); return node != null && node.value != null && equalTo(node.value,

value); } public Iterator<Integer> iterator() { return new

SkipListIterator(this); }

/******************************************************************************

* Utility Functions *

******************************************************************************/

private boolean lessThan(Integer a, Integer b) { return a.compareTo(b) < 0; }

private boolean equalTo(Integer a, Integer b) { return a.compareTo(b) == 0; } }

public static void main(String[] args) { } }

Technology

Daily Recommendation

views 4

views 3

views 3

©2019-2020 Toolsou All rights reserved,

Final review of database ： Summary of comprehensive application questions Laplance operator （ Second derivative ） Simple learning of computer composition principle pyqt Button call python program _PyQt： Link button to function in program How much can you go up once you change jobs ? Today, I saw the ceiling of job hopping python in str Function usage _python in str Usage Summary of built-in functions MySQL trigger web The server nginx---linux Installation and deployment C++ Chapter V polymorphism exercises ：（ It's coming to an end ）python Check built-in functions , How to check python Built in function