ਇੱਕ skip list ਇੱਕ ਕ੍ਰਮਬੱਧ linked list ਹੈ ਜਿਸਨੂੰ ਕਈ "express lane" ਪੱਧਰਾਂ ਨਾਲ ਵਧਾਇਆ ਜਾਂਦਾ ਹੈ। ਉਪਰਲੀਆਂ ਪੱਧਰਾਂ ਕਈ ਨੋਡਸ ਨੂੰ ਛੱਡ ਦਿੰਦੀਆਂ ਹਨ, ਇਸ ਲਈ ਖੋਜ ਉਤਰਦੀ ਅਤੇ ਸੱਜੇ ਵੱਲ ਚਲੀ ਜਾਂਦੀ ਹੈ, O(log n) ਪ੍ਰਤੀਸ਼ਤਬੱਧ ਸਮਾਂ ਪ੍ਰਾਪਤ ਕਰਦੀ ਹੈ — ਸੰਤੁਲਿਤ ਰੁੱਖ ਲਈ ਇੱਕ ਸੰਭਾਵ਼ਨਾਤਮਕ, ਸਰਲ ਵਿਕਲਪ ਜਾਂ।
L3: head ------------------------> 30 -------> NIL
L2: head ----------> 17 ---------> 30 -------> NIL
L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL
L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list)
ਹਰੇਕ ਨੋਡ ਨੂੰ ਸੰਭਾਵਨਾ p ਦੇ ਨਾਲ ਉੱਪਰਲੀਆਂ ਪੱਧਰਾਂ ਤਕ ਅੱਗੇ ਵਧਾਇਆ ਜਾਂਦਾ ਹੈ (ਅਕਸਰ 0.5), ਇਸ ਲਈ ਔਸਤਨ ਹਰੇਕ ਪੱਧਰ ਦੇ ਹੇਠਲਿਆਂ ਅੱਧੇ ਨੋਡਸ ਹੁੰਦੇ ਹਨ।
search(25): start top-left, move RIGHT while next <= target,
else drop DOWN a level. Repeat to level 0.
import random
def random_level(p=0.5, max_level=16):
lvl = 1
while random.random() < p and lvl < max_level:
lvl += 1 # coin flips decide a node's height
return lvl
| ਓਪਰੇਸ਼ਨ | ਪ੍ਰਤੀਸ਼ਤਬੱਧ | ਸਪੇਸ |
|---|---|---|
| ਖੋਜ | O(log n) | O(n) |
| ਸ਼ਾਮਿਲ ਕਰੋ / ਹਟਾਓ | O(log n) | — |
ConcurrentSkipListMap ਵਿੱਚ ਵਰਤੇ ਜਾਂਦੇ ਹਨ)।Skip lists ਰੁੱਖ-ਵਰਗੇ O(log n) ਕ੍ਰਮਬੱਧ ਓਪਰੇਸ਼ਨਾਂ ਨੂੰ ਬਹੁਤ ਘੱਟ ਕੋਡ ਅਤੇ ਸਹਜ lock-free ਸਮਕਾਲੀਨਤਾ ਦੇ ਨਾਲ ਵਿਤਰਤ ਕਰਦੇ ਹਨ, ਜੋ Redis ਜਿਹੀਆਂ ਅਸਲ ਪ੍ਰਣਾਲੀਆਂ ਉਹਨਾਂ ਨੂੰ ਚੁਣਦੀਆਂ ਹਨ।
ਉਹ ਜਟਿਲ ਨਿਰਣਾਤਮਕ ਸੰਤੁਲਨ ਲਾਜਿਕ ਨੂੰ ਬਦਲਣ ਲਈ randomization ਦੀ ਵਰਤੋਂ ਦੀ ਬਹੁਤ ਚੰਗੀ ਮਿਸਾਲ ਹਨ।