ত্রিভুজ গণনা – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৪

সমস্যাঃ একটি ইন্টিজার অ্যারে দেওয়া আছে, যার সবগুলো সংখ্যাই ধনাত্মক। ওই অ্যারে থেকে তিনটি করে উপাদান নিয়ে মোট কয়টি ত্রিভুজ বানানো যায়, সেটি গণনা করতে হবে।

সমাধানঃ সমস্যাটি নিয়ে চিন্তা করার শুরুতেই একটি বিষয় মাথায় চলে আসবে, “ত্রিভুজের যেকোনো দুই বাহুর সমষ্টি তৃতীয় বাহু অপেক্ষা বৃহত্তর।” এই বিষয়টি কাজে লাগিয়ে আমরা সমস্যাটির সমাধান করতে পারি। আমাদের মূল কোড হবে নিচের মতো –

count = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if A[i] + A[j] > A[k]:
                count += 1

ইন্টারভিউতে অবশ্য একটি ফাংশন তৈরি করে তার ভেতরে মূল কোড লেখা উচিত, আমি সেটি আর দেখালাম না। এখন প্রশ্ন হচ্ছে, এই সমাধানের কমপ্লেক্সিটি কত? O(n^3)। এখন ইন্টারভিউয়ার জানতে চাইবেন, এর চেয়ে ভালোভাবে সমাধান করা সম্ভব কী না, এবং সম্ভব হলে চেষ্টা করতে।

ধরা যাক, মূল অ্যারেতে দেওয়া আছে 1, 1, 2, 3, 4। এখানে প্রতিবার তিনটি করে সংখ্যা নিলে আমরা পাই –

1, 1, 2
1, 1, 3
1, 1, 4
1, 2, 3
1, 2, 4
1, 3, 4
1, 2, 3
1, 2, 4
1, 3, 4
2, 3, 4

এগুলোর মধ্যে, কেবল 2, 3, 4 যখন একটি ত্রিভুজের বাহুর দৈর্ঘ্য হবে, তখন একটি ত্রিভুজ তৈরি করা যাবে। কারণ, 2 + 3  > 4। বাকীগুলোর জন্য a + b > c সত্য নয় (এখানে a, b, c হচ্ছে যথাক্রমে ত্রিভুজের প্রথম, দ্বিতীয় ও তৃতীয় বাহু)। আর সংখ্যাগুলো যেহেতু ছোট থেকে বড় ক্রমে সাজানো, তাই a + b > c পরীক্ষা করলেই হবে, b + c > a, c + a > b এগুলো পরীক্ষা করার দরকার নেই।

এখন প্রশ্ন হচ্ছে, আমাদেরকে যেই অ্যারে দেওয়া আছে, সেটিতো ছোট থেকে বড় ক্রমে সাজানো নেই। তাই প্রথমে আমরা সেটি সর্ট করে নেবো। এই কাজটি করার কমপ্লেক্সিটি হচ্ছে O(n log n), যা O(n^3)-এর চেয়ে অনেক ছোটো। তাহলে প্রথমে আমরা অ্যারেটি সর্ট করে নেবো।

ধরা যাক, অ্যারে A-তে আছে দশটি সংখ্যা – 10, 11, 12, 13, 14, 15, 16, 20, 21, 22। এখন, i-এর মান 0, j-এর মান 1 হলে, k-এর মান 2 থেকে 7 পর্যন্ত প্রতিটির জন্যই A[i] + A[j] > A[k] শর্তটি সত্য হবে, অর্থাৎ A[i], A[j], A[k] ত্রিভুজের তিনটি বাহু হিসেবে ব্যবহার করা যাবে। আর মোট ত্রিভুজ কয়টি হবে? 7 – 1 বা 6টি।

এখন, i-এর মান 0, j-এর মান 2 এর জন্য কিন্তু আর k-এর মান 2 থেকে পরীক্ষা করার দরকার নেই, কারণ k-এর মান 7 পর্যন্ত অবশ্যই A[i] + A[j] > A[k] সত্য হবে, কারণ A[0] + A[1] এর মান অবশ্যই A[0] + A[2] এর মানের  চেয়ে ছোট বা সমান। তাই আমরা k-এর মান আগের চেয়ে এক এক করে বাড়িয়ে পরীক্ষা করবো।

তাহলে, i-এর যেকোনো মানের জন্য, j-এর মান i+1 এবং k-এর মান i+2 থেকে আমরা লুপ শুরু করবো। আর j-এর মান যখন বাড়বে, তখন কিন্তু আবার k-এর মান i+2 থেকে শুরু করবো না, বরং আগে k-এর মান যা ছিল, সেখান থেকেই শুরু হবে।

count = 0
for i in range(n - 2):
    k = i + 2
    for j in range(i + 1, n - 1):
        while k < n and A[i] + A[j] > A[k]:
            k += 1
        count = count + k - j - 1

ওপরের কোড-এর কমপ্লেক্সিটি কত? যারা একটু কম চিন্তা করবে, তারা হুট করে বলে দিবে O(n^3), কারণ তিনটি নেস্টেড লুপ আছে। কিন্তু একটু ভালোভাবে লক্ষ করলে দেখা যাবে যে, j-এর লুপের জন্য ভেতরের লুপটি আর নতুন করে শুরু হচ্ছে না, k-এর আগের মান থেকেই শুরু হচ্ছে। না বুঝলে খাতা কলম নিয়ে বসতে হবে। তাই সবচেয়ে বাইরের লুপ (i-এর লুপ)-এর জন্য ভেতরে j ও k-এর লুপ প্রতিটি সর্বোচ্চ n সংখ্যকবার চলবে (মোট, n + n = 2n)। তাই কমপ্লেক্সিটি হচ্ছে, n * 2n, বা 2 * n^2, বা, O(n^2).

কেউ চাইলে নিচের যেকোনো একটি সমস্যা সমাধানের চেষ্টা করতে পারে

1) https://leetcode.com/problems/valid-triangle-number/

2) https://www.interviewbit.com/problems/counting-triangles

স্ট্যাক দিয়ে কিউ তৈরি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৩

সমস্যাঃ স্ট্যাক (Stack) ব্যবহার করে কিউ (Queue) তৈরি করতে হবে, অর্থাৎ কিউ এর এনকিউ (enqueue) ও ডিকিউ (dequeue) ফাংশন তৈরি করতে হবে।

সমাধানঃ প্রথমে একটু চিন্তা করলেই আমরা বুঝতে পারবো যে একটি স্ট্যাক দিয়ে আসলে একটি কিউ তৈরি করা সম্ভব নয়। যদি সম্ভব হতো, তাহলে এই দুটি আলাদা ডেটা স্ট্রাকচার হতো না। কিন্তু যেহেতু সমস্যা দেওয়া হয়েছে, সমাধান নিশ্চয়ই আছে। সমাধান হচ্ছে, দুটি স্ট্যাক ব্যবহার করা।

নোটঃ স্ট্যাক ও কিউ নিয়ে আমি বিস্তারিত আলোচনা করেছি, কম্পিউটার প্রোগ্রামিং ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি এবং পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি বইতে। এছাড়া ইউটিউবেও এ বিষয়ে আলোচনা  করেছি ডেটা স্ট্রাকচার ও অ্যালগরিদম প্লেলিস্টে

ধরা যাক, কিউতে প্রথমে আমি পাঁচটি সংখ্যা রাখতে চাই, অর্থাৎ enqueue অপারেশন হবে পাঁচবার এবং সংখ্যাগুলো হচ্ছে – 1, 2, 3, 4, 5. আমি এগুলো প্রথম স্ট্যাকে পুশ (push) করব।

এখন আমি চাই, কিউ থেকে প্রথম তিনটি সংখ্যা সরিয়ে ফেলতে, অর্থাৎ তিনবার dequeue অপারেশন হবে। তাহলে কিউ থেকে যথাক্রমে 1, 2, 3 – এই তিনটি সংখ্যা চলে যাবে। কিন্তু স্ট্যাক থেকে তো কেবল ওপরের সংখ্যাটি সরানো যায়। তাহলে, আমি প্রথম স্ট্যাকের সবগুলো সংখ্যা দ্বিতীয় স্ট্যাকে নিয়ে আসব। তখন স্ট্যাকগুলোর অবস্থা হবে নিচের ছবির মতো –

এখন আমি দ্বিতীয় স্ট্যাকে তিনবার পপ (pop) অপারেশন চালালে 1, 2, 3 স্ট্যাক থেকে চলে যাবে। তখন স্ট্যাকদুটির অবস্থা হবে নিচের ছবির মতো –

এখন আমি কিউতে 6 ও 7 ক্রমানুসারে রাখতে চাই। আমি সেগুলো প্রথম স্ট্যাকে পুশ করবো।

এখন কিউ-এর অবস্থা হচ্ছে এমন: 4, 5, 6, 7. আমি যদি কিউ থেকে তিনটি সংখ্যা সরিয়ে নিই (অর্থাৎ তিনবার ডিকিউ করি), সেগুলো হবে, যথাক্রমে 4, 5, 6। ডিকিউ করার জন্য আমি প্রথমে দেখবো যে দ্বিতীয় স্ট্যাকে কিছু আছে কী না। যদি থাকে, সেই স্ট্যাক থেকে পপ করবো। আর যদি stack2 খালি থাকে, তাহলে Stack1-এর সব কিছু Stack2-তে নিয়ে আসবো (তখন দ্বিতীয় স্ট্যাকে সেগুলো প্রথম স্ট্যাকের বিপরীত ক্রমে থাকবে)। তারপরে দ্বিতীয় স্ট্যাক থেকে পপ করবো।

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

বাইনারি সার্চ ট্রি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ২

সমস্যাঃ একটি ফাংশন তৈরি করতে হবে, যেখানে একটি বাইনারি ট্রি ইনপুট দেওয়া হলে সেটি বাইনারি সার্চ ট্রি (BST) কী না, তা বের করতে হবে।

সমাধানঃ কোনো বাইনারি ট্রি-কে বাইনারি সার্চ ট্রি হতে হলে ওই ট্রি-এর যেকোনো নোডের বামদিকের চাইল্ড ও নাতি-পুতি নোডগুলো ওই নোডের চেয়ে ছোট এবং ডানদিকের চাইল্ড ও নাতি-পুতি নোডগুলো ওই নোডের চেয়ে বড় হতে হবে। যেমন নিচের ট্রি-টি একটি বাইনারি সার্চ ট্রি –

             6
          /     \
         3       12
       /   \    /   \
      1     4  9     13

কিন্তু নিচের বাইনারি ট্রি-টি বাইনারি সার্চ ট্রি নয় (কেন?)

             6
          /     \
         3       12
       /   \    /   \
      1     7  9     13

নোটঃ বাইনারি সার্চ ট্রি নিয়ে আমি বিস্তারিত আলোচনা করেছি, কম্পিউটার প্রোগ্রামিং ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি এবং পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি বইতে।

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

class node:
  def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None


def find_max(root):
    max_v = root.data
    if root.left:
        left_max = find_max(root.left)
        if left_max > max_v:
            max_v = left_max
    if root.right:
        right_max = find_max(root.right)
        if right_max > max_v:
            max_v = right_max
    return max_v


def check_binary_search_tree(root):
    if root is None:
        return True
        
    # find the largest number on the left sub-tree and check if it's smaller/equal to the root
    if root.left:
        max_value = find_max(root.left)
        if max_value >= root.data:
            return False
    
    # find the smallest number on the right sub-tree and check if it's larger than the root
    if root.right:
        min_value = find_min(root.right)
        if min_value <= root.data:
            return False
    
    # now do the same for the sub-trees
    valid_left = check_binary_search_tree(root.left)
    valid_right = check_binary_search_tree(root.right)
        
    return valid_left and valid_right

ওপরে find_min ফাংশনটি আমি ইমপ্লিমেন্ট করলাম না, find_max কীভাবে কাজ করে বুঝলে find_min তৈরি করতে সমস্যা হবে না। এখন প্রশ্ন হচ্ছে, ওপরের ফাংশনটির কমপ্লেক্সিটি কত? ফাংশনটির টাইম কমপ্লেক্সিটি হচ্ছে O(n^2). কীভাবে সেটি বুঝতে না পারলে একটি বাইনারি ট্রি, যেটি কী না বাইনারি সার্চ ট্রি, সেটি নিয়ে অ্যানালাইসিস করলে বুঝতে পারা যাবে (এই লেখার প্রথম উদাহরণের ট্রি-এর মতো)।

আরো ভালো সমাধানঃ আমরা O(n) টাইম কমপ্লেক্সিটিতে সমস্যাটির সমাধান করতে পারি। এজন্য আমরা ট্রি-টি ইনঅর্ডার ট্রাভার্সাল করে নোডগুলো একটি লিস্টে রেখে দেব। তারপরে দেখব যে, ওই লিস্টের সবগুলো উপাদান ছোট থেকে বড় ক্রমে সর্ট করা আছে কী না, যদি না থাকে তাহলে এটি বাইনারি সার্চ ট্রি নয়, অন্যথা এটি একটি বাইনারি সার্চ ট্রি।

def check_binary_search_tree_(root):
    nodes = []
    
    def inorder(root):
        if root is None:
            return
        inorder(root.left)    
        nodes.append(root.data)
        inorder(root.right)
            
    inorder(root)
    
    for i in range(len(nodes)-1):
        if nodes[i] >= nodes[i+1]:
            return False
        
    return True

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

ওপরের লিঙ্কগুলোতে পাইথন ছাড়াও অন্য ভাষা ব্যবহার করা যাবে।

def check_binary_search_tree(root):
    
    def inorder(root):
        nonlocal last_node
        
        if root is None: 
            return True
        
        left_valid = inorder(root.left)    
        if left_valid is False:
            return False
        
        if root.data <= last_node: 
            return False
        
        last_node = root.data
        
        return inorder(root.right)  
    
    last_node = -1 #assuming all nodes are non-negative
    return inorder(root)

লেখাটি যাদের কাজে আসতে পারে, তাদের সঙ্গে শেয়ার করার অনুরোধ রইলো। ধন্যবাদ।
 

pow(a, n) – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১

সমস্যাঃ একটি ফাংশন তৈরি করতে হবে, যেখানে দুটি ইন্টিজার (a, n) ইনপুট দেওয়া থাকলে ফাংশনটি a^n রিটার্ন করবে। ফাংশনটির রানটাইম হতে হবে O(log n)।

সমাধানঃ আমাদেরকে যেটি করতে হবে, সেটি হচ্ছে pow() ফাংশনটি ইমপ্লিমেন্ট করতে হবে। কিন্তু এতে ঘাবড়াবার কিছু নেই। আমরা পাইথনে খুব সহজে এটি ইমপ্লিমেন্ট করতে পারি।

def pow(a, n):
   result = 1.0
   for _ in range(n):
      result = result * a
   return result

ওপরে যেই ফাংশনটি লিখলাম, সেটির কমপ্লেক্সিটি কত? টাইম কমপ্লেক্সিটি হচ্ছে O(n)। কিন্তু আমাদেরকে বলা হয়েছে O(log n) কমপ্লেক্সিটিতে ইমপ্লিমেন্ট করতে। যদি এটি বলা না থাকতো, তাহলে কিন্তু ওপরের কোড লিখে দিলেই হতো।
আমরা ডিভাইড এন্ড কনকোয়ার পদ্ধতিতে সমস্যাটির সমাধান করতে পারি। সেজন্য আমাদেরকে একটি বিষয় উপলব্ধি করতে হবে। a^n-কে আমরা লিখতে পারি, (a^n/2) * (a^n/2). যেমন, 5^4 হচ্ছে 625. কিন্তু আমরা 5^4-কে লিখতে পারি, (5^2) * (5^2)। এভাবে লিখে লাভ কী হলো? লাভ হচ্ছে, 5^2 এর মান আমাদের দুবার বের করতে হবে না, একবার বের করলেই হবে। কিংবা ধরা যাক, আমাদেরকে 2^32-এর মান বের করতে বলা হলো।

2^32 = (2^16) * (2^16)
2^16 = (2^8) * (2^8)
2^8 = (2^4) * (2^4)
2^4 = (2^2) * (2^2)
2^2 = (2^1) * (2^1)

এখন আমরা জানি, a^0 হচ্ছে 1 আর a^1 হচ্ছে a. তাই রিকার্শন ব্যবহার করে সমস্যাটির সমাধান বের করতে কিন্তু আমাদের তেমন বেগ পেতে হবে না। আর n যদি জোড় সংখ্যা না হয়ে বিজোড় সংখ্যা হতো, তখন আমাদের কী করতে হবে? তখন a^n-কে আমরা লিখতে পারি a^(n-1) * a. n যেহেতু বিজোড় সংখ্যা, n-1 অবশ্যই জোড় সংখ্যা। তাই আমরা আবার আগের মতো আগাতে পারি।

এখন আমি প্রোগ্রাম লিখে ফেলি –

def pow(a, n):
   if n == 0: return 1
   if n == 1: return a 

   if n % 2 == 1:
      return a * pow(a, n-1) 
   else:
      p = pow(a, n/2)
      return p * p

ওপরের pow() ফাংশনটির কমপ্লেক্সিটি হচ্ছে O(log n)। কেন সেটি আর এখানে বিস্তারিত ব্যাখ্যা করলাম না, তবে যারা বাইনারি সার্চের কমপ্লেক্সিটি বোঝে, তাদের এটি বুঝতে কোনো সমস্যা হবে না।

সমস্যাটির সমাধান কিন্তু পুরোপুরি হয় নি। কারণ n যদি ঋণাত্মক হয় তখন কিন্তু প্রোগ্রামটি কাজ করবে না। এটি ঠিকঠাক করার জন্য আমাদেরকে কী করতে হবে?

পাইথন-এ ডেটা অ্যানালাইটিক্স

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

পাইথন এর প্রাথমিক ব্যাপারগুলো নিয়ে কিছু বলার আর তেমন দরকার আছে বলে আমার মনে হয় না। কারো প্রয়োজন হলে বিস্তারিত দেখে নেয়া যাবে এখান থেকে –

১। পাইথন পরিচিতি   

২। প্রাথমিক ধারনা  

আমার এই লিখাটা মূলত তিনটি বা চারটি পর্বে ভাগ করার ইচ্ছে। এই পর্বে আলোচনা করব NumPy এর একেবারের শুরুর কিছু ব্যাপার। সামনের পর্ব গুলোতে  থাকবে NumPy আর Pandas নিয়ে বিস্তারিত কিছু যা মূলত ডাটা এনালাইটিকস এর কাজে ব্যাবহৃত হয়।

তার আগে কিন্তু আমাদের পাইথন এর বেসিক কিছু ডাটা স্ট্রাকচার নিয়ে হাতেকলমে কাজ করে আসতে হবে ,যেমন list, dict, tuples, sets, strings । আমি নিশ্চিত তোমরা এই জিনিসগুলো পড়েই ডাটা এনালাইটিক্স এর কাজে হাত দিবে –
চটপট একটা পুরনো পড়া পড়ে ফেলতে পারি আমরা –
List এ  append আর  extend এর পার্থক্য কি ?

NumPy (সচরাচর উচ্চারন “নামপাই”) একটি লাইব্রেরি এবং শব্দটা এসেছে Numerical Python থেকে । এই লাইব্রেরি এন-ডাইমেনশনাল Array , বিভিন্ন জটিল গাণিতিক ফাংশন এর কাজ ( যেমন  Fourier transforms )-সহ আরো অনেক ধরনের গাণিতিক কাজ করার ক্ষেত্রে ওস্তাদ ।

ঢাকায় এখন বিভিন্ন এপভিত্তিক পরিবহন খুব জনপ্রিয় – আমরা সবাই উবার, পাঠাও, মুভ বা স্যাম নামে এইসব সেবা ব্যাবহার করছি আর সেইরকম একটি সার্ভিস-এর তিনজন ব্যবহারকারীর কিছু ডেটা আছে, সেইরকম তিনটা ফাইল নিয়ে আমরা কাজ শুরু করতে পারি।
আমরা সেখান থেকে তিনটা জিনিস বের করতে চাইব :
১। অফিস থেকে কে কখন রাইড নিয়ে বের হয়ে গিয়েছে ?
২। তাদের ভাড়ার Standard Deviation দেখতে কেমন ?
আর
৩। চেষ্টা করব বের করতে এই তিনজনের মাঝে কোন বাইক ড্রাইভার কমন ছিলেন কিনা, সম্ভব হলে সেটা গ্রাফে দেখা (যদিও গ্রাফে দেখার ব্যাপারটা এর সাথে তেমন একটা সম্পর্কিত না – কিন্তু দেখতে সুন্দর লাগে)।

এখান থেকে ফাইলগুলো নামিয়ে নেয়া যাবে (আপাতত আমি একটা ফাইল রেখেছি …পরবর্তী পর্বে বাকীগুলো পাওয়া যাবে)। 

প্রথমেই RidersData1 ফাইলটি পড়ে নিয়ে পাইথন-এ এর ডাটা দেখে নেই – 

import csv
with open("C:\Users\Asus\Desktop\RidersData1.csv", 'r') as f:
riders_data = list(csv.reader(f, delimiter=","))
print(riders_data[:2])

দেখে নেই যাত্রীর ভাড়ার পরিমান কত ছিল তার ভ্রমণের দিনগুলোতে

fare = [item[10] for item in riders_data[1:]]
print(fare)

তার মোট পরিমান কত ছিল ?

fare = [int(item[10]) for item in riders_data[1:]]
print(sum(fare))

>> ৫১৮৫ টাকা

এবার আমরা Numpy ইন্সটল করে কাজটা শুরু করি-
( Numpy ইন্সটল করার ধাপগুলো সুন্দর করে বলে দেয়া আছে এখানে

import numpy as np
riders_data = np.genfromtxt("D:\RidersData1.csv", delimiter=",", skip_header=1)

 

fare = [int(item[10]) for item in riders_data[0:]]
print(sum(fare))

এখন যদি Numpy ব্যাবহার করে Array তৈরী করি যা আসলে Array এর Array তৈরী করবে ।

riders_data_array = np.array(riders_data[1:], dtype=np.int)

এখানে dtype=np.int  আসলে নিশ্চিত করবে যেন ডাটা গুলোকে  String থেকে int এ রুপান্তর(convert) করে নেয়।

এখন আমরা যদি Array টা দেখতে চাই?

ইনপুট
 print(riders_data_array)
আউটপুট
 [[4445115     143    3180   15536       5]
  [4341383     167    3067   15704       5]
  [4153972     163    2383   15692       5]
  [4052253     167    3055   15703       5]
  [3935184     191    1520   12760       5]
  [3896665     202    2251   13224       5]
  [3807622     141    2611   15722       5]
  [3723194     236    2063   16165       5]
  [3650954     233    2411   15695       5]
  [3592384     262    5845   15721       5]
  [3538266     204    4802   11583       5]
  [3496106     242    3462   15698       5]
  [3455465     235    2588   15695       5]
  [3361305     229    1883   15724       5]
  [3353856     230    2173   15574       5]
  [3342150     234    2483   15700       5]
  [3302407     217    2461   15716       5]
  [3263818     163    2393   15688       5]
  [3227817     163    2270   15691       5]
  [3189625     166    2976   15635       5]
  [3118401     244    3155   16076       5]
  [3056517     245    3161   12712       5]
  [2966371     191    1882   12546       5]
  [2904590     242    2844   16122       5]
  [2872271     135    2652   15900       5]]

আমরা এখন যেকোন রকমের Array তৈরি করতে পারি

ইনপুট
 any_array = np.ones((5,6))
 print(any_array)
আউটপুট
 [[ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]
  [ 1.  1.  1.  1.  1.  1.]]

এখানে np.ones((5,6)) তে 5 এবং 6  যথাক্রমে row আর column বুঝাচ্ছে ।ঠিক একই রকম ভাবে একটা array তৈরি করতে পারি যেটার সবগুলো ভ্যালু হবে zero।

ইনপুট
 any_array = np.zeros((5,6))
 print(any_array)
আউটপুট
 [[ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]
  [ 0.  0.  0.  0.  0.  0.]]

আর এখন যদি চিন্তা করি একটা array তৈরি করব যার ভ্যালুগুলো হবে যে কোন নাম্বার বা Random ।

ইনপুট
 any_array = np.random.rand(2,3)
 print(any_array)
আউটপুট
 [[ 0.58870582  0.75596673  0.48148491]
  [ 0.39392526  0.16046594  0.34446376]]

এই পর্যায়ে এসে আমি দুটো বাড়ির কাজ দিতে চাই – 

১। Random নাম্বারের একটা array তৈরি করতে হবে যেখানে সংখ্যাগুলো হবে পূর্ণমান বা integer
২। any_array = np.eye(4)  – এই কোডটি run করলে যেই আউটপুট আসল তার মানে কি ?

স্লাইসিং (Slicing) :

শব্দটা শুনেই বুঝা যাচ্ছে – যে কোন বড় কোন Array থেকে কিছু অংশ কেটে নেয়াই slicing । যেমন আমাদের মূল ডাটা এর array ( riders_data_array)  যা দেখতে এমন

[[4445115     143    3180   15536       5]
  [4341383     167    3067   15704       5]
  [4153972     163    2383   15692       5]
  [4052253     167    3055   15703       5]
  [3935184     191    1520   12760       5]
  [3896665     202    2251   13224       5]
  [3807622     141    2611   15722       5]
  [3723194     236    2063   16165       5]
  [3650954     233    2411   15695       5]
  [3592384     262    5845   15721       5]
  [3538266     204    4802   11583       5]
  [3496106     242    3462   15698       5]
  [3455465     235    2588   15695       5]
  [3361305     229    1883   15724       5]
  [3353856     230    2173   15574       5]
  [3342150     234    2483   15700       5]
  [3302407     217    2461   15716       5]
  [3263818     163    2393   15688       5]
  [3227817     163    2270   15691       5]
  [3189625     166    2976   15635       5]
  [3118401     244    3155   16076       5]
  [3056517     245    3161   12712       5]
  [2966371     191    1882   12546       5]
  [2904590     242    2844   16122       5]
  [2872271     135    2652   15900       5]]

আমি যদি এখন এখান থেকে ২য় কলাম এর প্রথম ৫ টা ডাটা দেখতে চাই –

ইনপুট
 print(riders_data_array[0:5,1])
আউটপুট
 [143  167   163   167   191]

এখানে [0:5,1] অংশ টা বুঝাচ্ছে – প্রথম ৫ টি row এর ডাটা এবং তা ২য় column এর। এখানে যদি 0 এর পরিবর্তে আমি 1 লিখি – তারমানে তখন প্রথম row বাদ দিয়ে চারটি ডাটা নিবে এবং আউটপুট হবে এরকম

[167   163    167     191]

NumPy নিয়ে পরবর্তী পর্বটি কিছুদিন পর প্রকাশিত হবে। ধন্যবাদ।

 

 

 

 

গড়, মধ্যক ও প্রচুরক

গড় শব্দটির সঙ্গে তোমরা যারা স্কুলে বিষয়টি পড়ে ফেলেছ, তারা যেমন পরিচিত, তেমনি যারা ক্রিকেট খেলা দেখো, তারাও পরিচিত। এই বইটি যখন লেখা হচ্ছে, তখন তামিম ইকবালের টেস্ট ক্রিকেটে ব্যাটিং গড় হচ্ছ 40.34 আর সাকিব আল হাসানের 40.93। এই গড় কিভাবে হিসেব করা হলো আর এর মানেই বা কী?

আমাকে যদি দুটি সংখ্যা দিয়ে এদের গড় বের করতে বলা হয়, তখন আমি সংখ্যা দুটি যোগ করে দুই দিয়ে ভাগ করবো। যেমন : 5 ও 6, এই দুটি সংখ্যার গড় হচ্ছে (5 + 6) / 2 বা 11 / 2 বা 5.5। তিনটি সংখ্যা 6, 7, 8-এর গড় হচ্ছে (6 + 7 + 8) / 3 বা 21 / 3 বা 7। তাহলে আমাকে যদি n সংখ্যক সংখ্যা দেওয়া হয়, তাহলে তাদের গড় বের করতে হলে সবগুলো সংখ্যা যোগ করে n দিয়ে ভাগ করবো। তাহলেই হয়ে গেলো।

এখন আমরা পাইথন ব্যবহার করে একটি প্রোগ্রাম লিখবো, যার কাজ হচ্ছে অনেকগুলো সংখ্যার গড় বের করা।

def average(li):
   s = sum(li)
   n = len(li)
   return s / n

li = [1, 2, 3]
print("Average:", average(li))
li = [10, 20, 30, 40, 50, 60, 70, 80]
print("Average:", average(li))
li = [-1, 0, 1]
print("Average:", average(li))

প্রোগ্রামটি রান করলে আমরা আউটপুট পাবো এরকম :

Average: 2.0
Average: 45.0
Average: 0.0

ক্রিকেট খেলায় ব্যাটিং গড় কিভাবে বের করে? মোট রানকে ইনিংস দিয়ে ভাগ করতে হয়। তবে একটি মজার বিষয় হচ্ছে, কোনো ইনিংসে অপরাজিত থাকলে, অর্থাৎ, আউট না হলে, সেই ইনিংসকে ভাগ করার সময় গণনা করা হয় না। ধরা যাক, কোনো ব্যাটসম্যান প্রথম খেলায় করলো 50 রান, দ্বিতীয় খেলায় 100 রান (অপরাজিত), তৃতীয় খেলায় আবারো 50 রান করে আউট হলো। তাহলে তার ব্যাটিং গড় হবে, (50 + 100 + 50) / 2, বা 200 / 2 বা 100। এখানে 3 এর বদলে 2 দিয়ে ভাগ করার কারণ হচ্ছে, দ্বিতীয় খেলায় সে অপরাজিত ছিল।

এখন গড় আমাদের কী কাজে লাগে? ধরা যাক, আন্তর্জাতিক ক্রিকেট খেলায় নতুন একটি দেশের আগমন ঘটলো এবং বাংলাদেশের সঙ্গে ওই দলের খেলা। টসে হেরে ওই দল প্রথমে ব্যাটিং পেল। এখন ওদের যেই দুজন ব্যাটসম্যান ইনিংস ওপেন করতে এসেছে, ঘরোয়া লিগে একজনের ব্যাটিং গড় হচ্ছে 26 আরেকজনের হচ্ছে 41। এই তথ্য থেকে তুমি দুজন ব্যাটসম্যানের মধ্যে তুলনা করতে পারো যে, কে তুলনামূলক ভালো ব্যাটসম্যান। তবে আজকের ম্যাচে কে কত রান করবে, এটি কিন্তু ব্যাটিং গড়ের ওপর নির্ভর করে না। কারও ব্যাটিং গড় 26 মানে এই নয় যে, সে প্রতি ইনিংসে 26 রান করে। তাহলে গড় হচ্ছে কোনো কিছুর মান সম্পর্কে ধারনা করার জন্য একটি টুল মাত্র। ইংরেজিতে একে average বলে, তবে গণিতের ক্ষেত্রে mean শব্দটিই বেশি ব্যবহার করা হয়।

এখন আরেকটি উদাহরণ দেই। কোনো দেশের মানুষ কেমন ধনী বা গরিব, তা বোঝার জন্য অনেকসময় মাথাপিছু আয় ব্যবহার করা হয়। মাথাপিছু আয় মানে হচ্ছে গড় আয়। সেটি ব্যবহার করে সেই দেশের মানুষের অর্থনৈতিক অবস্থা সম্পর্কে ধারণা পাওয়া যায়। কিন্তু সেখানে যদি মানুষের আয়ের মধ্যে বৈষম্য অনেক বেশি হয়, তাহলে কিন্তু গড় ব্যবহার করে প্রকৃত ধারণা পাওয়া যাবে না। একটি উদহারণ দিয়ে বোঝাই। ধরা যাক, কোনো দেশে 10 জন মানুষ আছে। তাদের মধ্যে 2 জন প্রতি মাসে 10 হাজার টাকা আয় করে। 5 জন প্রতিমাসে 20 হাজার টাকা আয় করে। আর একজন আয় করে প্রতিমাসে 30 হাজার টাকা। বাকী দুইজন প্রতি মাসে 5 লক্ষ টাকা আয় করে। তাহলে প্রতিমাসে তাদের গড় আয় কত?

গড় আয় = (10000 + 10000 + 20000 + 20000 + 20000 + 20000 + 20000 + 30000 + 500000 + 500000) / 10 = 115000।
তার মানে গড় আয় এক লক্ষ পনের হাজার টাকা! তাহলে শুধু গড় আয় জানলে যেকেউ সেই দেশের মানুষকে ধনী ভাববে। তাই গড় ব্যবহার করে সবসময় প্রকৃত চিত্র পাওয়া যায় না। তবে এতে হতাশ হওয়ার কিছু নেই, কারণ আমাদের হাতে রয়েছে মধ্যক ও প্রচুরক।

মধ্যক

এখন ধরা যাক, তুমি কোনো ক্রিকেট দলের ম্যানেজার। তোমার দল তৈরির সময় দুই জন ব্যাটসম্যান – রবিন ও সমিত-এর মধ্যে একজনকে বেছে নিতে হবে। দুজনের মধ্যে যার ব্যাটিং গড় বেশি, তুমি তাকে দলে নিতে পারো। কিন্তু তুমি যদি আরেকটু সচেতন হও, তখন হয়ত তুমি জানতে চাইতে পারো যে, কে কতগুলো ম্যাচ খেলেছে। ধরা যাক, রবিন 50 টি ম্যাচ খেলেছে এবং তার ব্যাটিং গড় 30। আর সমিত খেলেছে 5টি ম্যাচ এবং তার ব্যাটিং গড় 38। তুমি কিন্তু বেশিরভাগ ক্ষেত্রেই রবিনকে দলে নেবে, যেহেতু সে সমিতের তুলনায় অনেক বেশি অভিজ্ঞ। কিন্তু দুইজন যদি সমান সংখ্যক ম্যাচ খেলে, তখন কি কেবল গড় হিসেব করবে? তুমি চাইলে তখন আরেক ধরনের টুল ব্যবহার করতে পারো, যার নাম মধ্যক (ইংরেজিতে বলে median)। ধরা যাক, রবিন ও সমিত – দুজনেই 10টি করে ম্যাচ খেলেছে। 10টি ম্যাচে রবিনের রান হচ্ছে 95, 88, 47, 0, 10, 1, 5, 12, 0, 3। আর সমিতের রান হচ্ছে 10, 40, 20, 37, 0, 1, 25, 35, 30, 33। রবিনের গড় রান সমিতের গড় রানের চেয়ে বেশি। তবে এখানে আমরা দেখতে পাচ্ছি, রবিন মাঝে-মধ্যে অনেক বেশি রান করে, তবে বেশিরভাগ সময়ই সে খুব একটা ভালো খেলে না। আর সমিত দুয়েকটা বাদের বাকি খেলাগুলোয় মোটামুটি রান করতে পারে। তাই শুধু গড়ের ওপর ভরসা করা আমাদের ঠিক হবে না। আমরা মধ্যক বের করবো। প্রথমে আমরা তাদের প্রতি ম্যাচের রান ছোট থেকে বড় ক্রমানুসারে সাজাবো। তাহলে রবিনের রান হবে 0, 0, 1, 3, 5, 10, 12, 47, 88, 95 আর সমিতের রান হবে 0, 1, 10, 20, 25, 30, 33, 35, 37, 40। মধ্যক বের করতে গেলে আমাদেরকে তালিকার মাঝামাঝি সংখ্যাটি নিতে হবে। মোট সংখ্যা যদি বিজোড় হয়, তাহলে মাঝামাঝি সংখ্যা হবে একটি। যেমন 11-এর ক্ষেত্রে 6 নম্বর সংখ্যাটি হচ্ছে মাঝামাঝি সংখ্যা। কারণ ওই সংখ্যার চেয়ে ছোট 5টি সংখ্যা আছে। আবার বড় সংখ্যাও আছে 5টি। কিন্তু জোড় সংখ্যার বেলায় একটি মাঝামাঝি সংখ্যা বের করা যায় না। যেমন 10টি সংখ্যার ক্ষেত্রে আমরা যদি 5 নম্বর সংখ্যাটিকে মাঝামাঝি সংখ্যা ধরি, তাহলে তার ছোটি 4টি আর তার বড় 5টি সংখ্যা থাকবে। আবার 6 নম্বর সংখ্যাকে মাঝামাঝি সংখ্যা ধরলে, তার ছোট 5টি আর বড় 4টি সংখ্যা থাকবে।

যেহেতু আমাদের 10 টি সংখ্যা, তাই আমরা 5 ও 6 নম্বর সংখ্যা দুটি নিয়ে তাদের গড় বের করবো, মানে সংখ্যা দুটি যোগ করে দুই দিয়ে ভাগ করবো। তাহলে রবিনের রানের মিডিয়ান হবে 7.5 আর সমিতের রানের মিডিয়ান হবে 27.5। এখানে আমরা মিডিয়ান ব্যবহার করে সিদ্ধান্ত নিতে পারি যে কাকে দলে নেব। কাজটি তোমরা খাতা কলমে করে ফেল, তবে আমি পাইথন ব্যবহার করে একটি প্রোগ্রাম লিখে দেখাবো।

def median(li):
   li.sort()
   count = len(li)
   if count == 0:
      return None
   if count % 2 == 1:
      mid = count // 2
      return li[mid]
   else:
      mid2 = count // 2
      mid1 = mid2 - 1
      return (li[mid1]+li[mid2])/2

robin_run = [95, 88, 47, 0, 10, 1, 5, 12, 0, 3]
shomit_run = [10, 40, 20, 37, 0, 1, 25, 35, 30, 33]

median_robin = median(robin_run)
median_shomit = median(shomit_run)

print("Median run for Robin", median_robin)
print("Median run for Shomit", median_shomit)

আমরা এখন আমাদের মাথাপিছু আয়ের হিসেবে ফেরত যাই। তোমরা যদি সেই উদাহরণ থেকে মধ্যক বের করো, তাহলে সেটি হবে 20000। তোমরা হাতে-কলমে কিংবা একটি প্রোগ্রাম লিখে সেটি বের করতে পারো। এখানে কিন্তু মধ্যক ব্যবহার করেই বাস্তব চিত্রের কাছাকাছি চিত্র পাওয়া যাচ্ছে।

প্রচুরক

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

একটি ওয়ানডে ম্যাচে একজন বোলারের পক্ষে সর্বোচ্চ ও সর্বনিম্ন কয়টি উইকেট পাওয়া সম্ভব? উত্তর হবে, যথাক্রমে 10টি ও 0টি। 0-এর চেয়ে কম কিংবা 10-এর চেয়ে বেশি উইকেট পাওয়া সম্ভব নয়। এখন ধরা যাক, মোস্তাফিজ এখন পর্যন্ত 20টি ওয়ানডে ম্যাচে বোলিং করেছে। সেই খেলাগুলোতে সে প্রতি খেলায় যতগুলো উইকেট পেয়েছে, তা হচ্ছে : 6, 5, 6, 4, 3, 1, 3, 2, 1, 0, 5, 3, 3, 2, 2, 1, 3, 4, 3, 3। এখন আমি একটি তালিকা তৈরি করবো, যে মোস্তাফিজ 0 উইকেট পেয়েছে কতবার, 1 উইকেট পেয়েছে কতবার … এরকম।

উইকেট ম্যাচের সংখ্যা
0 1
1 3
2 3
3 7
4 2
5 2
6 2
7 0
8 0
9 0
10 0

তাহলে আমরা দেখতে পাচ্ছি, মোস্তাফিজ সবচেয়ে বেশি পেয়েছে 3 উইকেট। 20টি খেলার মধ্যে 7 টি খেলাতেই সে 3 উইকেট করে পেয়েছে। তাহলে তুমি ধরে নিতে পারো যে, আজকের খেলাতে মোস্তাফিজের 3 উইকেট পাওয়ার সম্ভাবনাই সবচেয়ে বেশি। এখানে প্রচুরক হচ্ছে 3। কারণ উইকেটের লিস্টে 3 সবচেয়ে বেশি বার আছে। আমরা এখন ওপরের হিসেবটা একটি পাইথন প্রোগ্রাম লিখে করবো।

wkts_list = [6, 5, 6, 4, 3, 1, 3, 2, 1, 0, 5, 3, 3, 2, 2, 1, 3, 4, 3, 3]

for item in range(11):
   print("Wicket:", item, "Count:", wkts_list.count(item))

প্রোগ্রামটি রান করলে আউটপুট আসবে এরকম :

Wicket: 0 Count: 1
Wicket: 1 Count: 3
Wicket: 2 Count: 3
Wicket: 3 Count: 7
Wicket: 4 Count: 2
Wicket: 5 Count: 2
Wicket: 6 Count: 2
Wicket: 7 Count: 0
Wicket: 8 Count: 0
Wicket: 9 Count: 0
Wicket: 10 Count: 0

যে ঘটনাটি সবচেয়ে বেশি সংখ্যক বার ঘটে, সেটিই হচ্ছে প্রচুরক। বিভিন্ন রকম মতামত জরিপ করতে প্রচুরক ব্যবহার করা হয়। যেমন ধরো, তুমি একটি নতুন মোবাইল ফোন কিনতে চাও। কিন্তু কোন ব্র্যান্ডের ফোন ভালো সেটা বুঝতে পারছ না। তখন তুমি তোমার বন্ধুদের জিজ্ঞাসা করতে পারো এবং সবচেয়ে বেশি সংখ্যক বন্ধু যেই ব্র্যান্ডের মোবাইল ফোন ব্যবহার করে বা ভালো বলে, সেই ব্র্যান্ডের ফোন কিনতে পারো।

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

এই লেখাটি সহ গণিতের আরো কিছু মৌলিক বিষয় নিয়ে প্রকাশিত হয়েছে গণিত করবো জয়

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

আজকে সকালে গো (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

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

হ্যাশ ফাংশন – ২

লেখকঃ বজলুর রহমান রোকন
লেখকঃ বজলুর রহমান রোকন

আগের পোস্টের সমস্যাটি হলো- দুটি ভিন্ন ভিন্ন স্ট্রিং হ্যাশ ফাংশনে দিলে যদি একই ভ্যালু পাওয়া যায় তাহলে কী হবে? উত্তরটির জন্য পুরো আর্টিক্যাল পড়তে হবে।

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

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

h1

h2

উপরের ছবি দুটি থেকে দেখতে পাচ্ছো, আদা, কলা, পেঁপে, রসুন এবং মরিচ এগুলোর হ্যাশ ভ্যালু যথাক্রমে ১,২,৩ ও ৭, ৮। সুতরাং এগুলো অ্যারের ০,১,২ ও ৬,৭ নম্বর ইন্ডেক্সে বসনো হয়েছে। কিন্তু জীবন তো আর পুষ্পশয্যা নয়। একটু পরেই এসেছে আম। আর তোমার হ্যাশ ফাংশন এর জন্যে ভ্যালু রিটার্ন করেছে ১।

সমস্যাটি নিশ্চয় বুঝতে পারছো। এই সমস্যাকে বলা হয় কলিশন (collision)। এখন তুমি যদি অ্যারের ১ নম্বর ইনডেক্সে আমের দাম রাখো, তাহলে আগের আদার দামের সাথে এটি রিপ্লেস হয়ে যাবে। এতে করে তুমি যদি পরবর্তীতে আদার দাম দাও, তোমার হ্যাশটেবিল আমের দাম দিয়ে দিবে যা হওয়া উচিৎ নয়।

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

লিংকডলিস্টের নাম নিশ্চয় শুনেছো এবং আমার ধারণা প্রত্যেকেই ইমপ্লিমেন্ট করেছো। লিংকডলিস্ট হচ্ছে ট্রেনের মতো। একটির পেছনে আরেকটি বগি জোড়া লাগিয়ে তাতে ভ্যালু রাখা।

তবে এতেও একটি সমস্যা আছে। তোমার মুদির দোকানের সবগুলো পণ্য যদি একটি নির্দিষ্ট বর্ণ দিয়ে শুরু হয় তাহলে প্রথম স্লটে একটি বিশাল চেইন হবে। এক্ষেত্রে হ্যাশ টেবিল থেকে কোন পণ্যের দাম খুঁজে আনার সময় আর O(1) থাকবে না বরং সেটি হয়ে যাবে O(n)। কারণ তখন তোমাকে লিংকডলিস্ট থেকে উপাদানটি খুঁজতে হবে। লিংকডলিস্ট থেকে কোন উপাদান খুঁজে বের করতে সময় লাগে O(n)।

h3

উপরের ছবি থেকে নিশ্চয় দেখতে পাচ্ছো সমস্যাটি কোথায়? তোমার অ্যারের বাকি স্লটগুলো প্রায় খালি রয়ে গেছে।
তাহলে এখান থেকে দুটি বিষয় জানা গেলো –
১. হ্যাশ ফাংশন অনেক গুরুত্বপুর্ণ। এটি খুব সিম্পল হলে সমস্যা।
২. প্রত্যেকটি স্লটেই যদি অনেক বড় লিংকলিস্ট থাকে, তাহলে কনস্ট্যান্ট টাইম অর্থাৎ O(‌1) সময়ে তুমি উপাদান খুঁজে বের করতে পারছো না।
এখন যদি তুমি একটি ভালো হ্যাশ ফাংশন লিখতে পারো, এবং প্রত্যেক স্লটেই যাতে বিশাল লিংকডলিস্টের চেইন না হয় তা নিশ্চিত করতে পারো তাহলেই O(‌1) সময়ে হ্যাশ টেবিল থেকে ভ্যালু পড়তে পারবে।

এবার Load Factor বলে একটা টার্ম আছে, এটি নিয়ে একটু বলি তোমাদের। একটি হ্যাশটেবিলের লোড ফ্যাক্টর খুব সহজেই বের করা যায়।

Load Factor = Number of items in the hash table / Total slot in the array
তাহলে তোমার অ্যারেতে যদি স্লট হয় 10 এবং উপাদানের সংখ্যা যদি হয় ৭ তাহলে লোড ফ্যাক্টর হবে- 0.7। এটি দিয়ে একটি হ্যাশটেবলি কতগুলো স্লট ফাকা আছে তা বের করা যায়। একটি হ্যাশটেবিলের লোড ফ্যাক্টর যদি 1 হয় তাহলে এর বোঝায়, এর প্রত্যেকটি স্লটে একটি করে উপাদান রয়েছে। লোড ফ্যাক্টর একের অধিক থাকার অর্থ হলো, টেবিলের কোন স্লটে একাধিক উপাদান রয়েছে।

কনস্ট্যান্ট টাইম অর্থাৎ O(1) সময়ে কোন উপাদান খুঁজে পাওয়া নিশ্চিত করতে চাইলে লোড ফ্যাক্টর সবসময় একের নিচে রাখতে হবে। এটি করার জন্যে যখনই লোড ফ্যাক্টর ১ এর বেশি হবে তখনই টেবিলকে রিসাইজ করে আবার প্রত্যেকটি উপাদানের হ্যাশ ক্যালকুলেট করে বিভিন্ন স্লটে বসাতে হবে। এই অপারেশনটি মোটামুটি এক্সপেনসিভ। তবে তুমি কনস্ট্যান্ট টাইম উপাদানগুলো খুঁজে পাচ্ছো টেবিলের সাইজ যতোই হোক না কেনো।

তাহলে উপরের আলোচনা থেকে নিশ্চয় বুঝতে পারছো যে, যদিও কনস্ট্যান্ট টাইমে আমরা উপাদান খুঁজে বের করতে চাচ্ছি, কিন্তু সবসময় তা সম্ভব নয়। তবে best case এটি অবশ্যই O(1) হবে এবং worst case-এ এটি O(n) হতে পারে।

হ্যাশ ফাংশন ১

bazlur_pic
লেখকঃ বজলুর রহমান রোকন।

মনে করো, তুমি একটি মুদি দোকান দিয়েছো। তোমার দোকানে হরেকরকম পণ্যদ্রব্য রয়েছে। এই পণ্যগুলোর নাম ও দাম আলাদা আলাদা। এগুলো মনে রাখতে গিয়ে তুমি হিমশিম খাচ্ছো। তুমি সবগুলো খাতায় লিখে রেখেছো। যখনই তুমি একটি পণ্য বিক্রি করো, তোমাকে সেই খাতা দেখতে হয়। খাতা থেকে খুঁজে বের করতে হয়।

খাতাতে যদি নামগুলো বর্ণানুক্রমে রাখা না থাকে, তাহলে তোমার প্রতিবার খুঁজে বের করতে অনেক সময় লাগে। অ্যালগরিমদ ক্লাসে নিশ্চয় শিখেছো যে এক্ষেত্রে খুঁজে বের করার সময় O(n) । তবে নামগুলো যদি বর্ণানুক্রমে রাখা থাকে তাহলে বাইনারি সার্চ ব্যবহার করা যায় আর তখন সময় লাগবে O(log n)। তুমি নিশ্চয় জানো যে O(n) চেয়ে O(log n) কম সময় লাগে।

img1

যদিও O(log n) কম সময় লাগছে, তবুও কিছুটা সময় লাগছে। সবচেয়ে ভাল হতো যদি কোন সময়ই না লাগতো। তুমি সবগুলো পণ্যের নাম এবং দাম মুখস্থ করে ফেলতে পারতে এবং ক্রেতা কোন পণ্যের নাম বলার সঙ্গে সঙ্গেই তুমি দাম বলে দিতে পারতে।

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

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

মনে করো, তোমার ১০ সাইজের একটি অ্যারে রয়েছে। এখন, ধরো, পেঁপের দাম ২০ টাকা। পেঁপে নামটি যদি হ্যাশ ফাংশনে দাও, তাহলে এটি যদি ৪ রিটার্ন করে, তাহলে অ্যারের চতুর্থ নম্বর ইনডেক্সে পেঁপের দামর রেখে দেবে। এভাবে আদার নাম হ্যাশ ফাংশনে দিলে যদি ৩ রিটার্ন করে, তাহলে তাকে তিন নম্বর ইনডেক্সে রেখে দিলে। এভাবে কলা, মরিচ ইত্যাদি রেখে দিলে। এখন যখন তোমার এগুলো দাম জানার দরকার হয়, তাহলে চট করে হ্যাশ ফাংশনে নামটি দিয়ে তার ইনডেক্সটি বের করে নিলে। অ্যারতে ইনডেক্স জানলে ভ্যালু পড়ে আনা খুব সহজ। অ্যারে থেকে ভ্যালু পরে আনার সময় আসলে O(1) ।
img2

img3
হ্যাশ টেবিল

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

উপরের যে উদাহরণটি দিয়েছি তাতে একটি সমস্যা রয়েছে। সেটি নিয়ে পরবর্তীতে আলোচনা করবো। তবে সমস্যাটি তুমি চিন্তা করে যদি খুঁজে বের করতে পারো তাহলে নিচে কমেন্ট করে জানাও।

পরের পর্বঃ হ্যাশ ফাংশন ২।

পাদটিকা: বাইনারি সার্চের টাইম কমপ্লেক্সিটি কিভাবে O(log n) হলো, সেটা না বুঝলে দ্বিমিকের ডিসক্রিট ম্যাথমেটিক্স কোর্সের তৃতীয় ইউনিটের লেকচার দেখে নাও।

ডাটাবেজ ট্রানজেকশন ও এসিড

রিলেশনাল ডাটাবেজের খুব মৌলিক একটি বিষয় হচ্ছে ডাটাবেজ ট্রানজেকশন। আর ডাটাবেজ ট্রানজেকশনের একটি গুরুত্বপূর্ণ বিষয় হচ্ছে এসিড প্রোপার্টি। আজকের লেখায় এই বিষয়ে আলোচনা করবো।

মনে করি জনি, রবিন, জামাল আর কামাল নামে চার বন্ধুর একই ব্যাংকে একাউন্ট আছে। ওই ব্যাংকের ডাটাবেজে Account নামে একটি টেবিল আছে এবং নিচে আমরা সেই Account টেবিলের ডাটা দেখতে পাচ্ছি –

Account No Account Name Balance
100-01 Jony 15000
100-02 Robin 5000
100-03 Kamal 10000
100-04 Jamal 1200

এবার আমরা নিচের ঘটনাগুলি লক্ষ করি –

  • জনি তার একাউন্ট থেকে ১০০০ টাকা তুলে নিল (Cash Withdraw)
  • একজন রবিনের একাউন্টে ৫০০ টাকা জমা দিল (Cash Deposit)
  • কামাল তার একাউন্ট থেকে ২০০০ টাকা জামালের একাউন্টে পাঠাল (Fund Transfer)
  • জামাল তার একাউন্টে কত টাকা আছে তা জানতে চাইল (Balance Enquiry)

উপরের প্রথম তিনটি ঘটনা Account টেবিলের Balance কলামের ডাটা পরিবর্তন করবে এবং শেষের ঘটনাটি Balance কলামের ডাটা পড়বে। আর রিলেশনাল ডাটাবেজ ম্যানেজমেন্ট সিস্টেমের (RDBMS) পরিপ্রেক্ষিতে এ ধরনের ঘটনাগুলিকে আমরা ডাটাবেজ ট্রানজেকশন (Database Transaction or Transaction) বা ট্রানজেকশন বলি। একটি ডাটাবেজ ট্রানজেকশনে এক বা একাধিক কাজ/ধাপ থাকতে পারে। যেমন, যখন কামাল তার একাউন্ট থেকে ২০০০ টাকা জামালের একাউন্টে পাঠাল তখন দুটি কাজ হবে প্রথমে কামালের একাউন্ট থেকে ২০০০ টাকা কমাতে হবে এবং তারপরে জামালের একাউন্টে ২০০০ টাকা বাড়াতে হবে। প্রতিটি ট্রানজেকশন হয় সফল ভাবে সম্পূর্ণ বা কমিট (Commit) হবে নয়তো রোলব্যাক (Rollback) বা ট্রানজেকশনের পূর্বের অবস্থায় ফেরত যাবে। একটি ট্রানজেকশন ডাটাতে যে পরিবর্তন করে সেই পরিবর্তিত ডাটা ডাটাবেজে স্থায়ী ভাবে রেখে দেয়াকে কমিট (Commit) বলে। আর রোলব্যাক (Rollback) হল ট্রানজেকশনের ফলে ডাটাতে যে পরিবর্তন হয়েছে সেগুলোকে বাদ দিয়ে ডাটাকে ট্রানজেকশন শুরুর পূর্বের অবস্থায় ফিরিয়ে নেয়া। উদাহরণস্বরূপ, আমরা আবার কামালের একাউন্ট থেকে ২০০০ টাকা জামালের একাউন্টে পাঠানর ট্রানজেকশনটি বিশ্লেষণ করি। আমরা জানি এই ট্রানজেকশনে দুটি কাজ করতে হবে। মনে করি প্রথম কাজটি সফল হল অর্থাৎ কামালের একাউন্ট থেকে ২০০০ টাকা কমানো হল, তাহলে কামালের একাউন্টে থাকবে ৮০০০ টাকা (ট্রানজেকশন শুরুর আগে কামালের একাউন্টে ১০০০০ টাকা ছিল)। কিন্তু কোনো কারণে দ্বিতীয় কাজটি মানে জামালের একাউন্টে ২০০০ টাকা বাড়ানো গেল না। সুতরাং এই ট্রানজেকশনটিকে রোলব্যাক করতে হবে এবং রোলব্যাক করার পরে কামালের একাউন্টে আবার ১০০০০ টাকা হয়ে যাবে।

ডাটাবেজ ট্রানজেকশন বা ট্রানজেকশনের নিম্নোক্ত চারটি বৈশিষ্ট্য/ধর্ম আছে –

  • Atomicity (এটমিসিটি)
  • Consistency (কন্সিসটেনসি)
  • Isolation (আইসোলেশন)
  • Durability (ডিউরাবিলিটি)

আর এই চারটি বৈশিষ্ট্যের প্রথম অক্ষর গুলো দিয়ে অর্থাৎ A, C, I এবং D নিয়ে আমরা বলি এসিড (ACID)। ডাটাবেজ ম্যানেজমেন্ট সিস্টেম নিজেই ট্রানজেকশনের এই বৈশিষ্ট্যগুলি পরিচালনা করে এবং অ্যাপ্লিকেশন ডেভেলপারদের আশ্বস্ত করে যে প্রতিটি ট্রানজেকশন সেগুলো মেনে চলবে।

আমারা এই চারটি বৈশিষ্ট্য উদাহরনের মাধ্যমে বোঝার চেষ্টা করি –

Atomicity – ডাটাবেজ ট্রানজেকশনের এই গুনটি নিশ্চিত করে যে, হয় একটি ট্রানজেকশনের সবগুলি ধাপ সফল হবে অথবা কোনটিই হবে না। যেমন, মনে করি, জনি তার বন্ধু রবিনকে ১,০০০ টাকা দিতে চায়। এখন জনির ব্যাংক একাউন্টে ১০,০০০ টাকা আছে আর রবিনের একাউন্টে ৪,০০০ টাকা আছে। তাহলে আমাদেরকে একটি ডাটাবেজ ট্রানজেকশন করতে হবে এবং এই ট্রানজেকশনে আমাদের দুটি কাজ/ধাপ সম্পন্ন করেতে হবে। প্রথমে জনির একাউন্ট থেকে ১,০০০ টাকা কেটে নিতে হবে এবং তারপরে রবিনের একাউন্টে সেই ১,০০০ টাকা যোগ করতে হবে। আমারা এই ট্রানজেকশনটিকে সফল বলব যদি দুটি কাজই সম্পূর্ণ হয়। আর ট্রানজেকশনটি সফল/কমিট (Commit) হলে জনির একাউন্টে থাকবে ৯,০০০ টাকা এবং রবিনের একাউন্টে হবে ৫,০০০ টাকা। এখন যদি কোনও কারণে জনির একাউন্ট থেকে টাকা কেটে নেওয়ার পরে তা রবিনের একাউন্টে যোগ করতে না পারি তাহলে আমাদের ট্রানজেকশনটি সফল/কমিট হবে না। আর ট্রানজেকশনটি সফল না হলে জনির ব্যাংক একাউন্টে ১০,০০০ টাকা এবং রবিনের একাউন্টে ৪,০০০ টাকাই থাকবে অর্থাৎ ট্রানজেকশনটি রোলব্যাক (Rollback) হবে। ডাটাবেজ ট্রানজেকশনের এটমিসিটি বৈশিষ্ট্যটি এই বিষয়টির নিশ্চয়তা দান করে।

Consistency – কন্সিসটেনসি এর বাংলা অর্থ সামঞ্জস্য বা সঙ্গতি অথবা মিল। রিলেশনাল ডাটাবেজ ম্যানেজমেন্ট সিস্টেমে কন্সিসটেনসি দ্বারা আমরা বুঝি যে প্রতিটি ডাটাবেজ ট্রানজেকশনকে ডাটাবেজে নির্ধারিত নিয়মের (Database Constraint) সাথে সামঞ্জস্য রেখে ডাটা পরিবর্তন বা নতুন ডাটা যোগ করতে হবে। আমারা নানাবিধ উপায়ে ডাটাবেজ ট্রানজেকশনের উপরে বাধ্যবাধকতা বা নিয়ম (Database Constraint) নির্ধারণ করতে পারি। যেমন, প্রাইমারি কি (primary key), ফরেন কি (foreign key), ট্রিগার (trigger), ইত্যাদি দ্বারা আমরা ট্রানজেকশনের উপরে বাধ্যবাধকতা বা নিয়ম আরোপ করতে পারি। মনে করি আমাদের একটি Student টেবিল আছে এবং studentId হল এই টেবিলের প্রাইমারি কি। আমরা যখন নতুন একজন স্টুডেন্টের ডাটা যোগ (data insert) করতে যাব তখন ডাটাবেজ পরীক্ষা করে দেখবে যে প্রাইমারি কি নিয়মটি মানা হচ্ছে কিনা। নিচের ছবিতে বিষয়টি দেখানো হল –

studentId name
101 John এই ডাটাটি সফল ভাবে যোগ হবে কারন ডাটাবেজ পরীক্ষা করে দেখবে যে 101 দিয়ে আর কোনও স্টুডেন্ট নেই।
102 Simon এই ডাটাটিও সফল ভাবে যোগ হবে কারন ডাটাবেজ পরীক্ষা করে দেখবে যে 102 দিয়ে আর কোনও স্টুডেন্ট নেই।
101 Jack এই ডাটা আমরা যোগ করতে পারবনা কারন ডাটাবেজ পরীক্ষা করে দেখবে যে 101 দিয়ে আগে থেকেই একজন স্টুডেন্ট আছে। অর্থাৎ এই ডাটাবেজ ট্রানজেকশনটি ডাটাবেজে নির্ধারিত প্রাইমারি কি এর নিয়ম অনুযায়ী সফল হবে না।

এভাবেই ডাটাবেজে নির্ধারিত নিয়মগুলো (Database Constraint) প্রতিটি ট্রানজেকশনের সময় পরীক্ষা করে দেখে যেন ট্রানজেকশনটি নিয়মের ব্যত্তয় না ঘটিয়ে সম্পূর্ণ হয়।

Isolation – আইসোলেশনের আভিধানিক অর্থ হল বিচ্ছিন্নতা। আর এই বৈশিষ্ট্যটি নিশ্চিত করে যে একাধিক ট্রানজেকশন নিরাপদে এবং স্বাধীনভাবে কোনরূপ সংঘর্ষ ছাড়া একই সময়ে সম্পূর্ণ হতে পারে, কিন্তু এটা কোন ট্রানজেকশনটি আগে হবে আর কোনটি পরে হবে অর্থাৎ ক্রম (order) নিশ্চিত করে না। উদাহরণস্বরূপ, মনে করি রনির একাউন্টে ১৫,০০০ টাকা আছে। রনি তার দুই বন্ধু কামাল এবং জামাল কে যথাক্রমে ৩,০০০ ও ২,০০০ টাকার দুটি চেক দিল। কামাল এবং জামাল একসাথে ব্যাংকে গেল টাকা তোলার জন্য। তারা দুজন ব্যাংকের দুজন অপারেটরের কাছে একই সময়ে চেক দুটি জমা দিল। এখানে একই সাথে দুটি ট্রানজেকশন হবে, কিন্তু যেহেতু একই একাউন্ট থেকে টাকা তোলা হবে তাই যে কোনও একটি ট্রানজেকশন আগে হবে এবং অন্যটিকে অপেক্ষা করতে হবে। ধরে নেই জামালের ট্রানজেকশনটি আগে শুরু হল তাই কামালের ট্রানজেকশনটি অপেক্ষা করবে। জামালের ট্রানজেকশনটি সম্পূর্ণ হলে কামালের ট্রানজেকশনটি শুরু হবে। অর্থাৎ জামালের ট্রানজেকশনটি যখন শুরু হবে তখন রনির একাউন্টে আছে ১৫,০০০ টাকা আর ট্রানজেকশনটি শেষ হবার পরে রনির একাউন্টে ১৩,০০০ টাকা থাকবে। আর কামালের ট্রানজেকশনটি যখন শুরু হবে তখন রনির একাউন্টে আছে ১৩,০০০ টাকা আর ট্রানজেকশনটি শেষ হবার পরে রনির একাউন্টে ১০,০০০ টাকা থাকবে। যেহেতু দুটি ট্রানজেকশনই একই ডাটার (রনির একাউন্ট) উপর নির্ভরশীল তাই একটিকে অন্যটি শেষ হবার জন্য অপেক্ষা করতে হচ্ছে। যদি এভাবে না হত তাহলে যে ডাটার উপর ট্রানজেকশনগুলি নির্ভরশীল সেই ডাটা একটা সামঞ্জস্যহীন (inconsistent) অবস্থায় চলে যাবে। আর ডাটা যেন কোনও ভাবেই সামঞ্জস্যহীন না হয় সে জন্যই ট্রানজেকশন আইসোলেশন প্রয়োজন।

ডাটাবেজে চারটি আইসোলেশন লেভেল আছে –

  1. Read Uncommitted
  2. Read Committed
  3. Repeatable Read
  4. Serializable

Read Uncommitted হল আইসোলেশনের সর্বনিম্ন লেভেল আর Serializable হচ্ছে সর্বোচ্চ লেভেল। এই আইসোলেশন লেভেলগুলির কিছু সমস্যা আছে যথা, Dirty Reads, Non Repeatable Reads এবং Phantom। নিচে এগুলোর বর্ণনা দেয়া হল –

Dirty Read – একটি ট্রানজেকশন অন্য ট্রানজেকশনের দ্বারা পরিবর্তিত ডাটা যা কমিট (commit) হয়নি সেগুলো পড়তে পারাকেই ডারটি রিড বলে। উদাহরণ স্বরূপ, মনে করি একজন ক্রেতা একটি কেনাকাটার সাইট থেকে কোনও একটি পণ্য ২৮০ টি কিনতে চাইল, এখন তার জন্য ট্রানজেকশন A শুরু হল। ট্রানজেকশন A প্রথমে দেখবে যে ঐ পণ্যের ২৮০ টি স্টকে আছে কিনা। ধরে নেই সাইটের ডাটাবেজে Product_Inventory নামে একটি টেবিল আছে যাতে পণ্যের পরিমান আছে। তো ট্রানজেকশন A সেই Product_Inventory টেবিল থেকে পেল যে তার ইউজার যে পণ্যটি কিনতে চায় তা ৫০০ টি আছে। সুতরাং ট্রানজেকশন A এই অর্ডারটিকে কনফার্ম করল এবং Product_Inventory টেবিলে ঐ পণ্যটির পরিমান ৫০০ থেকে কমিয়ে ২২০ করে দিল। কিন্তু ট্রানজেকশন A এখনও কমিট হয়নি। একই সময়ে আরও একজন ঐ একই সাইট থেকে ঠিক ঐ পণ্যটি ৪০০ টি কিনতে চাইল। ধরে নেই পরের ক্রেতার জন্য ট্রানজেকশন B শুরু হল। ট্রানজেকশন B দেখল যে ঐ পণ্যটি মাত্র ২২০ টি আছে, তাই সে ক্রেতাকে জানাল যে তার অর্ডারটি নেয়া যাচ্ছে না। এরই মধ্যে আবার ট্রানজেকশন A এর যে ক্রেতা সে অর্ডারটি বাতিল করে দিল, তার ফলে ট্রানজেকশন A রোলব্যাক হয়ে গেল। অর্থাৎ Product_Inventory টেবিলে ঐ পণ্যটির পরিমান আবার ৫০০ হয়ে গেল। তার মানে এখানে ট্রানজেকশন B এমন একটি ডাটা পেয়েছিল যা আসলে কমিট হয়নি আর এটাকেই Dirty Read বলে।

Non Repeatable Read – একটি ট্রানজেকশন যদি একই ডাটা দুবার পড়ে আর দুবার দুটি আলাদা ভ্যালু পায় তাকে Non Repeatable Read বলে। যেমন, মনে করি রবিন একটি কেনাকাটার সাইট থেকে কোনও একটি পণ্য ৩০০ টি কিনতে চাইল, এখন তার জন্য ট্রানজেকশন A শুরু হল। ট্রানজেকশন A প্রথমে দেখবে যে ঐ পণ্যের ৩০০ টি স্টকে আছে কিনা। ধরে নেই সাইটের ডাটাবেজে Product_Inventory নামে একটি টেবিল আছে যাতে পণ্যের পরিমান আছে। তো ট্রানজেকশন A সেই Product_Inventory টেবিল থেকে পেল যে রবিন যে পণ্যটি কিনতে চায় তা ৫০০ টি আছে। একই সময়ে জামাল ঐ একই সাইট থেকে ঠিক ঐ পণ্যটি ২৫০ টি কিনতে চাইল। ধরে নেই জামালের জন্য ট্রানজেকশন B শুরু হল এবং এই ট্রানজেকশনটি Product_Inventory টেবিল থেকে পেল যে ঐ পণ্যের ৫০০ টি স্টকে আছে। এদিকে রবিন তার অর্ডারটিকে কনফার্ম করল তার ফলে ট্রানজেকশন A পণ্যটির পরিমান ৫০০ থাকে কমিয়ে ২০০ করে দিল এবং ট্রানজেকশন A কমিট হয়ে গেল। ওদিকে জামাল তার অর্ডারে একটু পরিবর্তন করল, সে ঐ পণ্যটি বাদ দিয়ে অন্য একটি পণ্য ২৫০ টি কিনতে চাইল। ফলে ট্রানজেকশন B আবার Product_Inventory টেবিল থেকে খুঁজে পেল যে এই পরে অর্ডার দেয়া পণ্যটি মাত্র ১০০ টি রয়েছে। তাই ট্রানজেকশন B জামালকে জানাল যে পরে অর্ডার দেয়া পণ্যটি স্টকে ২৫০ টি নেই, জামাল আবার প্রথমে অর্ডার দেয়া পণ্যটি নিতে চাইল। এবার ট্রানজেকশন B Product_Inventory টেবিল থেকে দেখল যে এই পণ্যের আর ২০০ টি অবশিষ্ট আছে এবং অর্ডারটি নেয়া যাচ্ছে না। অর্থাৎ ট্রানজেকশন B একই ডাটা দুবার পড়ে দুটি ভিন্ন ভ্যালু (পণ্যের দুটি ভিন্ন পরিমান) পেল। ট্রানজেকশন B যে সমস্যাটির মুখে পড়েছে তাকে Non Repeatable Read বলে।

Phantom – মনে করি কেনাকাটার সাইটের ডাটাবেজে Order নামে একটি টেবিল আছে এবং এই টেবিলে সব অর্ডারের ডাটা আছে। এখন একজন জানতে চাইল মোট কতগুলো অর্ডার হয়েছে। তো একটি ট্রানজেকশন A শুরু হল যা কিনা Order টেবিল থেকে মোট কতটি অর্ডার হয়েছে তা বের করবে। এদিকে একই সময়ে অন্য একটি ট্রানজেকশন B নতুন একটি ডাটা Order টেবিলে যোগ করল। এখন যদি ট্রানজেকশন A আবার Order টেবিল থেকে মোট কতটি অর্ডার হয়েছে তা বের করে তাহলে ভিন্ন ভ্যালু পাবে। এই ধরনের ঘটনাকে Phantom বলে। Non Repeatable Read এর সাথে Phantom এর পার্থক্য হচ্ছে এখানে ডাটা ভিন্ন হচ্ছে নতুন ডাটা যোগ করার ফলে বা ডাটা মুছে ফেলার কারণে (insert or delete)।

নিচের টেবিলে কোন আইসোলেশন লেভেলে কোন অসুবিধা গুলো হয় বা হয় না তা দেখানো হল –

Isolation Level Dirty Read Non Repeatable Read Phantom
Read Uncommitted হয় হয় হয়
Read Committed হয় না হয় হয়
Repeatable Read হয় না হয় না হয়
Serializable হয় না হয় না হয় না

Durability – ডিউরাবিলিটি শব্দের মানে স্থায়িত্ব। ডাটাবেজ ট্রানজেকশনের এই ধর্মটি নিশ্চিত করে যে, যখন একটি ট্রানজেকশন সফল হয় তখন তার ফলে যে ডাটা পরিবর্তন হয় তা যেন স্থায়ীভাবে ডাটাবেজে থেকে যায়। এর অর্থ হল, সব ধরনের অঘটন/দুর্ঘটনা সত্ত্বেও (System Failure/System Crash) বা সিস্টেম রিস্টার্ট (System Restart) হলেও সফল ট্রানজেকশনের দ্বারা ডাটাতে যে পরিবর্তন হয়ছে তা স্থায়ী ভাবে ডাটাবেজে সংরক্ষিত থাকবে। যেমন, মনে করি আমাদের একটি বাসের টিকেট বুকিং সিস্টেম আছে। এই বুকিং সিস্টেমে রবিন একটি টিকেট বুকিং দিল এবং তার বুকিংটি সফল হল, আর এরপরেই এই বুকিং সিস্টেমটি বৈদ্যুতিক গোলযোগের (Power Failure) কারণে (System Crash) ক্র্যাশ করল। কিন্তু যেহেতু রবিনের বুকিংটি সফল হয়েছিল তাই বুকিং সিস্টেমটি পুনরায় চালু হবার পরে তার করা বুকিংটি ডাটাবেজে পাওয়া যাবে।

আশা করি লেখাটি ডাটাবেজ ট্রানজেকশন ও এসিড সম্বন্ধে বুঝতে সাহায্য করবে।

লেখকঃ মোঃ শফিউজ্জামান রাজিব, ডাটাবেজ ও বিগ ডাটা প্রফেশনাল।