অ্যালগরিদম তুলনা — বাস্তব বেঞ্চমার্কিং

১ · কেন Wall-Clock সময় নয়, অপারেশন কাউন্ট

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

২ · ওয়ার্কড উদাহরণ — Bubble Sort ইনস্ট্রুমেন্টেড

Bubble sort-এর তত্ত্ব বলে সবচেয়ে খারাপ কেসে (ইতিমধ্যে উল্টো-সাজানো ইনপুট) তুলনা সংখ্যা হলো: $$\text{comparisons} = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$$ এটি $\Theta(n^2)$ — L39-এর কোয়াড্রেটিক ক্লাস। এই সূত্রটি এম্পিরিক্যালি (বাস্তবে চালিয়ে) যাচাই করি চারটি বিভিন্ন ইনপুট সাইজে — $n=10, 20, 40, 80$।

def bubble_sort_count(arr):
    a = list(arr)
    n = len(a)
    comparisons = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            comparisons += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a, comparisons

print(f"{'n':>4} | {'comparisons':>12} | {'n^2':>8} | {'comparisons/n^2':>16}")
for n in [10, 20, 40, 80]:
    arr = list(range(n, 0, -1))   # worst case — সম্পূর্ণ উল্টো ক্রমে সাজানো ইনপুট
    sorted_arr, comps = bubble_sort_count(arr)
    ratio = comps / (n ** 2)
    print(f"{n:>4} | {comps:>12} | {n**2:>8} | {ratio:>16.4f}")

    # সূত্র n(n-1)/2-এর সাথে মিলিয়ে দেখা
    expected = n * (n - 1) // 2
    assert comps == expected, f"n={n}-এ সূত্রের সাথে মিলছে না!"

print("\nসব মান n(n-1)/2 সূত্রের সাথে হুবহু মিলে গেছে — যাচাই সম্পন্ন।")

৩ · তুলনা: Python-এর বিল্ট-ইন sorted()

Python-এর বিল্ট-ইন sorted() Timsort ব্যবহার করে, যার তাত্ত্বিক জটিলতা $\Theta(n\log n)$ (L31-এ merge sort-এর জন্য দেখা ক্লাস)। যেহেতু sorted()-এর অভ্যন্তরীণ তুলনা C ভাষায় বাস্তবায়িত, আমরা সরাসরি এর ভেতরের প্রতিটি তুলনা গুনতে পারি না — কিন্তু ধারণাগতভাবে: $n=80$-এ bubble sort-এর প্রায় $3160$টি তুলনা লাগে (উপরের কোড দেখুন), যেখানে $n\log_2 n \approx 80\times6.3\approx504$ — অর্থাৎ Timsort তাত্ত্বিকভাবে প্রায় ৬ গুণ কম তুলনায় কাজ শেষ করবে। এটাই দেখায় কেন সঠিক জটিলতা ক্লাস বাছাই বাস্তবে সত্যিকারের পার্থক্য তৈরি করে, এমনকি n তুলনামূলক ছোট থাকলেও।

৪ · তাত্ত্বিক বনাম এম্পিরিক্যাল বিশ্লেষণ

পুরো M8 মডিউল জুড়ে আমরা তাত্ত্বিক বিশ্লেষণ শিখেছি — একটি অ্যালগরিদমের কোড না চালিয়েই, শুধু তার গঠন দেখে গাণিতিকভাবে বলে দেওয়া এটি asymptotically ($n\to\infty$) কেমন আচরণ করবে। এম্পিরিক্যাল বেঞ্চমার্কিং (এই পাঠ) ভিন্ন কাজ করে — বাস্তবে অ্যালগরিদম চালিয়ে নিশ্চিত করে তত্ত্ব সঠিক প্রমাণিত হচ্ছে কি না, এবং তত্ত্ব যা লুকিয়ে রাখে (কনস্ট্যান্ট ফ্যাক্টর, ছোট $n$-এ আচরণ) তা প্রকাশ করে। দুটোই প্রয়োজনীয় — তত্ত্ব দিক-নির্দেশনা দেয়, পরিমাপ তা নিশ্চিত করে।