বাবল সর্ট(Bubble sort) অ্যালগরিদম

 

গত পর্বে আমি সিলেকশন সর্ট(Selection sort) অ্যালগরিদম নিয়ে আলোচনা করেছিলাম এই পর্বে আরও একটি সহজ সর্টিং অ্যালগরিদম নিয়ে আলোচনা করবো নাম বাবল সর্ট(Bubble sort) ।

কম্পিউটার সায়েন্সে যতগুলো সর্টিং অ্যালগরিদম রয়েছে তার-মধ্যে সবচেয়ে সহজ অ্যালগরিদম বলা হয় বাবল সর্ট কে । তো চলুন আজাইরা ইন্ট্রো গল্প বাদ দিয়ে বাবল সর্ট(Bubble sort) অ্যালগরিদম নিয়ে আলোচনা করা যাক ।

বাবল সর্ট(Bubble sort) অ্যালগরিদম :-

এই অ্যালগোরিদমের মূল বিষয় হলো, পরপর দুইটি উপাদানের মধ্যে তুলনা করে তাদের ক্রম অনুসারে রাখা । যেমন : - নিচের visualization টি লক্ষ্য করি :-

ধরি, আমার কাছে একটি অ্যারে আছে [400,200,100,300] । এখন এই অ্যারেটি আমি বাবল সর্ট(Bubble sort) অ্যালগরিদম ব্যাবহার করে ছোট থেকে বড় ক্রমে অর্থাৎ Ascending Order এ সাজাতে চাই ।

উপরোক্ত অ্যারেতে মোট ৪টি উপাদান বাঁ সংখ্যা আছে । আপনি চাইলে যেকোনো সাইজের অ্যারে নিয়ে কাজ করতে পারবেন আমার সময় বাঁচানোর জন্য আমি কম সংখ্যক উপাদানসুমহের অ্যারেটি নিলাম । চলুন কাজে আসা যাক -

স্টেপ(০১) :- প্রথমে আমি অ্যারের প্রথম ২টি উপাদান নিবো সেক্ষেত্রে উপাদানগুল হলো 400 ও 200 । এখন এই ২টি সংখ্যার মধ্যে আমি তুলনা করবো যে সংখ্যাটি ছোট তাকে প্রথমে এবং বড় সংখ্যাটিকে তার পরে রাখবো । যেহেতু, 200 ছোট তাই 200 কে প্রথমে এবং 400 কে তার পরে রাখলাম এখন অ্যারেটি হবে -

[200,400,100,300]

স্টেপ(০২) :- এবার 400 এবং 100 এর তুলনা করবো সেক্ষেত্রে ছোট সংখ্যাটি 100 এবং বড় সংখ্যাটি 400 । তাহলে 100 কে আগে এবং 400 কে পরে রাখলাম -

[200,100,400,300]

স্টেপ(০৩) :- এবারে 400 এবং 300 এর মধ্যে তুলনা করি । 400 > 300 এক্ষেত্রে 300 ছোট এবং 400 বড় তাহলে 300 কে প্রথমে 400 কে পরে রাখি -

 [200,100,300,400]

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

স্টেপ(০৪) :- 200 এবং 100 এর মধ্যে তুলনা করি এক্ষেত্রে 100 ছোট এবং 200 বড় সংখ্যা । তাহলে 100 কে প্রথমে এবং 200 কে তার পরের স্থানে রাখি -

 [100,200,300,400]

স্টেপ(০৫):-  200 ও 300 এর মধ্যে যদি তুলনা করি তাহলে 200 হবে ছোট এবং 300 হবে বড় সংখ্যা । এখন এদের স্থানের অদল-বদল করতে হবে অর্থাৎ 200 কে আগে এবং 300 কে পরের স্থানে রাখতে হবে কিন্তু অ্যারের দিকে লক্ষ করলে দেখতে পারবো যে 200 এবং 300 তাদের যথাযথ স্থানেই রয়েছে । 

 

[100,200,300,400]

স্টেপ(০৬) :- 100 ও 200 এর মাঝে তুলনা করি স্পষ্ট দেখতে পাচ্ছি 100 ও 200 তাদের যথাযথ স্থানেই রয়েছে । সাথে বাকি সংখ্যাগুলোও কিন্তু ঠিকঠাক স্থানেই রয়েছে । এ পর্যায়ে এসে বলতে পারি আমাদের অ্যারেটি সর্টেড অর্থাৎ ছোট থেকে বড় ক্রমে সাজানো আছে ।

 আশা করি, আপনারা বাবল সর্ট(Bubble sort) অ্যালগরিদম বুঝতে পেরেছেন যদি একবারে বুঝে না থাকেন তাহলে আরেকবার পড়তে হবে । চলুন এখন ইমপ্লিমেন্টেশন বাঁ কোড লিখা যাক -

In Python :-

def bubbleSort(arr):
    # i এর মান  0 থেকে len(arr) এর আগ পর্যন্ত ১ করে বাড়াই
    for i in range(len(arr)):

        # j এর মান 0 থেকে len(arr)-i-1 এর আগ পর্যন্ত ১ করে বাড়াই
        for j in range(0, len(arr) - i - 1):

            # arr[j] > arr[j+1] সত্য হয় তাহলে দুইটিকে অদল-বদল করি

            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

In JavaScript :-

const optimizedBubbleSort = (arr) => {
  // i এর মান  0 থেকে arr.length এর আগ পর্যন্ত ১ করে বাড়াই
  for (let i = 0; i < arr.length; i++) {
    // j এর মান 0 থেকে arr.length-i-1 এর আগ পর্যন্ত ১ করে বাড়াই
    for (let j = 0; j < arr.length - i - 1; j++) {
      // arr[j] > arr[j+1] সত্য হয় তাহলে দুইটিকে অদল-বদল করি
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
};

যেকোনো অ্যালগরিদম বাঁ ডেটা-স্ট্রাকচারের মূল কনসেপ্ট যদি আপনি ভালোভাবে বুঝতে পারেন তাহলে যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যাবহার করেই ইমপ্লিমেন্ট করতে পারবেন ।

চলুন বাবল সর্ট(Bubble sort) অ্যালগরিদমের টাইম ও স্পেস কমপ্লেক্সিটি বের করা যাক -

টাইম কমপ্লেক্সিটি(Time Complexity) :

উপরোক্ত কোড লক্ষ করলে দেখবো প্রথম লুপটি চলে i = 0 থেকে n পর্যন্ত । এবং ভেতরের অর্থাৎ ২য় লুপটি চলে j = 0 থেকে n-i-1 পর্যন্ত ।

• যখন i = 0, তখন ভেতরের লুপটি চলে j = 0 থেকে j = n - i - 1 অর্থাৎ 3 বার ।

• আবার i = 1 হলে, ভেতরের লুপটি চলে j = 1 থেকে j = n - i - 1 অর্থাৎ 2 বার ।

এভাবেই যতক্ষণ না লুপটি শেষ হয় চলতেই থাকবে ।

এখন আমরা খুব সহজেই বলে দিতে পারি যে, উক্ত প্রোগ্রামের টাইম কমপ্লেক্সিটি(Time Complexity) O(n*(n-i-1)) 

অর্থাৎ O(n*(n-1)) ।

=> n*(n - 1)

=> n² - n

=> O(n² - n)

O(n² - n) কে আমরা O(n²) লিখতে পারি কারণ n² এর তুলনায় n ছোট ।

স্পেস কমপ্লেক্সিটি(Space Complexity) :

উপরের প্রোগ্রামে একটু খেয়াল করলে দেখতে পারবো যে, প্রোগ্রামে একটি লিস্ট বা অ্যারে প্যারামিটার হিসেবে নেওয়া হয়েছে । এবং যা কাজ-কারবার করা হয়েছে তা এই অ্যারে বা লিস্টের মধ্যেই । এই অ্যারে বা লিস্টে কিন্তু কোনো নতুন উপাদান সংযোজন, বিয়োজন ইত্যাদি কিছুই করা হয় নাই । তাহলে বলতে পারি অ্যারে বা লিস্টটি Constant । এখন আপনার কাছে আমার প্রশ্ন এই প্রোগ্রামের স্পেস কমপ্লেক্সিটি(Space Complexity) কত ?

আশা করি পেরেছেন হ্যাঁ স্পেস কমপ্লেক্সিটি(Space Complexity) হচ্ছে - O(1) ।

ব্রাভো, যদি এতদূর পর্যন্ত আপনি ঠিকঠাক ভাবে পড়ে থাকেন তাহলে আমি ধরে নিতেই পারি বাবল সর্ট(Bubble sort) অ্যালগরিদম সম্পর্কে ভালো একটা দখল চলে আসছে ।

যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে আমি কিন্তু Ascending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজিয়েছি এখন আপনি বাবল সর্ট(Bubble sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে Descending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজানোর চেষ্টা করবেন । 

খুবই সহজ একটি কাজ আশা করি পারবেন শুভকামনা রইলো ।

Read More

সিলেকশন সর্ট(Selection sort) অ্যালগরিদম

কোনো উপাদান বাঁ ডাটাসমূহকে একটি নির্দিষ্ট ক্রমে সাজানোর প্রক্রিয়াই হলো সর্টিং(Sorting) । সর্টিং(Sorting) আমরা দুই ভাবে করতে পারি -

 ১। Ascending Order

  এবং 

২। Descending Order

১। Ascending Order :-

ছোট থেকে বড় ক্রমে সাজানোর প্রক্রিয়াকে বলা হয় Ascending Order । যেমন :-

• শ্রেণিকক্ষের হাজিরা খাতায় শিক্ষার্থীদের নামগুলো রোল নম্বর অনুযায়ী সাজানো থাকে ।

২। Descending Order :-

বড় থেকে ছোট ক্রমে সাজানোর প্রক্রিয়াকে বলা হয় Descending Order । যেমন :-

• ফাইনাল পরীক্ষা শেষে রেজাল্ট শিটে শিক্ষার্থীদের নামগুলো মোট নম্বর অনুযায়ী বড় থেকে ছোট ক্রমে সাজানো থাকে ।

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

সিলেকশন সর্ট(Selection sort) :-

এই সর্টিং অ্যালগরিদমের মূল বিষয় হলো, প্রতি ইটারেশনে ডাটাসমূহ থেকে একটি সঠিক উপাদানকে সিলেক্ট করা এবং তাকে অন্য আরেকটি উপাদানের সাথে অদল-বদল করে(যদি প্রয়োজন হয়) সঠিক জায়গায় এসাইন করা ।

নিচে  সিলেকশন সর্ট(Selection sort) এর  Visualization লক্ষ্য করুন :-

ধরি, আমাদের কাছে [100,400,300,600,500] এই অ্যারেটি আছে । এখন এই অ্যারেটিকে সিলেকশন সর্ট(Selection sort) অ্যালগরিদম ব্যাবহার করে Descending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজাতে হবে।

স্টেপ(১) :- প্রথমে উপরোক্ত অ্যারে থেকে সবচেয়ে বড় সংখ্যাটিকে সিলেক্ট করি এক্ষেত্রে 600 হচ্ছে সবচেয়ে বড় সংখ্যা । এখন 600 কে সবার প্রথমে নিয়ে আসতে হবে এজন্য অ্যারের প্রথম উপাদান 100 এর সঙ্গে 600 এর স্থান অদল-বদল করি । অদল-বদল শেষে আমাদের অ্যারেটি দাঁড়াবে এরকম -

[600,400,300,100,500]

স্টেপ(২) :- এখন অ্যারের দিকে লক্ষ করলে দেখতে পারবো যে, অ্যারের প্রথম উপাদানটি সবচেয়ে বড় । তাই প্রথম উপাদান বাদে অ্যারের বাকি উপাদানগুলোর মধ্যে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি এক্ষেত্রে সংখ্যাটি হচ্ছে 500 । এরপর 400 এর সাথে 500 এর  স্থান অদল-বদল করি তাহলে অ্যারেটি দাঁড়াবে -

[600,500,300,100,400]

স্টেপ(৩) :- অ্যারের প্রথম দুটি উপাদান সর্ট করা শেষ এখন বাকি তিনটি(300,100,400) উপাদান সর্ট করতে হবে । তাহলে এই তিনটি উপাদানের মধ্যে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি সংখ্যাটি হলো 400 । এরপর 300 এর সাথে 400 এর স্থান অদল-বদল করি এখন অ্যারেটি হবে -

[600,500,400,100,300]

স্টেপ(৪) :- এখন আমরা নিশ্চিত যে, অ্যারের প্রথম ৩টি উপাদান সর্টেড রয়েছে তাহলে বাকি ২টি(100,300) উপাদান থেকে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি এক্ষেত্রে সংখ্যাটি হচ্ছে 300 । এখন 100 এর সাথে 300 এর স্থান অদল-বদল করি । অদল-বদল শেষে অ্যারেটি হবে -

[600,500,400,300,100]

যেহেতু, অ্যারের ৫টি উপাদানের মধ্যে প্রথম ৪টি উপাদান বড় থেকে ছোট ক্রমে সাজানো । সেক্ষেত্রে আমরা নিশ্চিত যে, অ্যারের শেষ উপাদান অর্থাৎ 100 তার সঠিক জায়গাতেই আছে এর কোনো অদল-বদল করতে হবে নাহ । তাহলে আমাদের ফাইনাল অর্থাৎ সর্টেড অ্যারেটি হলো -

[600,500,400,300,100]

আশা করি, আপনারা সিলেকশন সর্ট(Selection sort) অ্যালগরিদমটি বুঝতে পেরেছেন যদি একবারে বুঝে না থাকেন তাহলে আরেকবার পড়তে হবে । চলুন এখন ইমপ্লিমেন্টেশন বাঁ কোড লিখা যাক -

পাইথনে ইমপ্লিমেন্টেশন :-

def selectionSort(arr):
    # i এর মান  0 থেকে len(arr) - 1 এর আগ পর্যন্ত ১ করে বাড়াই
    for i in range(len(arr) - 1):
        # largest নামে variable নিই এবং i এসাইন করি
        largest = i

        # j এর মান i+1 থেকে len(arr) এর পর্যন্ত ১ করে বাড়াই

        for j in range(i+1, len(arr)):

          # arr[largest] < arr[j] যদি সত্য হয় তাহলে largest এসাইন করি
            if arr[largest] < arr[j]:
                largest = j

        # যদি largest এবং i সমান না হয় তাহলে সংখ্যা দুইটি অদল-বদল করি
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
    return arr

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন :-

const selectionSort = (arr) => {
  // i এর মান  0 থেকে arr.length - 1 এর আগ পর্যন্ত ১ করে বাড়াই
  for (let i = 0; i < arr.length - 1; i++) {
    // largest নামে variable নিই এবং i এসাইন করি
    let largest = i;
    // j এর মান i+1 থেকে arr.length এর পর্যন্ত ১ করে বাড়াই
    for (let j = i + 1; j < arr.length; j++) {

      // arr[largest] < arr[j] যদি true হয় তাহলে largest এ j এসাইন করি

      if (arr[largest] < arr[j]) {
        largest = j;
      }
    }

    // যদি largest এবং i সমান না হয় তাহলে সংখ্যা দুইটি অদল-বদল করি
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
    }
  }
  return arr;
};

যেকোনো অ্যালগরিদম বাঁ ডাটা-স্ট্রাকচারের মূল কনসেপ্ট যদি আপনি ভালোভাবে বুঝতে পারেন তাহলে যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যাবহার করেই ইমপ্লিমেন্ট করতে পারবেন ।

চলুন সিলেকশন সর্ট(Selection sort) অ্যালগরিদমের টাইম ও স্পেস কমপ্লেক্সিটি নিয়ে একটু অ্যানালাইসিস করা যাক -

টাইম কমপ্লেক্সিটি(Time Complexity) :

উপরোক্ত কোড লক্ষ করলে দেখবো প্রথম লুপটি চলে i = 0 থেকে n-1 পর্যন্ত । এবং ভেতরের অর্থাৎ ২য় লুপটি চলে j = i+1 থেকে n-1 পর্যন্ত ।

• যখন i = 0, তখন ভেতরের লুপটি চলে j = 0 থেকে j = n - 1 অর্থাৎ 4 বার ।

• আবার i = 1 হলে, ভেতরের লুপটি চলে j = 1 থেকে j = n - 1 অর্থাৎ 3 বার ।

• i = 2 হলে, ভেতরের লুপটি চলে j = 2 থেকে j = n - 1 অর্থাৎ 2 বার । এভাবেই যতক্ষণ না লুপটি শেষ হয় চলতেই থাকবে ।

একটু লক্ষ করলে দেখতে পারবো যে, প্রথম লুপটি n সংখ্যক বার চললে তার ভেতরের লুপটি চলতেছে m সংখ্যক বার । তাহলে টাইম কমপ্লেক্সিটি(Time Complexity) দাঁড়াবে O(n *  m) । এখানে যেহেতু m এর মান n এর সমান তাহলে টাইম কমপ্লেক্সিটি(Time Complexity) বলতে পারি O(n  * n) বা O(n²) ।

স্পেস কমপ্লেক্সিটি(Space Complexity) :

উপরের প্রোগ্রামে একটু খেয়াল করলে দেখতে পারবো যে, প্রোগ্রামে একটি লিস্ট বা অ্যারে প্যারামিটার হিসেবে নেওয়া হয়েছে । এবং যা কাজ-কারবার করা হয়েছে তা এই অ্যারে বা লিস্টের মধ্যেই । এই অ্যারে বা লিস্টে কিন্তু কোনো নতুন উপাদান সংযোজন, বিয়োজন ইত্যাদি কিছুই করা হয় নাই । তাহলে বলতে পারি অ্যারে বা লিস্টটি Constant । এখন আপনার কাছে আমার প্রশ্ন এই প্রোগ্রামের স্পেস কমপ্লেক্সিটি(Space Complexity) কত ?

আশা করি পেরেছেন হ্যাঁ স্পেস কমপ্লেক্সিটি(Space Complexity) হচ্ছে - O(1) ।

ব্রাভো, যদি এতদূর পর্যন্ত আপনি ঠিকঠাক ভাবে পড়ে থাকেন তাহলে আমি ধরে নিতেই পারি সিলেকশন সর্ট(Selection sort) সম্পর্কে ভালো একটা দখল চলে আসছে ।

যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে আমি কিন্তু Descending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজিয়েছি এখন আপনি সিলেকশন সর্ট(Selection sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে Ascending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজানোর চেষ্টা করবেন । 

খুবই সহজ একটি কাজ আশা করি পারবেন শুভকামনা রইলো 🥰।

---

Read More

চেক প্যালিনড্রোম (Palindrome) - using Stack

 

আমি বেশ কিছুদিন আগে Stack এবং Queue ডাটা-স্ট্রাকচার নিয়ে আলোচনা করেছিলাম সাথে জাভাস্ক্রিপ্ট এবং পাইথন দিয়ে ইমপ্লিমেন্টও করেছিলাম । তো আজকে আমি, একটি সুপরিচিত এবং সহজ প্রব্লেম নিয়ে আলোচনা করবো এবং Stack ডাটা-স্ট্রাকচার দিয়ে সমাধান করবো ।

আমরা জানি, Stack ডাটা-স্ট্রাকচার LIFO(Last In First Out) প্যারাডাইম মেনে চলে অর্থাৎ এখানে কোনো ভ্যালু শেষে এড করা হলে তা প্রথমে ডিলিট হয়ে যাবে । আপনি যদি Stack ও Queue ডাটা-স্ট্রাকচার সম্পর্কে না জেনে থাকেন তাহলে নিচের দেওয়া লিঙ্কগুলো থেকে পরে নিতে পারেন -

• Stack ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Queue ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Stack ডাটা-স্ট্রাকচার ইন পাইথন
• Queue ডাটা-স্ট্রাকচার ইন পাইথন

এখন, আসল কাজে ফিরে আসা যাক - আপনাকে একটি ফাংশন লিখতে হবে যা প্যারামিটার হিসেবে একটি স্ট্রিং নিবে । যদি স্ট্রিং টি Palindrome হয় তাহলে true নতুবা false রিটার্ন করবে ।

Palindrome String :-

যদি কোনো স্ট্রিং ডানে এবং বামে অর্থাৎ উভয় থেকে একই হয় তাহলে তাকে Palindrome String বলা যায় । যেমন :- mam, madam, racecar ইত্যাদি ।

এখন এই প্রব্লেমটি আমরা অনেক ভাবেই সমাধান করতে পারি আবার এক লাইনেও সমাধান করতে পারি । কিন্তু আমরা অন্যভাবে প্রব্লেমটি সমাধান না করে Stack দিয়ে কিভাবে সমাধান করতে হয় তা দেখবো এবং বোঝার চেষ্টা করবো ।

ধরি, আমাদের কাছে একটি স্ট্রিং আছে "MaM" । আমরা চাইলে সরাসরি Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট করে তা দিয়ে সমাধান করতে পারি । কিন্তু, Stack ডাটা-স্ট্রাকচার সরাসরি ইমপ্লিমেন্ট না করেও জাভাস্ক্রিপ্টের অ্যারে অথবা পাইথনের লিস্ট দিয়ে খুব সহজেই Stack এর কাজ করে ফেলতে পারি তো চলুন শুরু করা যাক -

স্টেপ(০১) :- প্রথমে, "MaM" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "M" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "M" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["M"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "a" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["M", "a"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "M" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["M", "a", "M"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে - 

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "M" 

contains = ["M", "a"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "Ma" 

contains = ["M"]

এখন,  contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "MaM" 

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার এবং word এর মান একই সেহেতু "MaM" একটি Palindrome স্ট্রিং ।

আরেকটি উদাহরণ :-

ধরি আমাদের কাছে একটি str নামে স্ট্রিং আছে,

 str = "abc" ।

স্টেপ(০১) :- প্রথমে, "abc" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "a" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "a" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["a"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "b" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["a", "b"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "c" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["a", "b", "c"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো, যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে - 

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "c" 

contains = ["a", "b"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cb" 

contains = ["a"]

এখন, contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cba" 

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার ছিলো "abc" এবং word এর মান "cba" সেহেতু "abc" একটি Palindrome স্ট্রিং নয়।

তো চলুন এখন কোড লিখা যাক -

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন -

const isPalindrome = (str) => {
  let contains = [];
  for (let i = 0; i < str.length; i++) {
    contains.push(str[i]);
  }

  let word = "";
  while (contains.length > 0) {
    word += contains.pop();
  }
  return word === str;
};

Output :

isPalindrome("MaM");  // true
isPalindrome("abc"); // false

পাইথনে ইমপ্লিমেন্টেশন :-

def isPalindrome(str):
    contains = []
    for item in str:
        contains.append(item)

    word = ""
    while len(contains) > 0:
        word += contains.pop()

    return word == str

Output :

isPalindrome("MaM"); # True
isPalindrome("abc"); # False

কোড বিশ্লেষণ :-

উপরোক্ত কোডে, প্রথমে contains নামে একটি অ্যারে বা লিস্ট নিয়েছি । তারপর, স্ট্রিং এ লুপ থ্রু করেছি এবং প্রত্যেকতা উপাদানকে contains নামের অ্যারে বা লিস্টে পুশ করে দিয়েছি ।

word নামে একটি ফাকা স্ট্রিং নিয়েছি এবং contains অ্যারেতে একটি লুপ থ্রু করেছি । লুপটি ততক্ষণ চলবে যতক্ষণ পর্যন্ত contains এর সাইজ 0 থেকে বড় থাকবে । এবং প্রত্যেক ইটারেশনে word এর সাথে contains এর শেষ উপাদানটি রিমুভ হয়ে যোগ হতে থাকবে । এক পর্যায়ে আমাদের লুপটি শেষ হবে । তখন যদি word এবং str সমান হয় তাহলে funciton টি আমাদেরকে true রিটার্ন করবে নতুবা false রিটার্ন করবে ।

কোডের টাইম ও স্পেস উভয় কমপ্লেক্সিটি হবে ওর্ডার অব এন অর্থাৎ O(n) ।

Read More

কিউ(Queue) ডাটা-স্ট্রাকচার ইন পাইথন

 

কম্পিউটার সাইন্সে আরও একটি কমন এবং বহুল ব্যবহৃত ডাটা-স্ট্রাকচার হলো Queue । আমরা আজকে এই ডাটা-স্ট্রাকচার সমন্ধে শিখতে যাচ্ছি, তবে আশা করি যে আপনি Stack ডাটা-স্ট্রাকচার সম্পর্কে জানেন।

যদি নাহ যেনে থাকেন তাহলে এখানে পড়ুন ।

- Queue কি ?

Queue একটি লিনিয়ার(Linear) ডাটা-স্ট্রাকচার যা FIFO প্যাঁরাডাইম(paradigm) মেনে চলে । FIFO এর পূর্ণরূপ হইলো - First In First Out অর্থাৎ Queue এ কোনো একটা ভ্যালু প্রথমে সংযোজন করা হইলে তা প্রথমেই বিয়োজন হবে। এখন একটু রিয়েল লাইফ উদাহরণ দেওয়া যাক -

- রিয়েল লাইফ উদাহরণ -

গত ব্লগে আপনার মামার মেয়ের তো বিয়ে হয়ে গেলো কিন্তু সেই বিয়েতে আপনি থালা বিতরন ছাড়া আর কিছুই করতে পারলেন নাহ । কিন্তু আপনি কি হাল ছেড়ে দেওয়ার মতো মানুষ ? নাহ অবশ্যই নাহ ।

হ্যাঁ আপনি আপনার মামাতো বোন কে পান নাই তাতে কি হয়েছে পৃথিবীতে কি মেয়ের অভাব নাকি ? তাই আপনিও আপনার মামার মেয়ের মতো বিয়ে করে ফেললেন । এখন আপনার মামাতো বোন কে তো দেখাতে হবে নাকি ? তাই আপনি প্ল্যান করলেন যে, হানিমুনে যাবেন দেশের কোথাও।

এই সুবাধে আপনি আগামিকালের টিকিট আজকেই বুক করতে গেলেন কিন্তু ওমা এ কি!

টিকিট কাউন্টারে তো অনেক লোক লাইন হয়ে দাঁড়িয়ে আছে । এবং তারা সিরিয়াল মোতাবেক একজনের পর একজন টিকিট নিচ্ছে । এখন আপনার সিরিয়াল ধরেন ১৮ নম্বর। তাহলে যখন আপনার সিরিয়াল আসবে তখনই আপনি টিকিট নিতে পারবেন ।

এখন আপনি মনে মনে ভাবতেছেন যে, ইস! যদি খানিকটা আগে আসতে পারতাম তাহলে আগেই যাইতাম । আসলেই, আগে আসলে আগেই যাইতে পারতেন । কিন্তু কি আর করার ।

 

আশা করি আপনি এখানে Queue ডাটা-স্ট্রাকচারের আচরণ ধরতে পেরেছেন । যদি এখনও আপনার খাটাস ব্রেইনে কিছু নাহ ঢুকে থাকে তাহলে চলেন আরেকটু বোঝা-বুঝি সেরে ফেলা যাক -

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

এভাবে পর পর ৬ জন মানুষ তাদের সিরিয়াল মেইন্টেইন করে টিকিট নিয়ে সেখান থেকে চলে যাবে। তাহলে বিষয়টা দাড়ালো যে, প্রথম যে মানুষটা লাইনে ইন হইলো সেই মানুষটাই প্রথমেই টিকিট নিয়ে লাইন থেকে আউট হয়ে গেলো । তাহলে কিন্তু এখানেও FIFO প্যাঁরাডাইম(paradigm) মেনে চললো অর্থাৎ - First In First Out।

- Common operations on Queue -

যে কোনো ল্যাংগুয়েজেই হোক নাহ কেনো Queue ইমপ্লিমেন্ট(implement) করার সময় মাস্ট(must) আমাদেরকে দুইটা মেথড তৈরি করতেই হবে-

1. enqueue - Queue এ আইটেম সংযোজন ।
2. dequeue - Queue থেকে আইটেম বিয়োজন ।

এইখানে মেথডস নেইম যে enqueue এবং dequeue ই হবে সেরকম বাধা-ধরা কোনো নিয়ম নেই । আপনি চাইলে add , remove বা আপনার সুবিধা-মতো যেকোনো নেইম দিতে পারেন । তবে এই দুইটা মেথড ছাড়াও Queue এ আমাদের প্রয়োজন মতো অনেক মেথডস তৈরি করতে পারি ।

- Queue এ আমরা যে মেথডস গুলো তৈরি করতে যাচ্ছি -

1. enqueue() - Queue এ আইটেম সংযোজন ।

2. dequeue() - Queue থেকে আইটেম বিয়োজন ।

3. size() - Queue এ আইটেম কতগুলো আছে তা জানতে।

4. isEmpty() - Queue খালি কি নাহ তা জানতে।

5। topElement() - Queue থেকে প্রথম আইটেম নেওয়া যাবে ।

6। tailElement() - Queue থেকে শেষ আইটেম নেওয়া যাবে ।

- Implementing a queue -

Queue ইমপ্লিমেন্ট(implement) করতে আমি লিস্ট(list) এবং ক্লাস(class) কে বেছে নিবো । তবে লিঙ্কড-লিস্ট(linked-list) দিয়েও চাইলে করতে পারেন । তবে, সামনের কোনোদিন সময় করে লিঙ্কড-লিস্ট(linked-list) দিয়ে কিভাবে Queue ইমপ্লিমেন্ট(implement) করতে হয় তা নিয়ে একটি Article লিখার চেষ্টা করবো ।

- ক্লাস(class) ডিফাইন -

class Queue :
    # code here

- কন্সট্রাক্টর(constructor) তৈরি -

def __init__(self) :
    self.data = []

এখানে একটি constructor ফাংশন নিয়েছি এবং data নামে একটা প্রোপার্টি নিয়েছি যা মুলত একটা লিস্টকে হোল্ড করে । এই লিস্টই মুলত Queue এর আইটেমগুলো কে কনট্রোল করবে ।

- enqueue() method -

এই মেথডের সাহায্যে কোনো আইটেমকে Queue এর প্রথমে সংযোজন করা যাবে ।

def enqueue(self, item):
    self.data.append(item)

লিস্টের append মেথডের সাহায্য নেওয়া হয়েছে যা এলিমেন্টকে খুব সহজেই Queue এ যুক্ত করে দিবে ।

- dequeue() method -

def dequeue(self):
    if len(self.data):
        return self.data.pop(0)
    else:
        return "dequeue failed!"

এখানে বলা হয়েছে যে যদি Queue এর লেন্থ শুন্য(0) থেকে বড় হয় তাহলে Queue থেকে শেষের এলিমেন্টকে ডিলিট করে দিবে। শেষের এলিমেন্ট সেইটাই যেইটা Queue এ প্রথমে এড করা হবে । আর বুঝতেই পারছি যে, শুন্য(0) থেকে বড় মানে Queue এ এলিমেন্ট আছে।

আর যদি Queue এ এলিমেন্ট নাহ থাকে তাহলে dequeue failed! রিটার্ন করবে ।

- size method -

Queue এ কতোগুলো আইটেম আছে তা এই সাইজ(size) মেথড রিটার্ন করবে ।

def size(self) :
    return len(self.data);

- isEmty method -

Queue খালি কি নাহ তা জানা যাবে isEmty() মেথডের এর সাহায্যে । যদি Queue এ আইটেম থাকে তাহলে false আইটেম নাহ থাকলে true রিটার্ন করবে।

def isEmpty(self):
    return len(self.data) == 0

- topElement method -

def topElement(self):
    if(len(self.data)):
        return self.data[0]
    else:
        return "queue is empty!"

Queue থেকে প্রথম এলিমেন্ট নেওয়া যাবে topElement মেথডের সাহায্যে ।

- tailElement method -

def tailElement(self):
    if(len(self.data)):
        return self.data[-1]
    else:
        return "queue is empty!"

Queue থেকে শেষ এলিমেন্ট নেওয়া যাবে tailElement মেথডের সাহায্যে ।

- Final Queue -

class Queue:
    # constructor
    def __init__(self):
        self.data = []

    # enqueue method
    def enqueue(self, item):
        self.data.append(item)

    # dequeue method
    def dequeue(self):
        if len(self.data):
            return self.data.pop(0)
        else:
            return "dequeue failed!"

    # size method
    def size(self):
        return len(self.data)

    # isEmpty method
    def isEmpty(self):
        return len(self.data) == 0

    # topElement method
    def topElement(self):
        if(len(self.data)):
            return self.data[0]
        else:
            return "queue is empty!"

    # tailElement
    def tailElement(self):
        if(len(self.data)):
            return self.data[-1]
        else:
            return "queue is empty!"

আপনি চাইলে Queue এ প্রয়োজন মতো আরও অনেক মেথড যুক্ত করতে পারেন । এখন আমাদের তৈরি করা Queue টেস্ট করে দেখবো যে সব কিছু ঠিকমতো কাজ করছে কি নাহ ।

- Create a Queue -

# create a queue
queue = Queue();

- Add Item To Queue -

queue.enqueue("shakil");
queue.enqueue("torikus");
queue.enqueue("morshed");
queue.enqueue("afifa");

# queue
[ 'afifa', 'morshed', 'torikus', 'shakil' ]

যেহেতু queue এ সর্বপ্রথমে shakil কে সংযোজন করা হয়েছে এখন যদি বিয়োজন করি তাহলে -

- Remove last item which is the first item -

print(queue.dequeue()); # shakil

# [ 'afifa', 'morshed', 'torikus' ]

যেহেতু queue এ সর্বপ্রথম shakil কে সংযোজন করা হয়েছে তাই dequeue() করার পর shakil কেই প্রথম বিয়োজন করে ফেলছে ।

- Length in Queue -

print(queue.size());
# 3

আমরা দেখতে পাইতেছি যে, queue এ তিনটি আইটেম আছে তাই আউটপুট হিসেবে 3 কেই রিটার্ন করা হয়েছে।

- Check if queue is empty -

print(queue.isEmty());
# false

যেহেতু, queue এ আইটেম আছে তাই আউটপুট হিসেবে false কেই রিটার্ন করা হয়েছে যদি আইটেম নাহ থাকতো তাহলে true রিটার্ন করতো। আমাদের queue ঠিক-ঠাক মতো কাজ করতেছে।

- শেষের কথা -

কোনো একটি বিষয় একবারে নাহ বুঝলে বার বার চেষ্টা করতে হয় । আপনারা যদি কোথাও বুঝতে নাহ পারেন তাহলে আরেকবার দেখতে পারেন । এতে অনেক কিছুই পরিস্কার হয়ে যাবে।

যদি এই আর্টিকেলে কোনো প্রকার ভূল পেয়ে থাকেন তাহলে আমাকে জানাতে ভূলবেন নাহ প্লিজ । আমরা শিখতে চাই সেটা ভূল থেকে হলেও ।

Read More

ফাইন্ড ফ্যাক্টরিয়াল - Using Stack

 

আমরা জানি, Stack ডাটা-স্ট্রাকচার LIFO(Last In First Out) প্যারাডাইম মেনে চলে অর্থাৎ এখানে কোনো ভ্যালু শেষে এড করা হলে তা প্রথমে ডিলিট হয়ে যাবে । আপনি যদি Stack ও Queue ডাটা-স্ট্রাকচার সম্পর্কে না জেনে থাকেন তাহলে নিচের দেওয়া লিঙ্কগুলো থেকে পরে নিতে পারেন -

• Stack ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Queue ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Stack ডাটা-স্ট্রাকচার ইন পাইথন
• Queue ডাটা-স্ট্রাকচার ইন পাইথন

এখন, আসল কাজে ফিরে আসা যাক - আপনাকে একটি ফাংশন লিখতে হবে যা প্যারামিটার হিসেবে একটি নাম্বার নিবে এবং সেই নাম্বারের Factorial বের করে তা রিটার্ন  করতে হবে ।

Factorial Number:-

কোন সংখ্যার factorial number বলতে সেই সংখ্যা থেকে ১ পর্যন্ত সবগুলো সংখ্যার গুণফল কে বোঝায় যেমন :- 

= 5 

= 5 *4 * 3 * 2 *1

 = 120

এখন এই প্রব্লেমটি আমরা অনেক ভাবেই সমাধান করতে পারি । কিন্তু আমরা অন্যভাবে প্রব্লেমটি সমাধান না করে Stack দিয়ে কিভাবে সমাধান করতে হয় তা দেখবো এবং বোঝার চেষ্টা করবো ।

ধরি, আমাদের কাছে একটি নাম্বার আছে 5 । আমরা চাইলে সরাসরি Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট করে তা দিয়ে সমাধান করতে পারি । কিন্তু, Stack ডাটা-স্ট্রাকচার সরাসরি ইমপ্লিমেন্ট না করেও জাভাস্ক্রিপ্টের অ্যারে অথবা পাইথনের লিস্ট দিয়ে খুব সহজেই Stack এর কাজ করে ফেলতে পারি তো চলুন শুরু করা যাক -

স্টেপ(০১) :- প্রথমে, 5 থেকে 1 পর্যন্ত প্রত্যেকতা সংখ্যাকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, 5 থেকে 1 এর মাঝে প্রথম সংখ্যা অর্থাৎ 5 কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু 5 কে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = [5]

স্টেপ(০২) :- এখন, 5 থেকে 1 এর মাঝে দ্বিতীয় সংখ্যা অর্থাৎ 4 কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = [5, 4]

স্টেপ(০৩) :- এবার , 5 থেকে 1 এর মাঝে তৃতীয় সংখ্যা অর্থাৎ 3 কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = [5, 4, 3]

স্টেপ(০৪) :- এবারে, 5 থেকে 1 এর মাঝে চতুর্থ সংখ্যা অর্থাৎ ২ কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = [5, 4, 3, 2]

স্টেপ(০৫) :- এবারে , 5 থেকে 1 এর মাঝে সবশেষ সংখ্যা অর্থাৎ 1 কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = [5, 4, 3, 2, 1]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য একটি নাম্বারের সাথে গুণ করে দিবো ।

একটা নাম্বার নিলাম fact নামে এবং তার ভেতর 1 এসাইন করলাম - 

fact = 1

এখন, contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে fact নাম্বারের এর সাথে গুণ করে দিলাম । এখন contains অ্যারে হবে ৪ উপাদান বিশিষ্ট এবং fact এর মান হবে 1*1 = 1 :-

fact = 1 

fact = 1* 1 

fact = 1

contains = [5, 4, 3, 2]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে fact এর সাথে গুণ করে দিলাম-

fact = 2 

fact = 1 * 2 

fact = 2

contains = [5, 4, 3]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে fact এর সাথে গুণ করে দিলাম-

fact = 3 

fact = 2 * 3 

fact = 6

contains = [5, 4]

একইভাবে contains অ্যারে থেকে শেষের ভ্যালু pop() করে fact এর সাথে গুণ করে দিলাম-

fact = 4 

fact = 6 * 4 

fact = 24

contains = [5]

এখন, contains অ্যারে তে একটি মাত্র সংখ্যা আছে সেইটাকেও pop() করে fact এর সাথে গুণ করে দিলাম -

fact = 5

fact = 2 *4 * 5 

fact = 120

contains = []

এখন এই (fact = 120) ই হলো আমাদের কাঙ্খিত ফলাফল । এতো দূর পর্যন্ত আপনি যদি বুঝে থাকেন তাহলে আপনাকে Congrats আর যদি বুঝে নাহ থাকেন তাহলে আরেকবার পড়ুন এবং অন্য আরেকটি নাম্বারের Factorial বের করার চেষ্টা করুন ।

তো চলুন এখন কোড লিখা যাক -

পাইথনে ইমপ্লিমেন্টেশন :-

def fact(n):
    contains = []
    while n > 0:
        contains.append(n)
        n -= 1

    fact = 1
    while len(contains) > 0:
        fact *= contains.pop()

    return fact

Output :

print(fact(5))  # 120
print(fact(7))  # 5040

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন -

const fact = (n) => {
  let contains = [];
  while (n > 0) {
    contains.push(n);
    console.log(n);
    n--;
  }
  let fact = 1;
  while (contains.length > 0) {
    fact *= contains.pop();
  }
  return fact;
};

Output :

fact(5);  // 120
fact(7); // 5040

কোড বিশ্লেষণ :-

উপরোক্ত কোডে, প্রথমে contains নামে একটি অ্যারে বা লিস্ট নিয়েছি । তারপর, একটি লুপ থ্রু করেছি যতক্ষণ 0 থেকে n বড় হতে থাকবে ততক্ষণ লুপটি চলবে এবং প্রত্যেকতা সংখ্যাকে contains নামের অ্যারে বা লিস্টে পুশ করে দিয়েছি । n এর মান প্রত্যেক ইটারেশনে 1 করে কমে দিয়েছি ।

fact নামে একটি নাম্বার নিয়েছি তাতে 1 এসাইন করেছি এবং contains অ্যারেতে একটি লুপ থ্রু করেছি । লুপটি ততক্ষণ চলবে যতক্ষণ পর্যন্ত contains এর সাইজ 0 থেকে বড় থাকবে । এবং প্রত্যেক ইটারেশনে fact এর সাথে contains এর শেষ উপাদানটি রিমুভ হয়ে গুণ হতে থাকবে । এক পর্যায়ে আমাদের লুপটি শেষ হয়েছে । এখন, fact ভেরিয়েবলে আমাদের কাঙ্খিত factorial ভ্যালু রয়েছে তাই সেইটা রিটার্ন করেছি ।

কোডের টাইম ও স্পেস উভয় কমপ্লেক্সিটি হবে ওর্ডার অব এন অর্থাৎ O(n) ।

Read More

স্ট্যাক(Stack) ডাটা-স্ট্রাকচার ইন পাইথন

 

 

কম্পিউটার সাইন্সে কমন এবং বহুল ব্যবহৃত ডাটা- স্ট্রাকচার গুলোর মাঝে Stack একটি । আমরা আজকে এই ডাটা- স্ট্রাকচার সমন্ধে শিখতে যাচ্ছি, Stack কি তা জানার আগে একটু বোঝার চেষ্টা করি যে লিনিয়ার(Linear) ডাটা- স্ট্রাকচার কি ?

লিনিয়ার(Linear) ডাটা-স্ট্রাকচার কি ?

যেসব ডাটা- স্ট্রাকচারে ডাটা গুলো একটি নির্দিষ্ট সিকুয়েন্সিয়াল(sequential) অর্ডারে(order) থাকে অর্থাৎ ডাটা সমূহ নির্দিষ্ট ভাবে সাজানো গোছানো অবস্থায় রাখা হয় । যেখানে ডাটা সমূহ একটি আরেকটির সাথে কানেক্টেড থাকে এবং খুব দ্রুত বিভিন্ন অপারেশনসমূহ সম্পন্ন করা হয় যেমন - ট্রাভারসিং(Traversing), সার্চিং(Searching), মারজিং(Merging) ইত্যাদি তাদেরকেই লিনিয়ার(Linear) ডাটা- স্ট্রাকচার বলা হয়।

 

Stack কি ?

Stack একটি লিনিয়ার(Linear) ডাটা- স্ট্রাকচার যা LIFO প্যাঁরাডাইম(paradigm) মেনে চলে । LIFO এর পূর্ণরূপ হইলো - Last In First Out অর্থাৎ Stack এ কোনো একটা ভ্যালু শেষে সংযোজন করা হইলে তা প্রথমেই বিয়োজন হবে। এখন একটু রিয়েল লাইফ উদাহরণ দেওয়া যাক -

 

রিয়েল লাইফ উদাহরণ -

অনেক স্বপ্ন ছিলো আপনার মামার মেয়েকে বিয়ে করবেন কিন্তু আজ সেই মেয়ের বিয়ে। আমি খুবই দুঃখিত যে বরটা আপনাকে বানাতে পারলাম নাহ । তবে আপনি সেই বিয়েতে একজন ওয়ার্কার যে কিনা মেহমানদের মাঝে থালা(Plate) সার্ভ করার দায়িত্ব পালন করবেন ।

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

এইখানে একটা জিনিস খেয়াল করেছেন ? এই যে আপনি বেসিন থেকে থালা একটি একটি করে হাতে নিচ্ছেন এবং তা আবার একটি একটি করে মেহমানদের মাঝে সার্ভ করতেছেন ।

ধরি যে, এইবার আপনি ৮টি থালা বেসিন থেকে হাতে নিয়েছেন । যখন ৮টি থালার ১ম টি হাতে নিয়েছেন তখন আপনার হাতে থালা একটি । তারপর যখন ২ নাম্বার থালা হাতে নিলেন তখন আপনার হাতে থালা দুইটি এবং প্রথম যে থালাটা হাতে নিয়েছেন সেইটা কিন্তু এখন ২য় থালার নিচে। এভাবে পর্যায়ক্রমে আপনি ৮ টি থালা হাতে নিয়েছেন ।

তাহলে সবশেষে যে থালাটা হাতে নিলেন অর্থাৎ ৮ নাম্বার থালা সেইটা কিন্তু এখন সবার ওপরে । এবং প্রথমে যে থালাটা নিয়েছিলেন সেইটা কিন্তু এখন সবার শেষে । তাই নাহ ?

 

এখন আপনি ৮টি থালা মেহমানদের দিতে গেলেন এবং উপরের থালাটা একজনকে দিলেন । আপনি কিন্তু উপরের থালাটা অর্থাৎ ৮ নাম্বার থালাটা একজনকে দিয়ে দিলেন। তার মানে কি ? আপনি সবশেষে যে থালাটা আপনার হাতে নিয়েছিলেন সেই থালাটাই আপনি সর্বপ্রথম একজনকে দিয়ে দিলেন। এইভাবে পর্যায়ক্রমে আপনি সব থালায় মেহমানদের দিয়ে দিলেন ।

তাহলে সারমর্ম এই যে, বেসিন থেকে সর্বশেষে যে থালাটা আপনি হাতে নিয়েছিলেন তা সর্বপ্রথম হাত থেকে সরিয়ে ফেললেন । এবং সর্বপ্রথম যে থালাটা হাতে নিয়েছিলেন তা সর্বশেষে হাত থেকে সরিয়ে ফেললেন।

এখানেও কিন্তু  LIFO প্যাঁরাডাইম(paradigm) মেনে চললো অর্থাৎ - Last In First Out, শেষে যে থালাটা হাতে ইন করলেন প্রথেমেই সেইটাকে আউট করে দিলেন । আশা করি এখন আপনি Stack সম্পর্কে Theoretical একটা ধারণা পেলেন।

যেহেতু আমরা মোটামোটি বুঝি যে, Stack ডাটা- স্ট্রাকচার কি তাহলে চলুন এখন আমরা খুব সহজেই এইটা কে ইমপ্লিমেন্ট(implement) অর্থাৎ তৈরি করে ফেলি ।
 

- Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট(implement) করার আগে -

যে কোনো ল্যাংগুয়েজেই হোক নাহ কেনো Stack ইমপ্লিমেন্ট(implement) করার সময় মাস্ট(must) আমাদেরকে দুইটা মেথড তৈরি করতেই হবে -

১। push - Stack এ আইটেম সংযোজন ।

২। pop - Stack থেকে আইটেম বিয়োজন ।

এইখানে মেথডস নেইম যে push এবং pop ই হবে সেরকম বাধা- ধরা কোনো নিয়ম নেই । আপনি চাইলে add, remove বা আপনার সুবিধা- মতো যেকোনো নেইম দিতে পারেন ।

তবে এই দুইটা মেথড ছাড়াও Stack এ আমাদের প্রয়োজন মতো অনেক মেথডস তৈরি করতে পারি ।

- Stack এ আমরা যে মেথডস গুলো তৈরি করতে যাচ্ছি -

1। push() - stack এ আইটেম সংযোজন হবে।

2। pop() - stack থেকে আইটেম বিয়োজন হবে।

3। size() - stack এ আইটেম কতগুলো আছে তা জানা যাবে।

4। isEmpty() - stack খালি কি নাহ তা জানা যাবে।

5। topElement() - stack থেকে প্রথম আইটেম নেওয়া যাবে ।

6। tailElement() - stack থেকে শেষ আইটেম নেওয়া যাবে ।

- Stack ইমপ্লিমেন্ট(implement) -

Stack ইমপ্লিমেন্ট(implement) করতে আমি লিস্ট(list) এবং ক্লাস(class) কে বেছে নিবো । তবে লিঙ্কড-লিস্ট(linked-list) দিয়েও চাইলে করতে পারেন । সামনের কোনোদিন সময় করে লিঙ্কড-লিস্ট(linked-list) দিয়ে কিভাবে Stack` ইমপ্লিমেন্ট(implement) করতে হয় তা নিয়ে একটি Article লিখার চেষ্টা করবো ।

- ক্লাস(class) ডিফাইন -

class Stack:
    # code here

- কন্সট্রাক্টর(constructor) তৈরি -

def __init__(self):
    self.data = []

এখানে একটি constructor ফাংশন নিয়েছি এবং data নামে একটা প্রোপার্টি নিয়েছি যা মুলত একটা লিস্টকে হোল্ড করে । এই লিস্টই মুলত Stack এর আইটেমগুলো কে কনট্রোল করবে ।

- push method -

def push(self, item):
    self.data.append(item)

লিস্টের append মেথডের সাহায্য নেওয়া হয়েছে যা এলিমেন্টকে খুব সহজেই Stack এর শেষে যুক্ত করে দিবে ।

- pop method -

def pop(self):
    if(len(self.data)):
        return self.data.pop()
    else:
        return "Pop failed!"

এখানে বলা হয়েছে যে যদি Stack এর লেন্থ শুন্য(0) থেকে বড় হয় তাহলে Stack থেকে শেষের এলিমেন্টকে ডিলিট করে দিবে। শুন্য(0) থেকে বড় মানে Stack এ এলিমেন্ট আছে।

আর যদি Stack এ এলিমেন্ট নাহ থাকে তাহলে Pop failed! রিটার্ন করবে ।

- size method -

def size(self):
    return len(self.data)

Stack এ কতোগুলো আইটেম আছে তা এই সাইজ(size) মেথড রিটার্ন করবে ।

- isEmty method -

def isEmpty(self):
    return len(self.data) == 0

Stack খালি কি নাহ তা জানা যাবে isEmty এর সাহায্যে । যদি stack এ আইটেম থাকে তাহলে false আইটেম নাহ থাকলে true রিটার্ন করবে।

- topElement method -

def topElement(self):
    if(len(self.data)):
        return self.data[0]
    else:
        return "stack is empty!"

Stack থেকে প্রথম এলিমেন্ট নেওয়া যাবে topElement মেথডের সাহায্যে ।

- tailElement method -

def tailElement(self):
    if(len(self.data)):
        return self.data[-1]
    else:
        return "stack is empty!"

Stack থেকে শেষ এলিমেন্ট নেওয়া যাবে tailElement মেথডের সাহায্যে ।

- Final Stack -

class Stack:
    # constructor
    def __init__(self):
        self.data = []

    # push method
    def push(self, item):
        self.data.append(item)

    # pop method
    def pop(self):
        if(len(self.data)):
            return self.data.pop()
        else:
            return "Pop failed!"

    # isEmpty method
    def isEmpty(self):
        return len(self.data) == 0

    # size method
    def size(self):
        return len(self.data)

    # topElement method
    def topElement(self):
        if(len(self.data)):
            return self.data[0]
        else:
            return "stack is empty!"

    # tailElement
    def tailElement(self):
        if(len(self.data)):
            return self.data[-1]

        else:
            return "stack is empty!"

আপনি চাইলে stack এ প্রয়োজন মতো আরও অনেক মেথড যুক্ত করতে পারেন । এখন আমাদের তৈরি করা stack টেস্ট করে দেখবো যে সব কিছু ঠিকমতো কাজ করছে কি নাহ ।

- Create a Stack -

stack = Stack()

- Add Item To Stack -

stack.push('torikus')
stack.push('fahim')
stack.push('afifa')

# ['torikus', 'fahim', 'afifa']

stack এ সবশেষে afifa কে সংযোজন করা হয়েছে এখন যদি বিয়োজন করি তাহলে -

- Remove Last Item To Stack -

print(stack.pop())  # 'afifa'
# [ 'torikus', 'fahim' ]

যেহেতু stack এ সবশেষে afifa কে সংযোজন করা হয়েছে তাই pop() করার পর afifa কেই প্রথম বিয়োজন করে ফেলছে ।

- Length In Stack -

print(stack.size())  # 2

যেহেতু, stack এ দুইটি আইটেম আছে তাই আউটপুট হিসেবে 2 কেই রিটার্ন করা হয়েছে।

- Check If Stack Is Empty -

print(stack.isEmty())
# false

যেহেতু, stack এ আইটেম আছে তাই আউটপুট হিসেবে false কেই রিটার্ন করা হয়েছে যদি আইটেম নাহ থাকতো তাহলে true রিটার্ন করতো।

আমাদের stack ঠিক-ঠাক মতো কাজ করতেছে। আশা করি আপনি বুঝতে পেরেছেন ।

- শেষের কথা -

কোনো একটি বিষয় একবারে নাহ বুঝলে বার বার চেষ্টা করতে হয় । আপনারা যদি কোথাও বুঝতে নাহ পারেন তাহলে আরেকবার দেখতে পারেন । এতে অনেক কিছুই পরিস্কার হয়ে যাবে।

যদি এই আর্টিকেলে কোনো প্রকার ভূল পেয়ে থাকেন তাহলে আমাকে জানাতে ভূলবেন নাহ প্লিজ । আমরা শিখতে চাই সেটা ভূল থেকে হলেও ।

Read More

গোল্ডেন আয়তক্ষেত্র - (লিনিয়ার সার্চ অনুশীলন )

 

আজকে আমরা  আরও একটি লিনিয়ার সার্চ রিলেটেড সমস্যা সমাধান করবো । এই সমস্যাটি Hackerearth অনলাইন জাজ থেকে নেওয়া হয়েছে ।

সমস্যার নাম -  গোল্ডেন আয়তক্ষেত্র

উপরোক্ত সমস্যাটিতে বলা হয়েছে যে, আমাদের কাছে একটি আয়তক্ষেত্র N আছে । এই N আয়তক্ষেত্রটি  গোল্ডেন আয়তক্ষেত্র  হবে  যদি এর পাশের (Height and Width) অনুপাত [1.6, 1.7] এর মাঝে হয় ।এখন আমাদের কাজ হল গোল্ডেন আয়তক্ষেত্রের সংখ্যা খুঁজে বের করা। 

 যদি আপনি সমস্যা টি বুঝে থাকেন তাহলে সমাধান করে এইখানে গিয়ে সাবমিট করুন । আপনার যদি জানা বা মনে নাহ থাকে যে কিভাবে জাভাস্ক্রিপ্ট দিয়ে বিভিন্ন অনলাইন জাজে সমস্যা সমাধান করা হয় তাহলে এই আর্টিকেল টি দেখতে পারেন ।

-------------------------

এই সমস্যাই, ইনপুট হিসেবে -

• প্রথম লাইনে  আমাদেরকে একটি ইন্টিজার নাম্বার  N  নিতে হবে যা 
  আয়তক্ষেত্রের সংখ্যা নির্দেশ করে। 
• N এর উপর নির্ভর করে পরবর্তী লাইনগুলোতে দুটি নাম্বার (Width and Height) নিতে হবে যা
  আয়তক্ষেত্রের প্রস্থ  এবং উচ্চতা নির্দেশ করে ।

আউটপুটে আমাদেরকে প্রিন্ট করতে হবে  ইনপুটকৃত নাম্বারের মধ্যে কতগুলো গোল্ডেন আয়তক্ষেত্র আছে  তার  সংখ্যা ।

আর বেশি কথা না বলে সমস্যাটি সমাধান করা যাক -

-------------------

// ইনপুট হিসেবে আয়তক্ষেত্রের সংখ্যা n নিলাম  
    let n = parseInt(readline());

    // গোল্ডেন আয়তক্ষেত্রের সংখ্যা হিসেব করার জন্য প্রথমে count = 0 রাখলাম
    let count = 0;

    // ratio নামে একটি ভেরিয়েবল নিলাম যা অনুপাতের মান ধরে রাখবে
    let ratio; 

    // একটি লুপ যা n সংখ্যক বার চলবে
    for(let i = 0; i<n; i++){
    
        // প্রত্যেক লাইনে ইনপুট (width and height)নিলাম 
        let wh = readline().split(" ").map((x) => parseFloat(x));
        
        // width এবং  height কে আলাদা আলাদা করে ভেরিয়েবলে রাখলাম
        let width = wh[0], height = wh[1];
    
  
        // যদি height থেকে width সমান বা বড় হয়
        if(width >= height){
        
        // তাহলে,  অনুপাত = প্রস্থ / উচ্চতা
            ratio = width / height; 
            
        }else{
         // তাহলে, অনুপাত = উচ্চতা / প্রস্থ
            ratio = height / width;
            
        }

        // এখন চেক করি অনুপাত কি [1.6, 1.7] এর মাঝে ? যদি সত্য হয় -
        if(ratio >= 1.6 && ratio <= 1.7){
            
            // count এর মান 1 করে বাড়ায়
            count = count + 1;
        }
    
    }
    
    // গোল্ডেন আয়তক্ষেত্র কয়টি আছে তা count ধরে রাখছে । 
    // count প্রিন্ট করি
    print(count);

আমাদের সমস্যা সমাধান হয়েছে । আশা করি কোড বুঝতে সমস্যা হবে নাহ । এখন আমি উপরোক্ত কোড এখানে গিয়ে সাবমিট করব তবে সাবমিট করার আগে আমাদের কিছু ব্রয়লার কোডের সাহায্য নিতে হয় আশা করি আপনারা তা জানেন ।

তবুও এখানে কোডটুকু দেওয়া হইলো -

"use strict";
process.stdin.resume();
process.stdin.setEncoding("utf-8");
function print(x) {
console.log(x);
}
let inputString = "";
let currentLine = 0;
process.stdin.on("data", (inputStdin) => {
inputString += inputStdin;
});
process.stdin.on("end", () => {
inputString = inputString.split("\n");
main();
});
function readline() {
return inputString[currentLine++];
}

// code start
function main() {

// write code here

}

এখন আমাদের সমাধান উপরোক্ত ব্রয়লার কোডের main() ফাংশনের ভেতর পেস্ট করি এবং  JavaScript(Node.js) সিলেক্ট করি  -

এখন সাবমিট করি -

আমাদের কোড Accepted । আশা করি বুঝতে পারছেন -

# linear search in javascript

# linear search problems

Read More

নাম্বারের খোজে - (লিনিয়ার সার্চ অনুশীলন )

 

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

 প্রব্লেমের  নাম - নাম্বারের খোজে  

আপনি যদি প্রব্লেমটি বুঝে থাকেন তাহলে কোড লিখা  শুরু করে দিন আর যদি বুঝে থাকেন কিন্তু সমাধান করতে নাহ পারেন তাহলে আমি আপনাকে সমাধানটি করে দিচ্ছি -

প্রব্লেমটিতে বলা হয়েছে যে,  ইনপুট হিসেবে একটি নাম্বারের অ্যারে nums এবং অ্যারে থেকে যে নাম্বার খোজ করবো অর্থাৎ  x  নিতে হবে । তারপর অ্যারের প্রথম অর্ধেকের প্রত্যেকটা উপাদানের সাথে 5 যোগ করে পুরো অ্যারেতে x কে খুজতে হবে । যদি x কে অ্যারেতে পাওয়া যায়  তাহলে আউটপুট হিসেবে  একটি স্ট্রিং YES অথবা NO প্রিন্ট করতে হবে ।

 

আমরা এই প্রব্লেমটি প্লেইন জাভাস্ক্রিপ্ট দিয়ে সমাধান করবো । সমস্যাটি আপনি অনেক ভাবেই সমাধান করতে পারেন , তবে আমরা গত লেকচারের অনুসারে অর্থাৎ লিনিয়ার সার্চ ব্যাবহার করবো -

 ১। প্রথমে একটি ফাংশন নিই -  

const findTheNumber = (nums, x) => {
    // code here
}

আমি findTheNumber() নামে একটি ফাংশন এবং দুইটি প্যাঁরামিটার nums এবং x নিয়েছি । এখন উপরোক্ত প্রব্লেমটি সমাধান করা যাক -

const findTheNumber = (nums, x) => {

    // অ্যারের মাঝের ইনডেক্স নাম্বার
    let halfNumber = Math.floor(nums.length/2);

    // nums অ্যারের দ্বিতীয় অর্ধেক array তে রাখলাম
    let array = [...nums.slice(halfNumber, nums.length - 1)];

    // nums অ্যারের প্রথম অর্ধেকে লুপ চালাইলাম
    for(let i = 0; i <= halfNumber; i++){

        // nums অ্যারের প্রথম অর্ধেকের প্রত্যেকে উপাদানের সাথে 
        // ৫ যোগ করে array তে  রাখলাম
        array.push(nums[i] + 5);
    };


    // এখন আমরা (array) এই অ্যারেতে লিনিয়ার সার্চ ব্যাবহার করে x খুজবো
    let isFound = false;
    for(let j = 0; j<array.length; j++){
        if(array[j] === x){
            isFound = true;
        }
    }

    // যদি isFound = true হয় তাহলে YES নয়তো NO রিটার্ন করি
    return (isFound ? "YES" : "NO");
}

প্রত্যেকটি লাইনে কমেন্ট আউট করে বোঝানো হয়েছে কিভাবে কি করতেছে । তারপরেও যদি আপনি নাহ বুঝেন তাহলে একটু একটু করে কোড লিখুন এবং রান করুন ।

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

সমাধান একটু বড় হলেও কিন্তু সহজ এখন টেস্ট কেস গুলো অ্যাপ্লায় করে দেখি প্রোগ্রাম ঠিকঠাক কাজ করে কি নাহ ?

১। প্রথম টেস্ট কেস পরীক্ষা -

let result = findTheNumber([1,2,3,4,5],7);
console.log(result);
// YES

১। দ্বিতীয় টেস্ট কেস পরীক্ষা -

let result = findTheNumber([10,20,30,40],70);
console.log(result);
// NO

সবকিছু ঠিকঠাক ।

সবার সুবিধার্থে উপরের সমাধানটি কোনো প্রকার কমেন্ট ছাড়া দেওয়া হইলো -

const findTheNumber = (nums, x) => {
    let halfNumber = Math.floor(nums.length/2);
    let array = [...nums.slice(halfNumber, nums.length - 1)];
    for(let i = 0; i <= halfNumber; i++){
        array.push(nums[i] + 5);
    };

    // linear search apply
    let isFound = false;
    for(let j = 0; j<array.length; j++){
        if(array[j] === x){
            isFound = true;
        }
    }

    return (isFound ? "YES" : "NO");
}

ধন্যবাদ সবাইকে আজকে এই পর্যন্তই।

# linear search problem

# linear search algorithm


Read More

লিনিয়ার সার্চ (Linear Search)

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

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

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

let players = ["warner","rohit","mustafizur","sakib","bravo","taylor"];

এখন এই অ্যারে থেকে আমি "sakib" কে খুজে বের করতে চাচ্ছি । তাহলে আমাকে অ্যারের প্রথম উপাদান থেকে খোজা শুরু করতে হবে যা লিনিয়ার সার্চের বৈশিষ্ট । দেখতে পাচ্ছি উপরোক্ত অ্যারের প্রথম ইনডেক্সে অর্থাৎ 0 নাম্বার ইনডেক্সে "warner" আছে যা "sakib" নাহ । তাই প্রথম ইনডেক্স হবে নাহ কারণ কন্ডিশন মিথ্যা -


 
অ্যারের পরের উপাদান হচ্ছে "rohit" যা "sakib" নাহ তাহলে এই কন্ডিশনও মিথ্যা -

সেইমভাবে 2 নাম্বার ইনডেক্সের কন্ডিশনও মিথ্যা । এইভাবে একাধারে অর্থাৎ একটার পর একটা খোজ করতেই থাকবে যতক্ষণ নাহ পর্যন্ত কাঙ্ক্ষিত রেজাল্ট পাওয়া যায় । অবশেষে 3 নাম্বার ইনডেক্সের উপাদানই হচ্ছে আমাদের কাঙ্ক্ষিত উপাদান -

 

এখন আমরা লিনিয়ার সার্চ অ্যালগরিদম লিখব এবং তা ইমপ্লিমেন্ট করবো ।

- লিনিয়ার সার্চ অ্যালগরিদম -

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

const linearSearch = (arr,searchItem) => {
    for(let i = 0; i<arr.length; i++){
        if(arr[i] === searchItem){
            return i;
        }
    }
    return -1;
}

এটাই লিনিয়ার সার্চ অনেক সোজা তাই নাহ ? এখন আমি একটু চেক করি যে আউটপুট ঠিকঠাক দেয় কি নাহ -

let players = ["warner","rohit","mustafizur","sakib","bravo","taylor"];
const res = linearSearch(players, 'sakib');
console.log(res);
// Output : 3

এখন এমন একটি ভ্যালু পাস করি যা উপরোক্ত অ্যারেতে নেই -

let players = ["warner","rohit","mustafizur","sakib","bravo","taylor"];
const res = linearSearch(players, 'shakil');
console.log(res);
// output: -1

যেহেতু, 'shakil' নামে কোনো উপাদান অ্যারেতে নেই তাই আউটপুটে আমরা -1 পেয়েছি যা আমাদের পাওয়ার কথা ছিলো । আশা করি আপনারা লিনিয়ার সার্চ অ্যালগরিদমটি বুঝতে পারছেন ।

 

- লিনিয়ার সার্চের কমপ্লিক্সিটি(Complexity) -

যদি আপনি আমার আগের আর্টিকেলগুলো দেখে থাকেন টাইম এবং স্পেস কমপ্লিক্সিটি(Complexity) নিয়ে তাহলে হয়তো খুব সহজেই বলতে পারবেন লিনিয়ার সার্চের টাইম এবং স্পেস কমপ্লিক্সিটি(Complexity) কত ?

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

লিনিয়ার সার্চ অ্যালগরিদমের টাইম কমপ্লিক্সিটি(Complexity) হচ্ছে অর্ডার অব এন O(n) । যদি কমপ্লিক্সিটি(Complexity) বিষয়টি নাহ বুঝে থাকেন তাহলে নিম্নোক্ত আর্টিকেলগুলো পড়তে পারেন সব ক্লিয়ার হবে যাবে -

১। অ্যালগরিদমে টাইম কমপ্লিক্সিটি(Complexity) - পর্ব(০১) 

২। অ্যালগরিদমে টাইম কমপ্লিক্সিটি(Complexity) - পর্ব(০২)

৩। অ্যালগরিদমে স্পেস কমপ্লিক্সিটি(Complexity) 

# linear search in algorithm

# linear search in javascript

---

Read More

 

স্পেস কমপ্লিক্সিটি(complexity)

---

কোনো একটা অ্যালগরিদম/প্রোগ্রামে টাইম কমপ্লিক্সিটির(complexity) মতো স্পেস কমপ্লিক্সিটি(complexity)ও গুরুত্বপূর্ণ বিষয় । স্পেস কমপ্লিক্সিটি(complexity) এবং টাইম কমপ্লিক্সিটি(complexity) প্রায়ই একই কারণ তারা একটি অ্যালগরিদমের ইনপুট পরিমাণের সাথে সম্পর্কিত। যেখানে টাইম কমপ্লিক্সিটি(complexity) একটি অ্যালগরিদমে অপারেশনের পরিমাণের সাথে সম্পর্কিত, এবং স্পেস কমপ্লিক্সিটি(complexity) অ্যালগরিদম সম্পন্ন করার জন্য প্রয়োজনীয় মোট জায়গার সাথে সম্পর্কিত।

স্পেস কমপ্লিক্সিটি(complexity) কি ?

সহজভাবে বললে, একটি অ্যালগরিদম বা প্রোগ্রাম সম্পন্ন করার জন্য ঠিক কতটুকু জায়গা বা মেমরি নিলো তাকেই স্পেস কমপ্লিক্সিটি(complexity) বলে। কোনো অ্যালগরিদম বা প্রোগ্রামের জন্য আমাদের নির্দিষ্ট পরিমাণ মেমরি ব্যাবহার করতে হয়। কিন্তু আমরা যদি স্পেস কমপ্লিক্সিটির(complexity) হিসেব-নিকেশ বুঝি তাহলে সহজেই বলে দিতে পারবো যে একটি প্রোগ্রাম কার্যকর করার জন্য ঠিক কতটুকু মেমরি ব্যাবহার করতে হবে।

একটি অ্যালগরিদম/প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) বের করতে প্রোগ্রামে ব্যবহৃত ভেরিয়েবল দ্বারা দখলকৃত স্থান গণনা করা যথেষ্ট।

স্পেস কমপ্লিক্সিটি(complexity) কেন দরকার ?

একটি অ্যালগরিদমে যদি টাইম কমপ্লিক্সিটি(complexity) অনেক বেশিও হয়ে যায় তবুও কিন্তু প্রোগ্রাম দেরিতে হলেও রান হবে বা চলবে । কিন্তু যদি সেই অ্যালগরিদম/প্রোগ্রামের বরাদ্দকৃত মেমরি অতিক্রম করে অর্থাৎ বরাদ্দকৃত মেমরি থেকে বেশি মেমরি ব্যাবহার করা হয়, তাহলে এটি চলবে না। তাই কোনো অ্যালগরিদম রচনা করার সময় আমাদের খেয়াল রাখা দরকার যে ব্যবহৃত মেমরি যাতে বরাদ্দকৃত মেমরির মধ্যে সীমাবদ্ধ থাকে ।

 

এখন কয়েকটি প্রোগ্রাম দেখি এবং স্পেস কমপ্লিক্সিটি(complexity) বের করার চেষ্টা করি ।

উদাহরণ - ০১ :

function Add(n1, n2) {
  const sum = n1 + n2;
  return sum;
}
const result = Add(10,20);
console.log(result);

জাভাস্ক্রিপ্ট প্রোগ্রামিং ভাষাতে, একটি নাম্বার মেমরিতে জায়গা নেয় 64 বিটস(bits) যাকে বাইটে কনভার্ট করলে হয় 8(আট) বাইটস(bytes) । এখন উপরোক্ত Add ফাংশনে লক্ষ্য করলে দেখবেন যে, প্রথমে এটি ২টা নাম্বার প্যাঁরামিটার হিসেবে নিচ্ছে এবং তাদের যোগফলকে sum নামের একটি ভ্যারিয়েবলে স্টোর করতেছে যা একটি নাম্বার ।

এই ফাংশনে মেমরি স্পেস হবে n1,n2,এবং sum তিনটি নাম্বার ভেরিয়েবলের ওপর নির্ভর করে । হিসাব করলে হয় 3*8 = 24 বাইটস(bytes) এখানে n1,n2 এর মান যতই হোক নাহ কেনো প্রত্যেকটার জন্য 8(আট) বাইটস(bytes) করেই মেমরি নিবে এবং তা sum ভেরিয়েবলে স্টোর হবে । তাহলে উপরোক্ত প্রোগ্রামে যেকোনো পরিস্থিতিতে n1,n2,এবং sum তিনটি নাম্বার ভেরিয়েবলের মেমরি খরচ করে ফেলবে যা একটি কন্সটেন্ট(Constant) নাম্বার । এখন বলতে পারি উপরোক্ত প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) অর্ডার অব ওয়ান O(1) ।

অনেকের মনে প্রশ্ন আসতে পারে যে ভাই, আমরা উপরে যে sum কে রিটার্ন এবং ফাংশনকে কল করলাম এগুলোর জন্য কি মেমরি নেয় নাহ ? উত্তর হবে হ্যাঁ নেয় কিন্তু সেগুলো অস্থায়ী(temporary) যা কাউন্ট করা হয় নাহ এসব মেমরিকে বলা হয় অক্সিলারি মেমরি(Auxiliary Space) ।

অক্সিলারি মেমরি(Auxiliary Space) কি ?

অক্সিলারি মেমরি(Auxiliary Space) হলো অতিরিক্ত বা অস্থায়ী(temporary) মেমরি যা প্রোগ্রাম এক্সিকিউশনের(Execution) সময় ব্যাবহার হয় এবং এটিকে ইনপুট মেমরিতে কাউন্ট করা হয় নাহ । উপরোক্ত ফাংশনে n1,n2,এবং sum তিনটি নাম্বার ভেরিয়েবলের মেমরিই হলো ইনপুট মেমরি ।

উদাহরণ - ০২ :

function sum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

এই ফাংশনে মেমরি স্পেস হবে sum এবং i দুইটি নাম্বার ভেরিয়েবলের ওপর নির্ভর করে যাকে আমরা ইনপুট মেমরিও বলতে পারি । তাছাড়াও উপরোক্ত প্রোগ্রামে রিটার্ন স্টেটমেন্ট, ফাংশন কল, এবং ফর লুপ আছে যারা অক্সিলারি মেমরি(Auxiliary Space) এর অন্তর্ভুক্ত । এখন তাহলে এই প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) নির্ণয় করা যাক -

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

যদি প্রথমে ৫ সাইজের একটি অ্যারেকে প্যাঁরামিটার হিসেবে পাস করি, তাহলে ফর লুপটি ৫ বার চলবে এবং sum এর সাথে অ্যারে এলিমেন্টের যোগ হবে অর্থাৎ প্রত্যেক এক্সিকিউশনে i এর মান ১ করে বাড়াবে এবং sum কে আপডেট করে ফেলবে । এখানে কিন্তু অ্যারের সবগুলো মান হবে নাম্বার ডাটা-টাইপ যা প্রত্যেকে মেমরিতে ৮ বাইটস করে নেয় -

 মেমরিতে জায়গা নিচ্ছে ৫৬ বাইটস । এখন প্যাঁরামিটারে ৫ এরে পরিবর্তে ১০ সাইজের একটি অ্যারেকে পাঠায় -

 

এখন মেমরিতে জায়গা নিচ্ছে ৯৬ বাইটস । এখানে কিন্তু এই প্রোগ্রামের মেমরি অ্যারের সাইজের উপর নির্ভর করেতেছে যা লিনিয়ার । তাহলে এখন খুব সহজেই বলতে পারি যে, এই প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) অর্ডার অব এন O(n) ।

আজকের পর্ব শেষ করার পূর্বে, চলুন জেনে নেওয়া যাক জাভাস্ক্রিপ্টে কিছু ডাটা-টাইপের স্পেস কমপ্লিক্সিটি(complexity) -

 # space complexity in javascript

# data structure and algorithm in javascript

# javascript space and time complexity

Read More