বাইনারি সার্চ-এর কোড

আজকে সকালে গো (Go) প্রোগ্রামিং ল্যাঙ্গুয়েজে একটু কোডিং প্র্যাকটিস করার জন্য বাইনারি সার্চ ফাংশন লিখলাম, তারপরে ইউনিট টেস্ট লিখলাম (টেবল ড্রিভেন টেস্ট)। তো এমন সময় আমার মনে হলো লাইব্রেরি ফাংশনগুলো কিভাবে ইমপ্লিমেন্ট করা, সেটা দেখা দরকার। তো গো এর লাইব্রেরিতে যে বাইনারি সার্চ আছে, তার কোড (এবং ডকুমেন্টেশন) দেখে তো আমি মুগ্ধ!
এটা হচ্ছে গো-এর কোড:

func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
	h := i + (j-i)/2 // avoid overflow when computing h 
        if !f(h) { 
            i = h + 1 // preserves f(i-1) == false 
        } else { 
            j = h // preserves f(j) == true 
        } 
    } 
    return i
}

ওপরের কোডটুকু দেখলে আসলে পুরোপুরি বোঝা যাবে না কেন আমি এত মুগ্ধ। এই লিঙ্কে গেলে বিষয়টা আরো পরিষ্কার হবে: https://golang.org/src/sort/search.go। কোডের চেয়ে ডকুমেন্টেশন অনেক বেশি। আর এই বেশি ডকুমেন্টেশনসহ কোড হচ্ছে ১১৩ লাইন। কিন্তু বিষয় এখানেই শেষ নয়। আমার তারপরে চিন্তা আসল, আচ্ছা, এত সুন্দর কোড আর ডকুমেন্টেশন – এই কোডের টেস্ট কোড (ইউনিট টেস্ট) ওরা কিভাবে লিখল? তার জন্য চলে গেলাম এই লিঙ্কেঃ https://golang.org/src/sort/search_test.go। ১১৩ লাইনের search.go এর জন্য search_test.go তে আছে ১৬২ লাইন। এই দুইটা ফাইলের কোড এবং ডকুমেন্টেশন ঠিকমতো পড়লে শেখার আছে অনেক কিছুই।

তারপর চিন্তা করলাম, গো এর কোড এত সুন্দর, সি এর লাইব্রেরিতে এটা কিভাবে করা হয়েছে? গুগল সার্চ করে খুঁজে বের করলাম কোড।

void *
bsearch (register const void *key, const void *base0,
    size_t nmemb, register size_t size,
    register int (*compar)(const void *, const void *))
{
    register const char *base = (const char *) base0;
    register int lim, cmp;
    register const void *p;

    for (lim = nmemb; lim != 0; lim >>= 1) {
        p = base + (lim >> 1) * size;
        cmp = (*compar)(key, p);
        if (cmp == 0)
            return (void *)p;
        if (cmp > 0) {	/* key > p: move right */
            base = (const char *)p + size;
            lim--;
        } /* else move left */
    }
    return (NULL);
}

এই কোডটাও বেশ সুন্দর, গুছানো। ডকুমেন্টেশনও ভালো। আর পয়েন্টার দেখে ভয় পাওয়ার কারণ নাই (পয়েন্টার নিয়ে আমি কম্পিউটার প্রোগ্রামিং ২য় খণ্ড বইতে বিস্তারিত আলোচনা করেছি অনেক উদাহরণসহ)। তবে এখানে গিয়ে পুরো ফাইলটা না দেখলে এর মর্ম বোঝা যাবে না : https://github.com/gcc-mirror/gcc/blob/master/libiberty/bsearch.c

গো আর সি-এর কোড যেহেতু দেখলাম, পাইথনের কোডটাও দেখা যাক। তাই সেটাও সার্চ করে বের করে ফেললাম :

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

গো আর সি এর তুলনায় বেশ সহজ! তবে ডকুমেন্টেশন সংক্ষিপ্ত হলেও ভালো। এখানে গিয়ে পুরো কোড দেখা যাবে : https://github.com/python-git/python/blob/master/Lib/bisect.py

তারপরে ভাবলাম, আমার ব্লগের পাঠকদেরকে বিষয়টা জানানো যাক। আশা করি, বিশ্বমানের প্রোগ্রামারদের কোডের সঙ্গে পাঠকদের কিছুটা হলেও পরিচয় করিয়ে দিতে পেরেছি। কোডিং সঠিক হোক, কোড সুন্দর হোক।

ইউনিট টেস্টিং

সফটওয়্যার ডেভেলাপমেন্টের একটি গুরুত্বপূর্ণ ধাপ হচ্ছে কোডিং। তো এই কোডিং করার আগে রিকোয়ারমেন্ট সংগ্রহ ও অ্যানালাইসিস করা হয়, আর্কিটেকচার ডিজাইন করা হয়, কোন প্ল্যাটফর্ম, টুলস্ ও প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যবহার করা হবে, সেই সিদ্ধান্ত নেওয়া হয়। তারপরে প্রজেক্ট যদি বড় হয়, তখন আরো কিছু ধাপ (যেমন ক্লাস ও ইন্টারঅ্যাকশন ডিজাইন) পার হয়ে কোডিং শুরু করা হয়। এখন কোড লেখার সময় একটি গুরুত্বপূর্ণ ব্যাপার হচ্ছে ইউনিট টেস্টিং যেখানে বিভিন্ন ইউনিট টেস্ট করা হয়। এখন ইউনিট মানে কী? ইংরেজি Unit শব্দের বাংলা অর্থ হচ্ছে একক। একটা মডিউলকে একক ধরা যায়, ইন্টারফেসকে একক ধরা যায়, ক্লাসকে একক ধরা যায়, আবার ফাংশনকেও একক ধরা যায়। আমি এখন কথা বলব ফাংশনকে একক ধরে টেস্ট কোড লেখার ব্যাপারে। আমরা যখন বড় প্রোগ্রাম লিখবো, তখন প্রতিটি আলাদা কাজকে আলাদা ফাংশনে লিখব এবং একটি ফাংশন কেবল একটি কাজই করবো। যদি কখনও দেখা যায় যে একটি ফাংশন একাধিক কাজ করছে, তখন বুঝতে হবে যে ফাংশনটি ভেঙ্গে ছোট ছোট ফাংশন লেখা প্রয়োজন। তো এই ফাংশন হচ্ছে ক্ষুদ্রতম ইউনিট এবং এই লেখার বাকি অংশে ইউনিট টেস্ট বলতে আমি এই ফাংশনগুলোর টেস্ট করাই বোঝাবো।

ইউনিট টেস্ট কিভাবে করে? ফাংশন লেখার পরে ওই ফাংশনের জন্য আলাদা একটি ফাইলে আরেকটি ফাংশন লিখতে হবে যেটি বিভিন্ন ইনপুট প্যারামিটারের মাধ্যমে ওই ফাংশনকে কল করবে। তারপরে আউটপুট মিলিয়ে দেখতে হবে যে আমরা যেই আউটপুট আশা করছি আর ফাংশনটি যেই আউটপুট দিচ্ছে – দুটি সমান কী না। ব্যাস, আমাদের ইউনিট টেস্ট হয়ে গেল। ইন্ডাস্ট্রিতে প্রচলিত সব প্রোগ্রামিং ল্যাঙ্গুয়েজেই ইউনিট টেস্ট সহজ করার জন্য বিভিন্ন প্যাকেজ তৈরি করা থাকে। যদিও এসব প্যাকেজ ব্যবহার না করেও ইউনিট টেস্ট করা যায়, যেহেতু প্যাকেজ তৈরি করে দেওয়া আছে, তাই প্যাকেজ ব্যবহার না করার কোনো কারণ নেই। আমরা এখন পাইথনে একটি সহজ উদাহরণ দেখবো।

পাইথনে unittest নামে একটি বিল্ট-ইন মডিউল রয়েছে যেটি ব্যবহার করে ইউনিট টেস্ট করা যায়। কিন্তু আমরা ব্যবহার করবো pytest কারণ এটি ব্যবহার করা অনেক বেশি সহজ। তবে এটি আলাদাভাবে ইনস্টল করতে হয়। কীভাবে ইনস্টল করতে হয়, সেটি ওদের অফিশিয়াল ডকুমেন্টশন থেকে দেখে নিতে হবে, এই লেখা পড়ার জন্য পাইটেস্ট ইনস্টল করার দরকার নেই, পরে করলেও হবে (কারণ এই লেখার উদ্দেশ্য হচ্ছে ইউনিট টেস্টিং সম্পর্কে প্রাথমিক ধারণা দেওয়া)। আরেকটি জিনিস জানতে হবে, সেটি হচ্ছে assert স্টেটম্যান্ট। assert এর পরে কোনো কিছু লিখলে পাইথন সেটা চালিয়ে দেখে এবং ফলাফল হয় True না হয় False হয়। ফলাফল False হলে পাইথন AssertionError এক্সেপশন দেয়।

ধরা যাক, আমাকে একটি প্রোগ্রাম লিখতে বলা হলো, যেটি ইনপুট হিসেবে একটি বছর নেবে এবং বছরটি লিপ ইয়ার কী না, সেটি বলে দেবে। লিপ ইয়ার হলে True আর লিপ ইয়ার না হলে False রিটার্ণ করবে। আমি জানি যে, কোনো সালকে যদি 4 দিয়ে ভাগ করলে ভাগশেষ শূণ্য হয়, তাহলে সেটি লিপ ইয়ার। তো আমি ঝটপট পাইথনে সেটি লিখে ফেললাম :

def is_leap_year(year):
        """This functon returns True if year is a leap year, returns False otherwise"""
        if year % 4 == 0:
                return True
        return False

এখন এই ফাংশনের জন্য ইউনিট টেস্ট লিখব :

def test_is_leap_year():
        assert is_leap_year(2016) == True
        assert is_leap_year(2015) == False

আমি আমার প্রোগ্রাম leapyear.py নামে সেভ করলাম। এখন pytest রান করাবো।

 tamimshahriar$ pytest leapyear.py 

======= test session starts========

platform darwin -- Python 3.5.1, pytest-3.0.3, py-1.4.31, pluggy-0.4.0

rootdir: /Users/tamimshahriar/work/practice/pypractice, inifile: 

collected 1 items 

leapyear.py .

======= 1 passed in 0.01 seconds =====

ওপরে দেখতে পাচ্ছি যে আমার টেস্ট ঠিকঠাকভাবে পাশ করেছে, কোনো সমস্যা নেই। এখন আমি খোঁজখবর নিয়ে জানলাম যে 2100 সাল নাকি আসলে লিপইয়ার না, কারণ সালটা যদি 100 দিয়ে বিভাজ্য হয়, সেটা 400 দিয়েও বিভাজ্য হতে হবে। তাহলে আমি এই টেস্ট কেইসটি আমার টেস্টে যোগ করে আবার টেস্ট রান করবো। এখন আমার টেস্ট ফাংশনটি হবে এরকম :

def test_is_leap_year():
        assert is_leap_year(2016) == True
        assert is_leap_year(2015) == False
        assert is_leap_year(2100) == False

এখন আবার টেস্ট রান করি : pytest leapyear.py, আউটপুট আসবে এরকম :

========= FAILURES ===========
_______ test_is_leap_year __________

    def test_is_leap_year():
        assert is_leap_year(2016) == True
        assert is_leap_year(2015) == False
>       assert is_leap_year(2100) == False
E     assert True == False
E     +  where True = is_leap_year(2100)

leapyear.py:10: AssertionError

===== 1 failed in 0.03 seconds =====

কোন টেস্ট কেইস ফেইল করেছে সেটা একটা তীরচিহ্ন দিয়ে দেখানো হয়েছে। এখন আমি আমার অরিজিনাল ফাংশনের কোড ঠিক করলে টেস্ট কেস পাশ করবে (পাঠকদের সেটি করার পরামর্শ দেওয়া হলো)।

ইউনিট টেস্ট করার সময় বিভিন্ন ধরনের কেস টেস্ট করা উচিত। ইউনিট টেস্টের সুবিধা হচ্ছে :

  • যে কেউ কোড দেখার আগেই ইউনিট টেস্ট দেখে ধারণা করতে পারবে যে ফাংশনটা আসলে কিভাবে ব্যবহার করতে হয়।
  • ইউনিট টেস্টের কেসগুলো দেখলে বোঝা যায় যে কোনো বিশেষ কেস মিস হয়ে গেল কী না আর তখন সেই কেস যোগ করে টেস্ট রান করলে বোঝা যাবে সেই কেসের জন্য ফাংশনটি ঠিকভাবে আউটপুট দিচ্ছে কী না।
  • অন্যকেউ যদি ফাংশনে কোনো পরিবর্তন করে তাহলে অনেক সময় ফাংশনে অনাকাঙ্ক্ষিত বাগ চলে আসতে পারে। সেক্ষেত্রে যদি ফাংশনের ইউনিট টেস্ট ঠিকঠাক লেখা থাকে, তাহলে বাগ ঢুকে যাওয়ার সম্ভাবনা অনেক কমে যায়। কারণ বাগ ঢুকলে ইউনিট টেস্ট ফেইল করবে (যদি ওই কেসটি আগে থেকে ইউনিট টেস্টে লেখা থাকে)।

এই লেখায় ইউনিট টেস্টের একেবারে প্রাথমিক বিষয়গুলো লেখলাম। ইউনিট টেস্ট ঠিকভাবে লেখা শিখতে অনেক সময়, ধৈর্য্য ও পরিবেশের প্রয়োজন। আমি এখন এটি ভালোভাবে শেখার চেষ্টা করছি। ভবিষ্যতে এই বিষয়ে আরো লিখার ইচ্ছা রইল। আরেকটা শেষ কথা বলা প্রয়োজন যে, ইউনিট টেস্ট লেখা কিন্তু ডেভেলাপারের কাজ ও দায়িত্ব, সফটওয়্যার টেস্টিং কিংবা কোয়ালিটি অ্যাশিউরেন্স টিমের কারো নয়।