DEV Community: Snehendu Roy

Space Complexity | Measure your code performance: DSA 002

Snehendu Roy — Mon, 22 Aug 2022 01:46:00 +0000

In my previous article I wrote about time complexity. A way to measure code with respect to growing size of inputs.

Time complexity is basically the relation between input size and running time

Think About It

You obviously have apps in your phone. You are most likely to prefer the ones which takes less time to load the data and consumes less space. The factor which is used to measure the time is related to time complexity. But what about the space? How do we measure the space used by a code?

Space Complexity

The relation between the input size and memory consumed in your system.

If you want your code to be optimized, it should take less time and less space too. So, here's where space complexity comes in place cause this is the way to measure how much space your code will take

Calculating Space Complexity

The space used by a code depends on how many variables are used. The more variables, the more space used.

How much memory consumed by a code is directly proportional to how many variables assigned

sum = 0
i = 0
while (i < 24):
    sum += i
    i += 1
print(sum)

Here, there are 2 variables which we are assigning to the memory that is i and sum. Now, no matter the the value of sum increases the memory used by that one variable would be the same. So, the space complexity for this code will be O(1)

Now, let's take the example of arrays. It is basically a data structure which stores a list of elements. We will talk about arrays deeply later

def create_array(n):
    a = []
    for i in range(n):
        a.append(i)
    return a

In this function, we take integer n as an input. Then we create an array. Using the loop we store the numbers 0 to n-1 in the array. Then we return it. So, basically what we are doing is, we are generating a series of numbers and storing it in an array. Here, with the increasing size of input, the space used by the code also increases. So, the space complexity for this code is O(n)

You can check the size here:

sys.getsizeof() gives out the size of a particular function, class, variable etc. in python

I really hope you understood, if you didn't then feel free to criticize in the comment section. It's okay to criticize if I have wasted your valuable time. Also if you have any doubts, feel free to put it up in the comments section

Time Complexity | DSA 001

Snehendu Roy — Fri, 19 Aug 2022 01:30:40 +0000

Ways to calculate code performance

Approach 1: Time based approach

calculateTime()
function fancyName(){
   do something
}
calculateTimeDifference()

In this approach of judging code, before running a chunk of code, the initial time is taken and after running that code, the final time is taken. Then when the final time is subtracted from initial time, we get the how much time was required for processing of the code.

This method of calculating code performance is rated as average but still this approach is used hugely to judge code

Problems in Approach 1:

It is based on machine: Depends from processor to processor
It is based on processing: Depends on the processing power of your PC

Approach 2:

Counting the number of operations in a code. Technically, this literally means that we are going to count the number of operations in a code.

Count Operation in the code below
a = a + 1

If you said there is one operation, you are wrong my friend. There are actually 2 operator: "=" and "+"

Now, count the operation in this code

sum = 0
winner = 1
for (i = 1; i < n; i++){
  sum = sum+1
}

Notice closely, that there are several operators. In total, there is 3 "="s, 1 "<", then in i++, there are actually 2 operators which are responsible to increment the value of i, i++ can be written as i = i+1, so in i++ there are 2 operators. Then inside the loop there are 2 operators: "=" and "+"

But, in this code, apart from sum = 0, winner = 1, i=1, all the other operators are dependent on the variable n. So, there are 3 constant operators, and 5 operators which varies with the value of n. Thus there are 3+5n operators

Big O

The whole way of measuring code with number of operators is known as Big O.

Code 1

sum = 0
i = 0
while (i < n):
    sum += i
    i += 1
print(sum)

In this given code, there are 5n+2 operators.

Now, coming to the complexity of the code: To measure the complexity of the code, the constants are to be ignored.

So O(n) [Said as O of n] is the complexity

Code 2

for (------):
  ---------
  ---------
for (------):
  ---------
  ---------

You might think that the complexity of the above code is 2O(n) and that's completely correct. But since the constants are to be ignored, so the complexity will be O(n).

Code 3

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    sum+=j
  }
}

In the above code, O(n) is inside another O(n). Thus, the complexity of the code becomes O(n^2). If the nested loop would run on a constant and not on N, the complexity would not be O(n^2).

Complexity Notation

Code Complexity	Notation	Note
O(10), O(1000) O(k), 3O(k) kO(k)	O(1)	"k" is some constant
O(3n), O(4n+100000)	O(n)	Constants are to be ignored
O(3n^2), O(4n^2+100000)	O(n^2)	Constants are to be ignored
O(3n^2), O(4n^2 + 3n + 4)	O(n^2)	Since with increasing value of n, the value of n^2 will become much higher than theat of n, so n can be ignored, incase of cubic equations,the complexity will be O(n^3) and so on

This graph shows the time for complexity of code with increasing input.

Introduction to Data Structures and Algorithms | 000

Snehendu Roy — Wed, 17 Aug 2022 00:49:00 +0000

I am going to call Data Structures and Algorithms as DSA
Code written is in Python

Why DSA?

The main moto to learn DSA is to know how to write optimized code. In this age of Cloud Functions, the optimized code requires less money as less computation and memory is used in the servers. On the other hand if you don't write optimized code, you will have to pay more money and also the results from the cloud servers would be very slow.

Judging code

Now you know that writing optimized code would save your time. But how will you judge if a code is optimized or not?
Many people say that the less number of lines means the more optimized code. But this is a true lie. Optimized code can't be judged by the number of lines but the parameters involved in the code. Judge this case:

Problem Statement: Generate a series of number from 1 to n and store it in a variable or function so that it can be accessed later

Code 1:

def gen_series():
    a = []
    n = int(input("What's n? "))
    for i in range(1, n+1):
        a.append(i)
    return a

def print_series():
    a = gen_series()
    for i in a:
        print(i)

if __name__ == "__main__":
    print_series()

Code 2:

def gen_series():
    n = int(input("What's n? "))
    a = series(n)
    print(a)
    return a

def print_series():
    a = gen_series()
    for i in a:
        print(i)

def series(n):
    d = 11
    for i in range(1, n+1):
        yield i + d
        d += 11

if __name__ == "__main__":
    print_series()

If you count the number of lines, you would say Code 1 is more optimized but is it?

In both the cases the series is generated and stored inside the function named gen_series(). If you know about the sys.getsizeof() method in python, you will know that it gives out the memory used inside a variable, function. If you write this in your code editor, run the program, and enter 200 as the input of What's n?

import sys


def gen_series():
    a = []
    n = int(input("What's n? "))
    for i in range(1, n+1):
        a.append(i)
    return a


def print_series():
    a = gen_series()
    for i in a:
        print(i)


if __name__ == "__main__":
    print(sys.getsizeof(gen_series()))

You will get the memory used in bytes. And surprisingly, you will notice that the 2nd code consumes less memory.

So, we can come to a conclusion that less code always doesn't mean optimized code. For a code to be judged, the parameters are important.

Programming Language

DSA is mostly independent of programming language the main things which matter are the concepts. I'll be using python in the next articles regarding DSA

Generators in Python

Snehendu Roy — Mon, 15 Aug 2022 04:01:25 +0000

Starting Note

Before reading this blog, I want to make a clear statement that this blog is written completely based on my understanding about how generators work in python. To move forward, you must be an intermediate in python.

Iterators

An object that contains countable number of values. The next value can be accessed with the next(object_name) parameter

You can know more about iterators here: Iterators by W3 Schools

Case

Let's say you are working in a company and your company gives you a task to write a program to find a series of numbers. Each number having a difference of 12 from the previous. So the series is like: [12,24,36,48.....]

You have to find the series till a number given by the user and store the results somewhere so that others get those values using a loop.

So, if the user enters 10, the program will return a series like: 12,24,36,........,120

You will be like: Okay that's easy

def gen_series():
    n = int(input("What's n? "))
    a = []
    d = 11
    for i in range(1, n+1):
        a.append(i + d)
        d += 11
    return a

if __name__ == "__main__":
    print(gen_series())

Now, your program works nicely if the user inputs numbers like 12, 23, 89, 74.

If you test this code yourself and you enter a number like 1000000000000000 then what happens?
Your code starts to hang, the program doesn't work smoothly. So, this is not the best approach to get a series of numbers.

Let's refactor this code a bit

def gen_series():
    n = int(input("What's n? "))
    a = series(n)
    print(a)

def series(n):
    a = []
    d = 11
    for i in range(1, n+1):
        a.append(i + d)
        d += 11
    return a

if __name__ == "__main__":
    gen_series()

Now, the program runs the same but our problem is not yet solved. We want to generate a series of numbers with each number having a difference of 12 from the previous and we want our program to generate as much numbers as we want.

Try to run this code:

def gen_series():
    n = int(input("What's n? "))
    a = series(n)
    print(a)


def series(n):
    d = 11
    for i in range(1, n+1):
        yield i + d
        d += 11


if __name__ == "__main__":
    gen_series()

If you run this code and input a number as 20, you will see the output as <generator object series at 0x0000020B20684350>. Now, if you run again, and input a big number such as 1000000000000000, you will notice that your program doesn't lag. It works perfectly fine and you get the output.

The yield keyword is responsible to make this function a generator.

The series function is now a generator function which generates an iterator. If you have read the article of W3 Schools, you will certainly know that we can easily access the values from an iterator using a loop.

So, here's the definition of generators

Generators

Generators are those kind of functions that return an iterator.

Back to program

Now to print the values of the series we can use another function

def print_series():
    a = gen_series()
    for i in a:
        print(i)

The complete code:

def gen_series():
    n = int(input("What's n? "))
    a = series(n)
    print(a)
    return a


def print_series():
    a = gen_series()
    for i in a:
        print(i)


def series(n):
    d = 11
    for i in range(1, n+1):
        yield i + d
        d += 11


if __name__ == "__main__":
    print_series()

Conclusion

Generators are functions that return an iterator
We can turn a normal function to generator by using the yield keyword

If you didn't understand then don't forget to criticize me in the comments. That will help me to come up with a better explanation. It is okay to criticize me if I have wasted your time. Also if you have any questions, please ask me in the comments

Solana

Snehendu Roy — Tue, 29 Mar 2022 08:44:21 +0000

What is Solana?

It is an open source project which aims to make a fast, high-performance, permission-less blockchain.

Why Solana?

It is possible for a centralised database to handle 710,000 transactions per second on a standard network if the transaction size is not more than 176 byes. A centralised database can also replicate itself and maintain itself highly without significantly compromising that transaction rate using the distributed system technique known as Optimistic Concurrency Control. Solana aims to achieve these theoretical limitations in its blockchain network.

Optimistic Concurrency Control

It is a method of generating correct results of concurrent operations which are applied to systems which record transactions.

How does it achieve

It is by a new mechanism called as proof of history. In normal blockchain transactions, nodes have to interact with each other to verify a transaction. Through proof of history, there is a standardised clock in every block of the network. In other networks, there is no standardised clock

The lack of a trusted source of time (i.e., a standardized clock) meant that when a message timestamp was used to accept or reject a message, there was no guarantee that every other participant in the network would make the exact same choice. Proof of History gets past this hurdle, with every node in the network able to rely on the recorded passage of time in the ledger on the trustless basis that is key to blockchain functioning

Fallback true returns error while deployment

Snehendu Roy — Tue, 29 Mar 2022 08:42:25 +0000

Next Js by itself is a super power over react. With its functions like getStaticPaths() and getDtaticProps(), dynamic page generation becomes truly easy.

But in most cases, fallback true returns error during deployment

export async function getStaticPaths() {
   returns {
     paths: paths, 
     fallback: true // returns erroe
   }
}

To solve this, you must handle the data coming from getStaticProps() in your component

export default function App({data}) {
  if (!data) return null;
}

This simple one liner, at the top of your component page where getStaticPaths()is used, can fix all the problems regarding this during deployment.

Fallback true returns error while deployment

Snehendu Roy — Tue, 01 Mar 2022 10:35:04 +0000

Next Js by itself is a super power over react. With its functions like getStaticPaths() and getDtaticProps(), dynamic page generation becomes truly easy.

But in most cases, fallback true returns error during deployment

export async function getStaticPaths() {
   returns {
     paths: paths, 
     fallback: true // returns error
   }
}

To solve this, you must handle the data coming from getStaticProps() in your component

export default function App({data}) {
  if (!data) return null;
}

This simple one liner, at the top of your component page where getStaticPaths()is used, can fix all the problems regarding this during deployment.

Crypto Arbitrage: This can make you millions

Snehendu Roy — Tue, 22 Feb 2022 03:12:14 +0000

Introduction

Crypto Arbitrage is a process through which you can make much money by swapping crypto coins
Let that blow your mind for a while

Swapping

There are crypto exchange platforms like Uniswap, Sushiswap where you can swap cryptos. Let's say you have a METAMASK account with 1 ETH in it. Now, if you swap 1ETH with Dai you might get 2200 DAI. So this is what swapping is, exchange of tokens.

How is it related to profit

The amount of DAI you get for 1 ETH is different for each platforms. For example if you get 2200 DAI for 1 ETH in Uniswap, then 1 ETH might be equivalent to 2000 DAI in Sushiswap.

The Profit

Now, you have 1 ETH in your account, you go to Uniswap where 1ETH is equivalent to 2200 DAI. So, you have 2200 DAI in your account now.

Then you go to SushiSwap where 1 ETH is equivalent to 2000 DAI. You exchange 2000 DAI from your account for 1 ETH and still you are left with 200 DAI. That's your free profit.

What do you need

To start this arbitrage and earn:

Capital: You need some tokes in your wallet to do this
Knowledge: You need to know how much you are getting for the tokens in you have in different websites ## Automation Now there is a way to do this arbitrage automatically even if you don't have any capital.

You can make a smart contract and a node server to do this. Here's how it will work.

Smart Contract

Take a flash loan
Swap the flash loans in one Exchange where you get more of you preferred tokens
Again swap the tokens in other exchange where its price is low
Send the tokens widrawn from the Flash Loan and keep the rest

Node Server
Check the price of tokens in exchanges and according to that execute smart contract events.

Features of Blockchain which makes it useful

Snehendu Roy — Wed, 05 Jan 2022 01:08:16 +0000

Introduction

Blockchain contains 2 words in itself one is block and the other is chain. The block represents the data which are stored in variety of computers and chain makes the network. So the blockchain is a record of data stored in networks of computers.

There are 3 features of blocchain which makes it useful:

Decentralization
Immutability
Transparency

Decentralization:

Once a data is being created, it gets divided among the network of computers and no particular authority has a hold on it. So, no centralized authority is present in a blockchain platform.

Immutability

Once a data is being put up in the blockchain network, it cannot be altered or forged. This happens due to advanced cryptography hashing concepts.

Transparency

In a blockchain network every action is stored as a transaction and once a transaction is made, the data becomes available to all. Since no central authority remains and the data is also immutable, the data is kept forever and everyone can see it making it a transparent and trustable system for everyone.

Linux Commands that you need to know

Snehendu Roy — Wed, 01 Dec 2021 20:21:16 +0000

ls
Helps you to list the directories

pwd

Helps to know the exact directory you are in

alias
This helps you to create your own shortcuts of commands.
Example:

alias cls=clear

One tip: Install tmux in linux. If you want me to make a detailed post then make sure to comment down below

GHOST CMS. Is it a superpower for making blog-applications

Snehendu Roy — Tue, 23 Nov 2021 20:56:42 +0000

INTRODUCTION

Ghost CMS can be a lifesaver and a timesaver if you want to make a fulstack blog app.

DETAILS

Ghost CMS provides you a prebuilt admin dashboard which makes 70% of your works easier. You can directly publish a blog post through that admin panel.

It will provide you with a REST API with a bunch of endpoints and you can use those in your next blog application.

Visit: GHOST for reference

In short you can say that if you get into any error in the backend portion for making your next node.js app, then you can use ghost CMS as your REST API. Rather than that, it also provides you support like WordPress

Redux the easiest way [Part 2]

Snehendu Roy — Fri, 05 Nov 2021 19:49:53 +0000

So in the 1st part we saw a story for understanding about redux. So what redux basically does is that it takes the data from other screens and those data can afterwards be rendered in other screens without any sort of prop drilling. So, it basically puts up the state to the steroid form.

Redux: Three Principles

Store: The global state of your application is stored in a store from where the data flows through different screens and you can have access to them.
Actions: The only way to change the state is to emit an action. In the example story of part 1, we saw that, your sister tells Clark to give the pizza then only Clark gives it to her. This 'call for pizza' is actually an action.
Reducer: This is basically the function which is fired once an action is emmited. In the story, when your sister calls for the pizza, Clark checks the box and if there is a pizza for her he returns it. This whole thing that Clark is doing is an example of a reducer. This is kind of the brain of the redux.