DS Library from Scratch

কেন এই প্রজেক্ট

Python programmer হিসেবে আপনি প্রতিদিন list আর dict ব্যবহার করছেন, কিন্তু ভেতরে কী চলে সেটা কোনোদিন দেখতে হয় না। Arrays-and-dynamic-arrays লেসনে দেখেছি capacity শেষ হলে কী হয়, Hash-tables লেসনে দেখেছি collision কীভাবে probe করে সামলায় — সবই ছিল অন্য কারো লেখা কোডের উপর গল্প। এই প্রজেক্টে নিয়ম কঠোর: list আর dict storage হিসেবে নিষিদ্ধ — শুধু fixed-size array (array module বা bytearray) দিয়ে চারটা ডেটা স্ট্রাকচার বানাতে হবে, আর প্রতিটার জন্য stdlib-এর বিপরীতে benchmark দিতে হবে।

আর সবচেয়ে জরুরি যে শিক্ষা: big-O notation asymptotic — n=১০০-তে constant factor আর cache behavior-ই খেলা জেতে। আপনার AVL tree সম্ভবত lookup-এ stdlib dict-কে হারবে, ঠিক তেমন আপনার Vector নির্দিষ্ট workload-এ list-কে ছুঁয়ে ফেলবে। কেন হারলেন, কোথায় জিতলেন — এই প্রশ্নের উত্তর বের করাই এই প্রজেক্টের আসল কাজ, কোড লেখা তার অর্ধেক।

ধাপে ধাপে

১. Vector — capacity আর growth

import array

class Vector:
    def __init__(self):
        self._cap = 4
        self._n = 0
        self._buf = array.array('q', [0]) * self._cap   # fixed-size buffer

    def _grow(self):
        new = array.array('q', [0]) * (self._cap * 2)
        for i in range(self._n):
            new[i] = self._buf[i]
        self._buf = new
        self._cap *= 2

    def append(self, x):
        if self._n == self._cap:
            self._grow()
        self._buf[self._n] = x
        self._n += 1

Amortized analysis লেসনের হিসাব এখানে কাগজে-কলমে মেলে: n টা element ঢোকাতে মোট copy = n + 2 + 4 + … + n/2 ≈ 2n, তাই per-append average constant। যাচাই করুন — _grow()-এ একটা counter বাড়ান, ১০ লাখ append-এ counter কত দেখায়?

Checkpoint: initial cap 4 হলে 1,000,000 append-এ resize হবে ঠিক 18 বার (log₂(250k))। আপনার counter এর সঙ্গে মিললো তো growth বোঝা গেছে।

২. HashMap — probing আর tombstone

Open addressing-এ delete-ই আসল মাথাব্যথা। Cell খালি করে দিলে তার পরের chain-এ বসা key আর কোনোদিন খুঁজে পাওয়া যাবে না — তাই tombstone:

EMPTY, TOMBSTONE = object(), object()

class HashMap:
    def get(self, key):
        i = hash(key) % self._cap
        while True:
            slot = self._slots[i]
            if slot is EMPTY:
                return None              # chain শেষ — নেই
            if slot is not TOMBSTONE and slot[0] == key:
                return slot[1]
            i = (i + 1) % self._cap      # linear probe

    def delete(self, key):
        i = self._find_slot(key)
        if i is not None:
            self._slots[i] = TOMBSTONE   # মুছবেন না — ঢেকে রাখুন

দুটো classic bug নিজেই ঘটিয়ে দেখুন:

Tombstone-কে EMPTY করে delete করলে কিছু key হঠাৎ হারিয়ে যায়।
Resize-এ load factor হিসাবে শুধু live entry ধরলে tombstone জমতে জমতে probe length আকাশছোঁয়া — resize-এর threshold-এ tombstone-ও গুনুন।

Resize-এ সব live key rehash হয়, tombstone মরে যায় — এই পার্থক্যটা টেস্টে ধরুন।

৩. AVL — insert + rotation

Recursive insert প্রতিটা subtree-র root return করে, ফেরার পথে height আর balance update:

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update_height(node)
    bf = balance_factor(node)          # h(right) - h(left)
    if bf > 1:
        if key > node.right.key:       # RR → single left
            return rotate_left(node)
        node.right = rotate_right(node.right)   # RL → double
        return rotate_left(node)
    if bf < -1:                        # LL / LR mirror image
        ...
    return node

rotate_left/rotate_right-এ child pointer swap-ই সব — কাগজে আঁকুন, কোডে সেটার অনুবাদ।

Checkpoint: property-based test — প্রতিটা insert-এর পরে তিনটা invariant যাচাই করুন: (a) BST order ঠিক (inorder sorted), (b) প্রতিটা node-এ |balance factor| ≤ 1, (c) stored height = computed height। Random ৫,০০০ insert-এ একবারও ভাঙলে rotation logic-এ bug।

৪. MinHeap + heapsort

def sift_down(a, i, n):
    while True:
        smallest, l, r = i, 2*i+1, 2*i+2
        if l < n and a[l] < a[smallest]: smallest = l
        if r < n and a[r] < a[smallest]: smallest = r
        if smallest == i: return
        a[i], a[smallest] = a[smallest], a[i]
        i = smallest

Heapsort দুই phase-এ: পুরো array দিয়ে heap build (নিচের অর্ধেক থেকে sift-down, O(n)), তারপর max/min ঘুরিয়ে swap করে shrink — in-place, extra memory zero। Heap-priority-queues লেসনের sift দুটোই এখানে কাজে লাগবে। MinHeap দিয়ে descending order-এ sort হয় — ভাবুন কেন।

Checkpoint: heapsort output sorted, আর প্রতিটা ধাপে parent ≤ child scan করে heap invariant ভাঙেনি — দুটো assertion আলাদা লিখুন।

৫. Benchmark harness — op-count + wall-clock

দুই ধরনের মাপ দুই টেবিলে:

class CountingVector(Vector):        # op-count instrumentation
    def __init__(self):
        super().__init__()
        self.copies = 0

    def _grow(self):
        self.copies += self._n       # grow-এ কয়টা element copy হলো
        super()._grow()

Wall-clock-এর জন্য: warmup run, তারপর একই কাজ k বার, median নিন — mean-এ outlier (GC pause, OS scheduler) টেবিল নষ্ট করে। Workload তিনটা আলাদা করুন: sequential insert, random lookup-heavy, mixed insert/delete। তারপর নিজের implementation আর stdlib পাশাপাশি:

operation (100k)	my Vector	Python list	my HashMap	dict
append/insert median	? ms	? ms	? ms	? ms
successful lookup median	? ms	? ms	? ms	? ms
p99 lookup	? ms	? ms	? ms	? ms
total copies/rehashes	?	?	?	?

p99 কলামটাই গল্প বলবে — median ভালো দেখলেও resize-এর মুহূর্তে latency spike ধরা পড়ে।

৬. Serialization

প্রতিটা স্ট্রাকচারের to_bytes() আর from_bytes():

import struct

def vector_to_bytes(v):
    out = struct.pack('<QQ', v._n, v._cap)     # header: n, cap
    return out + v._buf.tobytes()[:v._n * 8]

Little-endian, length prefix, versioned magic number — তিনটাই convention অভ্যাসের জন্য। Round-trip test: random data ঢেলে serialize → deserialize → প্রতিটা operation (get/probe/sort) আগের মতো এক ফল দেয় কি না। HashMap-এ tombstone সিরিয়ালাইজ হবে না — rebuild করে compact form-এ ফেলুন।

Checkpoint: from_bytes(vector_to_bytes(v)).to_bytes() == vector_to_bytes(v) — canonical encoding মানে এটা সবসময় true।

৭. Fuzz vs oracle

Random operation sequence দুই জগতে একসঙ্গে চালান — আপনার structure আর oracle (stdlib dict/set/sorted list):

rng = random.Random(42)
mine, oracle = HashMap(), {}
for step in range(100_000):
    key = rng.randrange(1000)          # ছোট keyspace → collision বেশি
    op  = rng.random()
    if op < 0.5:
        val = rng.randrange(10**6)
        assert mine.get(key) == oracle.get(key)
        mine.put(key, val); oracle[key] = val
    else:
        assert mine.get(key) == oracle.get(key)
        mine.delete(key); oracle.pop(key, None)

Mismatch ধরা পড়লে seed fixed থাকায় reproduce সহজ — ছোট failing case shrink করে রাখুন। Keyspace ইচ্ছে করে ছোট রাখুন, নইলে collision পাবেই না আর probe code path অপরীক্ষিত থেকে যাবে।

নিজেকে চ্যালেঞ্জ করুন

Growth factor 1.5 বনাম 2 বনাম 3 — wall-clock benchmark দিয়ে কোনটা কেন জেতে ব্যাখ্যা করুন (memory reuse বনাম copy count trade-off)
Linear probing বনাম robin-hood hashing — clustered workload-এ probe length distribution compare
Deletion-এ tombstone-এর বদলে backward-shift deletion — কোন edge case ভুল করলে chain ভাঙে?
AVL-এ range query keys(lo, hi) — inorder traversal prune করে
Iterator invalidation semantics — Vector resize হলে পুরনো index-based iterator-এর কী হবে, নিজের নিয়ম লিখুন আর enforce করুন (version counter)
mmap-backed Vector — file-কেই buffer বানিয়ে persistence free পাওয়া

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Amortized growth আর p99 spike	Latency-sensitive system design — tail latency এখান থেকেই শুরু
Open addressing + tombstone	Storage engine-এর memtable, Bloom filter-জাতীয় structure
Rotation + invariant test	Red-black tree, B-tree page split — একই “local repair” চিন্তা
Benchmark methodology	যেকোনো optimization claim — measurement ছাড়া argument নয়
Serialization round-trip	Wire protocol আর on-disk format design
Fuzz vs oracle	Differential testing — parser, VM, সবখানে একই কৌশল

মাইলস্টোন

আগে যা পড়া দরকার