র‍্যান্ডমাইজড অ্যালগরিদম৭ মিনিট পড়া

স্কিপ লিস্ট (Skip List)

প্রোবাবিলিস্টিক বিএসটি-র বিকল্প — প্রত্যাশিত সময় O(log n)
search:দ্রুত · প্রত্যাশিত O(log n)insert:দ্রুত · প্রত্যাশিত O(log n)space:প্রত্যাশিত O(n log n)

কল্পনা করুন একটি বিশাল বুকশেলফ যেখানে ১,০০০টি বই টাইটেল বা নাম অনুযায়ী সাজানো আছে। একটি নির্দিষ্ট বই খুঁজে পেতে, আপনি হয়তো একদম বাঁ-দিক থেকে শুরু করে প্রতিটি নাম চেক করতে পারেন — যা হলো O(n) পদ্ধতি। অথবা আপনি একটি স্মার্ট সিস্টেম ব্যবহার করতে পারেন।

বুকশেলফের কিছু বইয়ে একটি লম্বা রঙিন ট্যাব লাগানো আছে। সবচেয়ে লম্বা ট্যাবগুলো (লাল রঙের) প্রতি ১২৮তম বইকে নির্দেশ করে। মাঝারি ট্যাবগুলো (নীল রঙের) প্রতি ১৬তম বইকে নির্দেশ করে। এবং ছোট ট্যাবগুলো (সবুজ রঙের) প্রতি দ্বিতীয় বা অল্টারনেট বইকে নির্দেশ করে। কোনো বই খুঁজতে হলে, আপনি সবচেয়ে লম্বা ট্যাব থেকে খোঁজা শুরু করবেন — অর্থাৎ বড় বড় ধাপে লাফ দেবেন — তারপর ধীরে ধীরে গন্তব্যের কাছাকাছি পৌঁছানোর জন্য ক্রমাগত ছোট ট্যাবগুলো ব্যবহার করবেন। এটাই হলো স্কিপ লিস্ট (skip list) এর ধারণা।

একটি স্কিপ লিস্টে, প্রতিটি উপাদান লেভেল 0-এর একটি সর্টেড লিঙ্কড লিস্টে অবস্থান করে। এরপর কিছু উপাদানকে প্রমোট করে লেভেল ১-এ নিয়ে যাওয়া হয় (যা তুলনামূলকভাবে ফাঁকা, অনেকটা "এক্সপ্রেস লেন" এর মতো), কিছু উপাদানকে লেভেল ২-এ নিয়ে যাওয়া হয়, এবং এভাবেই চলতে থাকে। প্রতিটি লেভেল তার নিচের লেভেলের একটি সাবসেট বা অংশবিশেষ, এবং উচ্চতর লেভেলগুলো অনেক বড় অংশে লাফ দিতে সাহায্য করে।

সম্ভাবনা-ভিত্তিক প্রমোশন নিয়ম (The Probabilistic Promotion Rule)

স্কিপ লিস্টের সবচেয়ে সুন্দর দিকটি হলো: এটিকে ব্যালান্স বা ভারসাম্যপূর্ণ রাখার জন্য আপনার কোনো জটিল রোটেশন লজিকের (ঘূর্ণন বা পাল্টানোর নিয়মের) প্রয়োজন নেই। নতুন একটি উপাদান ইনসার্ট করার সময়, আপনি শুধু একটি কয়েন বা মুদ্রা টস করবেন। যদি হেড (Heads) পড়ে? তাহলে সেটিকে পরবর্তী লেভেলে প্রমোট করুন। যতক্ষণ না টেইল (Tails) পড়ছে (অথবা সর্বোচ্চ লেভেলের ক্যাপে না পৌঁছাচ্ছে) ততক্ষণ টস করতে থাকুন। এর মানে হলো:

  • প্রায় ১/২ অংশ উপাদান লেভেল ১-এ থাকে
  • প্রায় ১/৪ অংশ থাকে লেভেল ২-এ
  • প্রায় ১/৮ অংশ থাকে লেভেল ৩-এ
  • ... এভাবেই চলতে থাকে

যেকোনো নোডের প্রত্যাশিত উচ্চতা হলো ২, এবং মোট পয়েন্টারের প্রত্যাশিত সংখ্যা হলো O(n)। কোনো ধরনের জটিল বুককিপিং বা ব্যবস্থাপনা ছাড়াই কাঠামোটি গড়ে (on average) ভারসাম্যপূর্ণ থাকে।

সার্চ যেভাবে কাজ করে (How Search Works)

টপ-লেফট সেন্টিনেল নোড (top-left sentinel node) (সর্বোচ্চ লেভেলের হেডার) থেকে শুরু করুন। যতক্ষণ সামনের নোডের কী (key)-এর মান আপনার লক্ষ্যের চেয়ে ছোট হবে, ততক্ষণ ডানদিকে এগোতে থাকুন। যখন মনে হবে আপনি লক্ষ্য পার হয়ে যাচ্ছেন, তখন এক লেভেল নিচে নেমে আসুন। আপনি লেভেল 0-তে না পৌঁছানো পর্যন্ত এটি পুনরাবৃত্তি করুন এবং এরপর বর্তমান নোডটি চেক করে দেখুন। প্রতিটি লেভেল বাকি থাকা সার্চ স্পেসকে প্রায় অর্ধেক করে দেয় — তাই সাধারণত একটি নোড খুঁজে পেতে যে কয়টি লেভেল পার করতে হয় তা হলো O(log n)।

ইনসার্ট এবং ডিলিট যেভাবে কাজ করে (How Insert and Delete Work)

ইনসারশনের জন্য: প্রথমে সার্চ করুন, এবং প্রতিটি লেভেলেই পূর্বসূরি বা প্রিডেসেসরকে (predecessor) রেকর্ড করে রাখুন (যে নোডগুলো থেকে আপনি নিচে নেমেছিলেন)। এরপর কয়েন টসের মাধ্যমে নির্ধারিত k সংখ্যক লেভেলের জন্য, লেভেল-0 থেকে লেভেল-k পর্যন্ত প্রতিটি প্রিডেসেসরের পর নতুন নোডটি ইনসার্ট বা যুক্ত করুন। ডিলিট করার জন্য: সমস্ত লেভেলে প্রিডেসেসর খুঁজুন এবং তারপর নোডটিকে সেই অনুযায়ী সরিয়ে ফেলুন। উভয় অপারেশনই ঠিক সার্চের মতোই O(log n) প্রত্যাশিত সময় (expected cost) নেয়।

স্কিপ লিস্ট বনাম ব্যালান্সড বিএসটি (Skip Lists vs Balanced BSTs)

এভিএল ট্রি (AVL trees) বা রেড-ব্ল্যাক ট্রি (Red-Black trees) অত্যন্ত নিখুঁত রোটেশনের মাধ্যমে সবচেয়ে খারাপ ক্ষেত্রে বা ওয়ার্স্ট-কেস (worst case) O(log n)-এর নিশ্চয়তা দেয়। অন্যদিকে স্কিপ লিস্টগুলো রেন্ডমনেস বা দৈবচয়ন ব্যবহারের কারণে প্রত্যাশিত (expected) O(log n) প্রদান করে — যার কোড অনেক সহজ, কিন্তু এর কোনো ওয়ার্স্ট-কেস গ্যারান্টি নেই (যদিও উল্লেখযোগ্য বিচ্যুতির সম্ভাবনা বাস্তবে খুবই নগণ্য)।

স্কিপ লিস্টের আসল সুবিধাটি লুকিয়ে আছে কনকারেন্ট প্রোগ্রামিং (concurrent programming)-এর ক্ষেত্রে। ট্রি রোটেশনের সময় অনেকগুলো নোড একসঙ্গে পাল্টাতে হয়, যার কারণে ট্রির বড় অংশে লক (lock) করতে হয়। কিন্তু স্কিপ লিস্ট ইনসার্শনের ক্ষেত্রে শুধুমাত্র স্থানীয় কয়েকটি পয়েন্টার (local pointers) পরিবর্তন করতে হয়, যা লক-ফ্রি ইমপ্লিমেন্টেশনকে অনেক সহজ করে তোলে। ঠিক এই কারণেই জাভা (Java)-এর ConcurrentSkipListMap স্কিপ লিস্ট ব্যবহার করে।

দ্রষ্টব্য: স্কিপ লিস্ট আপনাকে লিঙ্কড লিস্টের সরলতা এবং ব্যালান্সড ট্রির গতির সমন্বয়ে সর্টেড-সেট অপারেশনগুলো (সার্চ, ইনসার্ট, ডিলিট, রেঞ্জ কোয়েরি) ব্যবহারের সুবিধা দেয় — কোনো রোটেশন নেই, কোনো কালার ফ্ল্যাগ নেই, এবং কোনো হাইট বা উচ্চতা গণনারও প্রয়োজন নেই। প্রতিটি লেভেলের জন্য শুধু একবার কয়েন টস করাই যথেষ্ট।

স্কিপ লিস্ট ইমপ্লিমেন্টেশন

import random


MAX_LEVEL = 4
P = 0.5


class Node:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)


class SkipList:
    def __init__(self):
        self.head = Node(float('-inf'), MAX_LEVEL)
        self.level = 0


    def random_level(self):
        lvl = 0
        while random.random() < P and lvl < MAX_LEVEL:
            lvl += 1
        return lvl


    def insert(self, key):
        update = [None] * (MAX_LEVEL + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].key < key:
                curr = curr.forward[i]
            update[i] = curr
        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl
        new_node = Node(key, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node


    def search(self, key):
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].key < key:
                curr = curr.forward[i]
        curr = curr.forward[0]
        return curr and curr.key == key


sl = SkipList()
for x in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]:
    sl.insert(x)
print(sl.search(19))   # True
print(sl.search(15))   # False
Output
True
False

Complexity

🔍 সার্চ (Search)
প্রতিটি লেভেল বাকি থাকা উপাদানকে প্রায় অর্ধেক করে দেয় — তাই সাধারণত প্রত্যাশিত ভিজিট করা লেভেলের সংখ্যা O(log n) হয়
গড়ে O(log n) O(log n)
➕ ইনসার্ট (Insert)
সার্চ করার খরচের সাথে প্রতিটি প্রমোটেড লেভেলে পয়েন্টার আপডেট করার জন্য O(1) যোগ হয় — কয়েন টস করেই উচ্চতা নির্ধারণ করা হয়
গড়ে O(log n) O(log n)
🗑️ ডিলিট (Delete)
সব লেভেলে পূর্বসূরিদের (predecessors) খুঁজে বের করে পয়েন্টার সরিয়ে ফেলা — খরচ ঠিক সার্চের মতোই
গড়ে O(log n) O(log n)
💾 মেমরি বা স্পেস (Space)
প্রতিটি নোড গড়ে মোট ২টি লেভেলে অবস্থান করে — প্রত্যাশিত স্পেস O(n), তবে ক্যাপ থাকলে O(n log n) হতে পারে
সাধারণ লিস্টের চেয়ে বেশি O(n log n)

ছোট কুইজ

একটি স্কিপ লিস্টে নতুন একটি কী (key) ইনসার্ট করার সময়, নোডটি কতগুলো লেভেল বা স্তর পর্যন্ত যাবে তা আপনি কীভাবে নির্ধারণ করবেন?

পড়া চালিয়ে যান