DEV Community: Samiun Black

Journey of creating a programming language: Bat Lang

Samiun Black — Sun, 21 Jan 2024 08:41:57 +0000

Quick Access

If you're eager to dive into the Bat Lang playground without delay, just click here: Bat Lang Playground

The Birth of Bat Lang

In the vast and creative universe of programming languages, where each line of code tells a unique story, I embarked on a journey to create something different—something that not only brings functionality but also a smile. Being a longtime fan of Batman, I couldn't resist the idea of gifting the Dark Knight his very own programming language. And thus, Bat Lang was born.

Design and Inspiration: Crafting the Bat Code

Bat Lang, being a toy language designed for fun, took shape as an interpreted language. The design philosophy draws inspiration from iconic elements of the Batman universe—Batarangs, the Bat Signal, and the utility belt. It's not just about writing code; it's about weaving a narrative with each line.

Implementation Adventures

Choosing Python as the canvas, I initially experimented with third-party lexer and parser tools. However, the journey became more frustrating than anticipated. So, I pivoted and decided to build everything from scratch. The lexer was a breeze, but crafting the Abstract Syntax Tree (AST) and the parser brought its set of challenges. The interpreter and environment creation, while relatively straightforward, presented some intricacies. Dealing with bugs in the parser became an ongoing quest. The main challenge? Understanding and implementing the execution order of code blocks. Adding features like functions and arrays added complexity, but perseverance won the day.

Features that Make Bat Lang Soar

Bat Lang allows you to perform the usual programming tasks—printing, variable declarations, conditions, loops, arrays, and functions. However, what truly sets it apart is not just what you can do, but how you do it. Every syntax element is Batman-themed. For instance, to print something, you use a function called BatSignal(), and to declare a variable, you employ the keyword batarang.

Future Plans: Unveiling the Road Ahead

In the spirit of continuous improvement, the first order of business is cleaning up the codebase. Looking forward, plans include incorporating more features into Bat Lang, such as Object-Oriented Programming (OOP) and expanding the repertoire of built-in data structures and functions.

Explore and Share Your Thoughts!

Ready to experience Bat Lang? Dive into the live playground: Bat Lang Playground

If you have any question or feedback about Bat Lang I would be more than happy to hear them out. Let's make coding an extraordinary journey together!

Why so many beginner programmers fail to learn to code and get a job FAST

Samiun Black — Sun, 14 May 2023 06:52:16 +0000

If you're looking to learn how to code and get a job, a quick search on YouTube will show you thousands of results promising to teach you how to code in 6 months or 100 days. But the truth is, becoming a proficient programmer takes time and effort. When I was in middle school, I started learning to code with Python. I spent more than 4 hours every day reading books, taking courses, and watching YouTube videos in order to grasp the concepts. It took me a year to have that "aha" moment and finally understand programming, and another year to land a job. So, what exactly is the problem that we face when learning to code FAST? Well, let’s look at our own lives and we will find the answer.

Think about when we first started school. We spent a year or more learning only the alphabet and forming basic words. As we grow up, we are tasked with reading massive articles and books, and writing essays. It takes 12 years (and another 4 in college, for some) to become eligible for a well-paying job. Why? Because we need to spend enough time learning the fundamentals, which we’d be building on for the rest of your life. That’s why we spend A YEAR to learn only the 26 alphabets and form very basic words with them.

Now, suppose you have never coded before, you never heard of programming before and you have absolutely no clue what it is. Also you sucked at math your entire life. So, how do you expect your brain to learn to code in 6 months and get a job? Your brain needs time to understand the fundamentals and really absorb them and be able to create something based on them.

Now you may say- “But there are people who HAVE learned to code from 0 knowledge in 6 months and landed a job” Well, yes there are. But most of them had the knowledge they needed to learn to code though they didn’t know coding.

Let’s take the example of Clément Mihailescu. The founder of algoexpert.io who learned to code in six months and landed a job in Google. Here’s the cliché - he did his undergrad in mathematics and programming is really close to mathematics. That means he already had the knowledge that he needed to get started with coding. Most of the people who learn to code in very less time and land a job are people who already had some knowledge related to coding.

But people like me and you, who are learning to code in a very young age or who simply don’t know a thing about coding or anything related to it, won’t be able to learn to code in 6 months and land a job in most cases. So what should we do instead of being depressed about it? We should accept it and give enough time to our brain to learn the fundamentals of coding. We need to play around with the fundamentals and experiment with them and really think about them.

Spend a week learning only about variables and input/output. Spend another week learning only about array. Think about them when you’re not in front of your computer, find real life examples of them, experiment with them. Enjoy the process of learning, and don't be afraid to repeat the same topics until they really stick. Only then you will be able to build a really strong fundamental based on which you’re going to be able to build a successful coding career. And here’s a good news- Once you've built a strong foundation, you'll be able to learn even harder languages in just a week or so. It took me a year to learn Python but I was able to learn and build a game in C++ in just a week. So don't give up, and remember to enjoy the process and soon you'll have that "aha" moment too.

Happy coding! 😄

Recursion: A beginner-friendly approach

Samiun Black — Sat, 06 May 2023 14:25:57 +0000

Recursion is the first topic that makes beginner programmers nervous. I had been there too. And that is expected because recursion is not a natural thing to happen in real life. It is a very abstract and mathematical concept, and that makes it a bit tricky to grasp at first. But don’t worry we wouldn’t use any advanced math here. So let’s jump into it.

Recursion meme from 9GAG

In its simplest form, a recursive function is one that directly or indirectly calls itself. Let me try to explain with an example.

Let’s take an example from grokking algorithms:

Suppose you’re digging through your grandma’s attic and come across a

mysteriously locked suitcase. Grandma tells you that the key for the suitcase is probably in this other box.

This box contains more boxes, with more boxes inside those boxes. The

the key is in a box somewhere. What’s your algorithm to search for the key?

Here are iterative and recursive approaches to find the key:

Which approach seems easier and simpler to you? The recursive approach is much cleaner.

Let’s take another example:

Suppose you’re going to someone’s house. You can describe the steps as-

If you are at the house, stop moving.
Take one step towards the house.
“Go to someone’s house”

See the pattern in both examples? You do the same thing with a smaller amount. This is the main concept of recursion. You keep doing the same work but every time on a smaller amount until you can’t go any smaller or have found the answer.

Parts of Recursive Algorithm

Base Case
Work toward the base case
Recursive Call

Something you have to be careful about when writing a recursive function is infinite loop. This is when the function keeps calling itself and the function never stops calling itself!

The “work toward base case” is where we make the problem smaller (e.g., divide the list into two parts, each smaller than the original). The recursive call is where we use the same algorithm to solve a smaller and simpler version of the problem. The base case is the solution to the “smallest” possible problem (For example, the base case in the problem “sort the array” would be if the array has only one element… and by definition, if the list has only one element then it’s already sorted).

Let’s see an example in Code:

Problem Statement:

Return the sum of all the numbers in an array.

Solutions:

The Sum of an array is equivalent to the => first number + sum of all other numbers

Let’s breakdown the problem-

Base Case:

if len(nums) == 1:
    return nums[0]

Work towards Base Case:

return first_num + sum_of_nums(rest)

Recursive Call:

sum_of_nums(rest)

By now you’ve got a grasp of basic recursion. Now we need to understand the BRI or Big Recursion Idea. It’s an idea that’s so straightforward it will

seem like a trick, but it works.

Let’s see an example from Think Like a Programmer:

Problem Statement

The manager of DelegateCorp needs to determine which of eight customers produces the most revenue for his company. Two factors complicate this otherwise simple task. First, determining the total revenue for a customer requires going through that customer’s whole file and tallying numbers on dozens of orders and receipts. Second, the employees of DelegateCorp, as the name suggests, love to delegate, and each employee passes work along to someone at a lower level whenever possible. To keep the situation from

getting out of hand, the manager enforces a rule: When you delegate, you must do some portion of the work yourself, and you have to give the delegated employee less work than you were given.

Following the company rule on delegating work, here’s what will happen

to the six customer files. The manager will take one file and determine how

much revenue that customer has generated for the company. The manager

will delegate the other five files to the vice manager. The vice manager will

process one file and pass the other four to the associate manager. This pro-

cess continues until we reach the sixth employee, the intern, who is handed

one file and must simply process it, with no further delegation possible.

Here’s an example of how this would proceed in practice.

MANAGER tallies the revenue for customer #0001, which is $172,000.
MANAGER to VICE MANAGER: “The highest revenue we have seen sofar is $172,000, customer #0001. Take these five files and determine theoverall highest revenue.”
VICE MANAGER tallies the revenue for customer #0002, which is $68,000. The highest revenue seen so far is still $172,000, customer #0001.
VICE MANAGER to ASSOCIATE MANAGER: “The highest revenue wehave seen so far is $172,000, customer #0001. Take these four files anddetermine the overall highest revenue.”
ASSOCIATE MANAGER tallies the revenue for customer #0003, which is$193,000. The highest revenue seen so far is now $193,000, customer #0003.
ASSOCIATE MANAGER to ASSISTANT MANAGER: “The highest revenuewe have seen so far is $193,000, customer #0003. Take these three filesand determine the overall highest revenue.”
ASSISTANT MANAGER tallies the revenue for customer #0004, which is$13,000. The highest revenue seen so far is still $193,000, customer #0003.
ASSISTANT MANAGER to JUNIOR MANAGER: “The highest revenuewe have seen so far is $193,000, customer #0003. Take these two files anddetermine the overall highest revenue.”
JUNIOR MANAGER tallies the revenue for customer #0005, which is$256,000. The highest revenue seen so far is now $256,000, customer #0005.
JUNIOR MANAGER to INTERN: “The highest revenue we have seen sofar is $256,000, customer #0005. Take this remaining file and determinethe overall highest revenue.”
INTERN tallies the revenue for customer #0006, which is $99,000. Thehighest revenue seen so far is still $256,000, customer #0005.
JUNIOR MANAGER to ASSISTANT MANAGER: “The highest revenueof all customers is $256,000, customer #0005.”
ASSISTANT MANAGER to ASSOCIATE MANAGER: “The highest revenueof all customers is $256,000, customer #0005.”
ASSISTANT MANAGER to ASSOCIATE MANAGER: “The highest revenueof all customers is $256,000, customer #0005.”
ASSOCIATE MANAGER to VICE MANAGER: “The highest revenue ofall customers is $256,000, customer #0005.”
VICE MANAGER to MANAGER: “The highest revenue of all customersis $256,000, customer #0005.”

In this sample problem, the BRI is in action. How so? Each person in the chain performs the same steps on a smaller and smaller subset of the original data. It’s important to note, however, that the problems involve no recursion at all.

each employee in the management chain hands-off as much work as possible to a subordinate. The assistant manager, for example, may know the junior manager well and expect the junior manager to hand all of the files but one to the intern. However, the assistant manager has no reason to care whether the junior manager processes all of the remaining files or passes some of them off to a subordinate. The assistant manager cares only that the junior manager returns the right answer. Because the assistant manager is not going to repeat the work of the junior manager, the assistant manager simply assumes that the result returned by the junior manager is correct and uses that data to solve the overall task that the assistant manager received from the associate manager. In the problems, when employees make requests of other employees, they are concerned with what but not how.

So the Big Recursion Idea is- You just need to think about the task in hand the other tasks would be handled by themselves. That brings us back to our recursive code structure again. We just need to find the base case and a way to work towards the base case others will take care of themselves.

This is all recursion is. I hope you found this article helpful. Here are some other helpful resources to learn recursion-

What on Earth is Recursion

Blueprint of Recursion

How Recursion Works

2D Array in C++

Samiun Black — Thu, 04 May 2023 03:20:56 +0000

Introduction

A 2D array is nothing but a giant array of 1D arrays. In a normal 1D array we can see that the array contains data like int, char, double, string, etc. In the same way, a 2D array contains 1D arrays instead of data. So we can call it an array of arrays.

Declaration and Initialization

int row = 3;
int column = 4
int arr[row][column] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
};

For declaring a 2D array we write the array name followed by its row number and column number. So in the example, the array arr contains 3 rows and 4 columns. For initializing we write the rows as a 1D array and fill up the array with elements equal to the column number.

We can initialize a 2D array like this too-

int arr[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

This array too has 3 rows and 4 columns but it looks a little less organized. So the first approach is preferred.

Traversing 2D Array

For traversing a 2D array we use a nested for loop. We can traverse a 2D Array in two ways-

Row Major Traversing
Column Major Traversing

Row Major Traversing

This is the common way of traversing a 2D array. We can do it with a nested for loop like this-

int row = 3, col = 4;
int arr[row][col] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
};

for(int i = 0; i < row; i++)
{
    for(int j = 0; j < col; j++)
    {
        cout << arr[i][j] << " ";
        //output: 1 2 3 4 5 6 7 8 9 10 11 12
    }
}

In the row-major traversing the outer loop iterates over the rows while the inner loop iterates over the column. As a result, when we access arr[i][j] in each iteration we get row by row elements.

Column Major Traversing

This is a tricky way of traversing and in most places, it's not taught. We can do column-major traversing with a nested for loop like this-

int row = 3, col = 4;
int arr[row][col] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
};

for(int i = 0; i < col; i++)
{
    for(int j = 0; j < row; j++)
    {
        cout << arr[j][i] << " ";
        //output: 1 5 9 2 6 10 3 7 11 4 8 12
    }
}

In the column-major traversing the outer loop iterates over the column while the inner loop iterates over the rows. Point to be noted- here we are visiting arr[j][i] instead of arr[i][j] which means we are visiting elements of each column.

Pointer to a 2D Array

If we can have a pointer to an integer, a pointer to a float, a pointer to a char, then can we can also have a pointer for 2D array. The following program shows how to build and use it.

int row = 3, col = 4;
int arr[row][col] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
};

int *p;

for (int i = 0 ; i < 3 ; i++)
{
    p = &arr[i][0];
    cout << "Row " << i << ":";

    for (int j = 0; j < 4; j++)
        cout << "\t" << *(p+j);

  cout << endl;
}

In the above code, we try to print a 2D array using pointers. At first we initialize a 2D array, arr[row][col] and a pointer (*p)[4], where p is a pointer which stores the address of the first element of the array. We use a for loop to traverse over these 3 elements of the 2D array arr. For each iteration, we assign p with the address of arr[i][0], which is the address of first element of every row. Further, the inner for loop prints out the individual elements of the array arr[i] using the pointer p. Here, *(p + j) gives us the address of the individual element arr[i][j], so using *(p+j) we can access the corresponding value.

Passing a 2D array in a Function

We can pass 2D array into as a function parameter just like any other data. In the code below, we pass the array arr, to a function printArray() which prints out the passed 2D array.

#include<iostream>
using namespace std;

void printArray(int  a[][4], int row, int col)
{
    for(int i = 0 ; i < row; i++)
    {
         for(int j = 0; j < col; j++)
            cout << "\t" << a[i][j];
         cout << "\n";
    }
      cout << "\n";
}

int main()
{
  int  arr[3][4] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21} ;

  printArray(arr, 3, 4);
  return 0;
}

In the function printArray(), the declaration of a looks like this: int a[][4]. Here a is a pointer to an array of 4 integers. Inside the function we can use the array just as we used in other places.

Conclusion

In this article we discussed 2D array C++, how we can traverse it, how to have a pointer of it and lastly how to pass it to a function. If you have any confusion or question you can knock me up at samiunblack@gmail.com. Happy Coding

Increase typing speed

Samiun Black — Sat, 26 Mar 2022 16:50:48 +0000

Today I will share some tips for increasing typing speed and also some websites for different level of typing speeds.

Tips:

First things first DON'T look at the keyboard. Just don't. Cause you can never accelerate your typing speed if you type looking at the keyboard.
Know where the keys are by heart. You need to know it so well that even when you're not focused on typing and thinking something else your hands type by themselves. Don't worry it will come with practice.
Practice Practice Practice. There's no other way to be fast at typing other than practice.
Use Ctrl + backspace. Whenever you need to delete more than one-two letter use Ctrl + backspace. Though it will take some time to get used to it. But once you get used to it you'll type much faster.

Best Places to Learn Typing:

For WPM 0-20: Use keybr.com. This is the most beginner friendly typing practice site I've found. They will show you where your hands are, guide you letter by letter and improves all letters' typing ability equally. Also it feels like a game so you might get addicted to typing practice.

For WPM 20-50: Use 10fastfingers. This is one of the classic typing practice sites. You can see what letters you've wrote incorrect and practice those letters frequently.

For WPM 50-∞: Use monkeytype. Okay, this is my favorite one. It has smooth caret animation, different themes and many other customization options. Also you can flex your typing skill with this site. It has your typing states organized in a nice way and overall the best typing practice site in my opinion.

Surviving Big O: Part I

Samiun Black — Fri, 25 Mar 2022 08:02:29 +0000

Let's be honest- learning Big O is hard for beginners. This article is written so that you don't be afraid of such an innocent topic like Big O. As prerequisite I would recommend you to have some knowledge about loops and nested loops. Let's begin this survival mission-

Simply put, Big O is the sum of all the steps your algorithm takes from beginning to end. Now If you want to flex in front of someone then tell them this definition-

"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity" - Wikipedia

You don't even have to try to understand this. Even I don't know how this definition is related to Big O.

Now let's talk about importance of Big O. Suppose you have written an algorithm and it took 5 millisecond to run in your machine. So you told your friend- "see what a programmer I am. My algorithm runs in 5 milliseconds". Then your friend also ran the same algorithm in his machine and it took 1 millisecond to run. What the heck!!! Actually how many seconds our algorithm will take to run depends on a lot of things like CPU, processor, RAM, programming language etc. Then how are we going to know how fast or slow an algorithm is? This is where our Big O notation is the hero.
With the help of Big O, we can figure out how a code would perform if given a large input. Simply, how much steps the algorithm will take when its given a large input.

Let's see an example-
Suppose you wrote a program to get the sum of all numbers of an array.

def sum_of_array(numbers):
    sum = 0
    for num in numbers:
        sum += num

    return sum

First of all we have declared a variable named
sum. This is one step. So here the Big O is O(1) (The Syntax of Big O is A capital O and then inside parenthesis the number of steps). After the variable we are looping through the array. How are we going to count the Big O of this loop? We know that the loop will iterate through each and every element of the array and add the current number with the sum which is one step. If there are "n" elements in the array then the loop will add the current number "n" times. That means here the total steps will be- 1 * n = n. So we will add a "n" in our Big O- O(1 + n). After that we have a return statement. This return statement is 1 step. That means our final Big O is- O(1 + n + 1) = O(2 + n)

Now how are we going to know which one is one step and which one is "n" steps? When you're code won't depend on the input size that is one step and when it does that's "n" or "m" or "a" or "b" steps. (Note: you don't have to take "n". You can take any character. But taking "n" is a best practice). Let's understand steps with the above example. In the very first line we are declaring a variable sum and assigning 0 to it. It doesn't depend on the input size cause whatever the input size be we will assign 0 here. So it's one step. Next we have a for loop and this for loop depends on the input array size cause it's gonna run through all the elements of the input array till the end of the array. So if there are 5 elements it would run 5 times and if there are 100000 elements it would run 100000 times. So we are taking "n" steps here. At last we are return sum variable. Whatever the input size be we would return the sum variable so it doesn't depend on the input that's why its one step.

If you understand this far, then you are have learnt the fundamental of Big O.🤩🤩🤩

Now let's jump into another interesting example-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

Here we are drawing a square with the help of a nested for loop. I hope you all know how nested for loop works. What's the Big O's gonna look like here? The first for loop will run as many times as the input number is. Let's say the number is "n" Then the first for loop will run "n" times and the second for loop will run "n" times for each iteration of the first loop. That means it would run total n * n times. Recall in the first example we had multiplied 1 * n cause there were 1 step inside the for loop. As there are "n" steps inside the for loop here we are multiplying n * n = n^2. So the Big O here would be O(n^2). Next we have a print() statement inside the first for loop so it will run n * 1 = n. The final Big O will be- O(n + n^2).

If you understand all the above discussed things then learning Big O will be a piece of cake to you now.

Now I want to give you three fun little exercises. Try to solve them on your own first.

1st problem

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

Here for some reasons we are looping over the same array twice (Note: It's not a nested loop) and we are adding all the items to the sum variable in both loops.

2nd problem

def sum_of_two_array(arr1, arr2):
    sum1 = 0
    sum2 = 0
    for i in range(len(arr1)):
        sum1 += arr[i]

    for j in range(len(arr2)):
        sum2 += arr[j]

This one is almost the same as the previous one. But here you're given two input arrays. Remember we can't take "n" for both arrays. We have to take different characters for different inputs. Cause here the first input array can be of size 100000 and the second input array can be of size 5. Now try to solve the problem.

3rd problem

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

This problem also has two inputs just like the previous one. But this one is nested.

Solutions

O(2n)
Because here we have two for loops one after another. If each for loop takes "n" steps then total steps will be- O(n + n) = O(2n)
O(n + m)
Note: Here you can take any character. Taking "m" is not a must.
Here we are iterating over two different arrays one after another that's why it's O(n + m)
O(n * m)
Here we have a nested for loop but over two different arrays. That means for each iteration of first for loop we will iterate "m" times on the second for loop. (here "m" is the number of elements in the second array). So if the first for loop runs "n" times the total steps will be O(n * m)

You know the basics of Big O. Now we will talk about how to simplify big O. First I will state the rules-

Worst Case
Remove Constants
Different Terms for inputs
Drop non dominants

Rule 1: Worst Case
Whenever we are finding Big O of an algorithm we are always concerned about the worst case, that is how many steps the algorithm will take in the worst case. Example-

def search(numbers, target):
    for i in range(len(numbers)):
        if numbers[i] == target:
            return  i

In this code, we are searching for a given number. Now what will its big O look like? Suppose the target number is in the very first index of the array. Then we just need one step. That means O(1). But what if the target number is at the last index of the array? Then we will need to iterate through the whole array which is O(n). Then what will be the real big O? The real big O will be O(n) cause we are always concerned about the worst case when finding out the Big O. Cause if we can optimize the code for worst case it's gonna be optimized for other cases too.

Rule 2: Remove Constants

If there is any constant in the Big O you don't need to keep that. Let's understand it by the very first problem-

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

we saw the big O here was O(2n) which is actually wrong. The real big O here is O(n) cause we need to remove the constants from the Big O.

Rule 3: Different Terms for inputs

We have learnt this rule in problem 2 and 3. Let's understand it again by problem 3:

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

Here two separate input arrays are given. So we need to take two different character or term for two different inputs. Here the Big O will be O(n * m)

Rule 4: Drop non dominants

We saw a example a long time ago-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

Here we said that the Big O is O(n + n^2) but "n" is smaller than "n^2" so we will drop "n" and the real big O here is O(n^2)

These were the four rules. Now you can find Big O for any algorithm. In the next part we will talk about some famous Big Os. See you there.

"Big O"-র সাথে কুস্তি: প্রথম পর্ব

Samiun Black — Wed, 23 Mar 2022 14:01:26 +0000

অনেকের ভিতরে দেখি "বিগ ও" দেখলেই একটা "বিগ ভয়" কাজ করা শুরু করে। বিগ ও র মতো একটা নিরীহ জিনিস কে যেন আপনারা আর ভয় না পান তাই এই আর্টিকেল টি লেখা। এই আর্টিকেল টি পড়ার আগে আপনাকে লুপ এবং নেস্টেড লুপ সম্পর্কে ধারণা নিয়ে আসার জন্য আমি রেকমেন্ড করবো। তাহলে শুরু করা যাক এই কুস্তি-

সহজ ভাষায় বিগ ও হলো আপনার এলগোরিদম শুরু থেকে শেষ পর্যন্ত যতগুলো স্টেপ নিবে তার যোগফল। এখন আপনার যদি অনেক ভাব নিয়ে কারো সামনে বিগ ও-র ডেফিনেশন বলতে হয় তাহলে বলবেন-
"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity" - Wikipedia

এই ডেফিনেশন টি বোঝার চেষ্টা করার কোনো দরকার নাই। আমি নিজে ও এখনো বুঝি নি এটি কিভাবে বিগ ও র সাথে রিলেটেড। শুধু আপনার ভাব নেয়ার ইচ্ছা হলেই এই ডেফিনেশন টি বলবেন।

এবার আসি প্রয়োজনীয়তায়- মনে করেন আপনি একটি এলগোরিদম লিখলেন। এবং রান করে দেখলেন সেটি চলতে আপনার মেশিন এ ৫ মিলিসেকেন্ড সময় লাগে। আপনি খুব ভাব নিয়ে আপনার বন্ধু কে বললেন- আরেহ আমি তো বিশাল প্রোগ্রামার আমার এলগোরিদম ৫ মিলিসেকেন্ড এ রান করে। শুনে আপনার বন্ধু সেই একই এলগোরিদম নিজের মেশিন এ চালিয়ে দেখলো- তখন এটি চলতে ১ মিলিসেকেন্ড নিলো। কি ব্যাপার?? আসলে আমাদের এলগোরিদম কত সেকেন্ড এর ভিতর রান করবে সেটি অনেক কিছুর উপর নির্ভর করে যেমন- সিপিইউ, প্রসেসর, RAM, প্রোগ্রামিং ল্যাঙ্গুয়েজ ইত্যাদি। তাহলে আপনি কিভাবে বুঝবেন আপনার এলগোরিদম টি কত তা স্লো বা ফাস্ট হবে? এইখানে আমাদের বিগ ও নোটেশন টি কাজে লাগে। বিগ ও র সাহায্যে আমরা একটি কোড অনেক লার্জ ইনপুট দিলে কেমন ভাবে পারফর্ম করবে সেটি বের করতে পারি। আরো সুন্দর ভাবে বললে ইনপুট যত বড় হবে তখন এলগোরিদম টির সকল স্টেপ শেষ করতে কত সময় লাগবে সেটি বের করতে পারি।

একটা উদাহরণ দিয়ে বোঝায়-
মনে করেন আপনি একটি প্রোগ্রাম লিখলেন একটি array র সকল এলিমেন্ট এর যোগফল বের করার জন্য।

def sum_of_array(arr):
    sum = 0
    for num in arr:
        sum += num

    return sum

একদম প্রথমে আমরা একটা ভ্যারিয়েবল ডিক্লেয়ার করেছি sum নামের। এই ভ্যারিয়েবল টি একটি স্টেপ। তাই এখানে বিগ ও হবে O(1) (আমরা বিগ ও র সিনটেক্স এইভাবে লিখি- একটি বড় হাতের O এবং তারপর ফার্স্ট ব্রাকেট এর ভিতর স্টেপ এর সংখ্যা।) ভ্যারিয়েবলটির পরে আমরা একটি লুপ চালাচ্ছি। এখন এই লুপ এর বিগ ও কেমন হবে? এরে টি তে যতগুলো এলিমেন্ট আছে লুপ টি ততবার চলবে এবং প্রত্যেকবার sum এ কারেন্ট নম্বর টি যোগ করবে তারমানে একটি স্টেপ। ধরে নিলাম এরে তে "n" সংখ্যক নম্বর আছে। তারমানে এখানে মোট স্টেপ এর সংখ্যা হবে- 1 * n = n। তাই আমরা বিগ ও তে "n" যোগ করে দিবো। তাহলে এখন বিগ ও হবে- O(1 + n)। এরপরে আমরা একটি রিটার্ন স্টেটমেন্ট দেখতে পাচ্ছি এই রিটার্ন স্টেটমেন্ট টি ১ টি স্টেপ। তাহোলে আমাদের ফাইনাল বিগ ও হবে-
O(1 + n + 1) = O(2 + n)

এখন ভাই কোনটাকে একটা স্টেপ ধরবো আর কোনটাকে এইরকম "n" স্টেপ ধরবো? যেখানে আপনার কোড ইনপুট এর সাইজও এর উপর নির্ভর করবে না সেটি ১ টি স্টেপ এবং নির্ভর করলে “n” বা “m” বা “a” বা “b” টি স্টেপ। (লক্ষ্য করেন এখানে “n” ধরতে হবে এমন কোনো কথা নেই. আপনি যেকোনো কিছু ধরতে পারেন কিন্তু “n” ধরা একটি বেস্ট প্রাকটিস।) উপরের কোড দিয়ে আপনাকে স্টেপ এর বিষয় টি আরেকটু ভালো করে বুঝিয়ে দি- দেখেন ফার্স্ট লাইন এ আমরা যেখানে sum ভ্যারিয়েবল টি লিখেছি সেখানে আমরা ইনপুট এরে টির সাইজ এর উপর নির্ভর করছি না। কারণ সাইজ যাই হোক আমরা sum ভ্যারিয়েবল টিতে 0 এসাইন করবো। তাই এখানে একটি স্টেপ। তারপরে ফর লুপ টি কিন্তু এরে র সাইজ এর উপর নির্ভর করে, কেননা আপনার এরে র সাইজ যদি হয় ৫ তাহলে ফর লুপ এর ভিতরের কোড চলবে ৫ বার, যদি সাইজ ১০ হয় তাহলে ফর লুপ এর ভিতরের কোড চলবে ১০ বার। তাই আমরা এখানে "n" স্টেপ নিয়েছি। শেষে আমরা sum ভ্যারিয়েবল টি রিটার্ন করছি। আপনার এরে র সাইজ যতই হোক না কেন আমরা কিন্তু sum ভ্যারিয়েবল টি রিটার্ন করবো তারমানে এখানে আমরা একটি স্টেপ নিচ্ছি।

আপনি যদি এই পর্যন্ত বুঝে থাকেন তাহলে আপনি বিগ ও র বেসিকটুকু শিখে ফেলছেন। 🤩🤩🤩

এবার আপনার জন্য আরেকটি ইন্টারেষ্টিং উদাহরণ দি-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

এখানে আমরা একটি নেস্টেড ফর লুপ দিয়ে একটি বর্গ আঁকছি। আশা করি আপনারা সবাই জানেন কিভাবে নেস্টেড ফর লুপ কাজ করে। তাহলে এখানে বিগ ও কেমন হবে? প্রথম ফর লুপ টি কতবার চলবে? নম্বর টি যত হবে ততবার নিশ্চয়। সেকেন্ড ফর লুপ টি ফার্স্ট ফর লুপ এর প্রত্যেক টি ইটারেশন এর জন্য নম্বর টি যত ততবার চলবে। তাহলে যদি ফার্স্ট ফর লুপ টি চলে "n" বার এবং সেকেন্ড ফর লুপ টি ফার্স্ট ফর লুপ এর প্রত্যেক টি ইটারেশন এর জন্য চলে “n” বার তারমানে নিশ্চয় গুনফল হবে n * n। দেখুন প্রথম উদাহরণ এ ও আমরা n * 1 করেছিলাম কারণ ওখানে ফর লুপ এর ভিতরে ১ টি স্টেপ ছিল। এখানে যেহেতু ফর লুপ এর ভিতরে "n" টি স্টেপ আছে সেহেতু আমরা n * n = n^2 ধরবো বিগ ও। এরপর আমরা একটি print() লিখেছি এটি যেহেতু প্রথম ফর লুপ এর ভেতর সেহেতু আমরা n * 1 = n যোগ করবো বিগ ও তে। তারমানে ফাইনাল বিগ ও হবে- O(n + n^2)।

আপনি যদি এইটুকু বুঝতে থাকেন তাহলে আপনার বাকি বিগ ও গুলো বুঝতে আর কেন সমস্যা হবে না।

এখন আপনার জন্য একটি এক্সারসাইজ দিতে চাই। উত্তর ও আমি দিয়ে দিবো কিন্তু উত্তর না দেখে আগে ১০ মিনিট নিজে নিজে বের করার চেষ্টা করুন উত্তর কি হতে পারে-

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

এখানে আমরা কোনো একটা বিচিত্র কারণে দুইবার পর পর লুপ করছি (এটি কিন্তু নেস্টেড লুপ না) এবং এরে র প্রত্যেকটি আইটেম কে sum এর সাথে যোগ করছি দুইটি লুপেই।

উপরের প্রব্লেম টি সল্ভ করতে পারলে আপনাকে আরো দুইটি প্রব্লেম সল্ভ করতে দি যেটা আপনার এই পর্বের লার্নিং তাকে একদম পাকা পোক্ত করবে-

def sum_of_two_array(arr1, arr2):
    sum1 = 0
    sum2 = 0
    for i in range(len(arr1)):
        sum1 += arr[i]

    for j in range(len(arr2)):
        sum2 += arr[j]

এটি প্রায় আগের কোডটির মতোই। কিন্তু এখানে আপনাকে দুইটা ইনপুট দেয়া হয়েছে। মনে করিয়ে দি আবার- আপনি কিন্তু দুইটা ইনপুট থাকলে দুটিকেই “n” ধরতে পারবেন না। একটি কে “n” অন্যটিকে অন্য কোনো অক্ষর ধরতে হবে। কেননা দুইটা ইনপুট এর সাইজ একই হবে না। একটি ১০০০০০০০ সাইজের এবং আরেকটি ৫ সাইজের হতে পারে। এবার আপনি প্রব্লেম টি সল্ভ করার চেষ্টা করেন।

শেষ প্রব্লেম-

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

এই প্রব্লেম এ ও আগেরটির মতোই দুইটি ইনপুট। আপনি যদি আগের প্রব্লেমটি সল্ভ করতে পারেন তাহলে এটি সল্ভ করা অনেক সহজ হবে।

আশা করি সবগুলো প্রব্লেম সল্ভ করতে পেরেছেন। আমি এখন উত্তর বলে দিচ্ছি-

১. O(2n)
কেননা এখানে আমরা দুইটা ফর লুপ পর পর করছি। প্রতিটি ফর লুপ এ যদি n স্টেপ নি তাহলে যোগফল O(n + n) = O(2n) হবে।

২. O(n + m)
নোট: এখানে আপনি "m" না ধরে যেকোনো অক্ষর ধরে নিতে পারেন। আপনার টি ও সঠিক হবে।
এখানে O(n + m) কারণ এখানে দুইটি ফর লুপ পর পর করা হচ্ছে কিন্তু এরে দুইটি আলাদা তাই আমরা দুইটি আলাদা অক্ষর নিয়েছি।

৩. O(n * m)
এখানে নেস্টেড ফর লুপ হয়েছে। কিন্তু দুইটি ভিন্ন এরের উপর। তারমানে প্রথম ফর লুপ এর প্রতিটি ইটারেশন এর জন্য দ্বিতীয় ফর লুপ টি “m” বার চলবে। প্রথম ফর লুপ টি যদি “n” বার চলে তাহলে মোট স্টেপ হবে n * m

আপনি এখন বিগ ও র বেসিক টুকু পারেন। এখন আমরা কথা বলবো কিভাবে বিগ ও টি সিম্পলিফায় করবেন। ফার্স্ট এই আমি রুলস গুলো বলি -
১. Worst Case
২. Remove Constants
৩. Different Terms for inputs
৪. Drop non dominants

রুল ১: Worst Case
আপনি যখন একটি এলগোরিদম এর বিগ ও বের করবেন তখন আপনাকে সবসময় সবচেয়ে প্রতিকূল অবস্থায় এলগোরিদম টি কয়টি স্টেপ নিবে সেটি বের করতে হবে। একটা উদাহরণ দি-

def search(numbers, target):
    for i in range(len(numbers)):
        if numbers[i] == target:
            return  i

এই কোড টি তে আমরা একটি নির্দিষ্ট নম্বর খুঁজছি একটি এরের ভিতর। এখন এখানে বিগ ও কেমন হবে? মনে করুন টার্গেট নম্বর টি এরের একদম শুরুতে আছে। তাহলে কিন্তু আমরা একটি স্টেপ নিয়েই নম্বর টি পেয়ে যাবে তারমানে বিগ ও হবে O(1). কিন্তু যদি টার্গেট নম্বর টি এরের একদম শেষে থাকে তাহলে কি হবে? তখন আমাদের পুরো এরেটি লুপ করতে হবে তারমানে এরেটিতে যতগুলো আইটেম আছে ততগুলো স্টেপ অর্থাৎ O(n) এখানে তাহলে আসল বিগ ও টি কেমন হবে? এখানে বিগ ও হবে O(n) কারণ বিগ ও নিয়ে কথা বলার সময় আমরা সবসময় Worst Case টি ভাবি। কারণ আমরা যদি worst case এর জন্য একটি এলগোরিদম ইফিসিয়েন্ট বানাতে পারি তাহলে অন্য case এর জন্য এমনিই ইফিসিয়েন্ট হয়ে যাবে।

রুল ২: Remove Constants
আপনার এলগোরিদম থেকে কোনো কনস্ট্যান্ট থাকলে সেটি রাখার প্রয়োজন নেই। একদম ফার্স্ট প্রব্লেম দিয়ে এটি বুঝিয়ে বলি-

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

আমরা দেখেছিলাম এর বিগ ও- O(2n) আমাদের সেকেন্ড রুল অনুযায়ী আমরা এখন থেকে 2 বাদ দিয়ে দিবো তারমানে আমাদের আসল বিগ ও হবে O(n)

রুল ৩: Different Terms for inputs
এই রুল টি আমরা আগেই শিখেছি। প্রব্লেম ২ এবং ৩ এ এই রুল টি ব্যবহার করা হয়েছে। আমি আপনাদের প্রব্লেম ৩ দিয়ে আরেকবার বুঝিয়ে দি-

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

এখানে দুইটি ইনপুট এরে দেয়া হয়েছে তারমানে আমাদের দুইটি এরে র জন্য দুইটি আলাদা অক্ষর বা টার্ম ব্যবহার করতে হবে। এখানে বিগ ও হবে O(n * m).

রুল ৪: Drop non dominants
আমরা অনেক আগে একটি উদাহরণ দেখেছিলাম-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

এখানে আমরা বিগ ও বের করেছিলাম- O(n + n^2). এখানে "n" কিন্তু "n^2" এর থেকে ছোট। তারমানে এখানে n^2 সবচেয়ে বেশি প্রভাব ফেলবে তাই আমরা "n" টিকে বাদ দিয়ে দিবো। এখানে আসল বিগ ও হবে- O(n^2)

এই ছিল আমাদের চার টি রুলস। আপনি এখন যেকোনো এলগোরিদম এর বিগ ও বের করতে পারবেন। দ্বিতীয় পর্বে আমরা কিছু বিখ্যাত বিগ ও নিয়ে আলোচনা করবো।

আশা করি আপনাদের বিগ ও সম্পর্কে ভয় টি এখন কেটেছে। দ্বিতীয় পর্বে আবার দেখা হবে। সবার প্রোগ্রামিং যাত্রা সুন্দর হোক 😃😃😃