DEV Community: Awdesh

Step by step guide to create an analytics application with AWS Redshift using AWS Lambda and S3

Awdesh — Tue, 13 Apr 2021 13:41:24 +0000

AWS Redshift is a data warehouse service where you can run analytics and make smart product decisions. Redshift can easily scale on petabytes of data with blazing fast querying speed.

Its query engine is powered by PostgreSQL which means that PostgreSQL drivers for every language will work just fine to connect to the Redshift cluster. You can query data inside Redshift just like you'd query the data in Postgres.

Why not use a regular RDBMS solution to run data analytics?

Regular databases are meant for OLTP purposes i.e. they are good for transactions over the database. A standard application writes and reads into the database a lot and that's where a regular OLTP solution shines.
For an analytics application we feed the data into the database once and then read it many times where OLTP solutions aren't the perfect fit. An OLAP solution like Redshift fits perfect and gives great performance.
OLAP solutions store data in column-based storage for fast table scans.
Amazon Redshift, Google's Big Query, and Snowflake are some examples of the OLAP database.

How can we populate Redshift database

There are a couple of ways by which we can unload data from S3 to Redshift. Let's explore them in details.

#1 AWS Glue

We can hand over the work of offloading the data from S3 to Redshift by using another AWS service "AWS Glue". As the name suggests it'll work as a Glue between the two services by dynamically creating schema from the uploaded file inside S3.

AWS Glue which can run crawler on the uploaded file inside S3 and accordingly create a schema for us for Redshift database.

#2 AWS Lambda

Another option is to take the matter into our hand :P and create tables manually inside Redshift, trigger AWS Lambda from S3 upload operation and let Lambda COPY data from JSON to Redshift.

I have experimented with both the options and I prefer the latter because I don’t want the dependency on another AWS service(AWS Glue) when I can manually create the schema which doesn't change too often. Also, it is an optimized option from a cost perspective.

Let's get started.

1) Create Redshift cluster using AWS console.

First and foremost we need to create a Redshift cluster from the AWS console. You can choose "free trial" which is more than enough for POC purposes. The free trial gives 1 node of "db2-large" with 160GB storage. Creating a cluster is pretty fast and doesn't require any custom configuration. You can choose default settings and provide your master username and password to have your cluster ready in few mins.

2) Create a new table inside Redshift.

Using the Query Editor connect to the database using the credentials that you have supplied while creating the Redshift cluster.
Once you are connected to the database you can use the Query Editor to run the regular SQL commands.
To create a new table simply run

Create table public.<table_name>

this will create a new table with the given table name in the database that you are on under the public schema category. Query Editor left pane will allow you to choose the database, schema category.

If you prefer video tutorial, I have a video on YT of above steps. You can find it here.

3) Create a Lambda function

Lambda function is going to be quite simple and straightforward. We are just going to pass a file location inside S3, connect to Redshift and unload the file in it.

import json
import psycopg2
import boto3

def lambda_handler():
    key = "file.json"
    loc = "'s3://mybucket-awdeshcodes/%s'" % (key)
    output = unload_to_redshift(loc)
    print("output: ", output)
    return {
        'statusCode': 200,
        'body': json.dumps('Hello from Lambda!')
    }

def unload_to_redshift(loc):
    con = psycopg2.connect(dbname='snippets',host='<redshift_endpoint>',port='5439', user='<master_username>', password='****')
    cur = con.cursor()
    # Begin your transaction
    cur.execute("begin;")
    cur.execute(
        "COPY public.<table_name> FROM" + loc + "CREDENTIALS 'aws_iam_role=arn:aws:iam::1234567:role/lamda-s3-rd-full-access' json 'auto';")
    # Commit your transaction
    cur.execute("commit;")
    # Commit your transaction
    cur.execute("commit;")

I am using psycopg2 python driver to connect to the Redshift cluster from lambda. The connection line is most important.

psycopg2.connect(dbname='snippets',host='<redshift_endpoint>',port='5439', user='<master_username>', password='****')

dbname: Name of the Redshift database used when we created the cluster and where our table exists.
host: Redshift endpoint. You can find that by clicking on the cluster link.

When you copy the entire endpoint from the console, it'll come up with the database name and port at the end, make sure to remove them since we are going to use port and database name in a separate param.

user: This is the master username for the Redshift cluster.
password: password used for the master username.

Another important command in the above snippet is the COPY command that is going to COPY the file from S3 to RS. Let's take a look at it.

COPY public.<table_name> FROM" + loc + "CREDENTIALS 'aws_iam_role=arn:aws:iam::1234567:role/lamda-s3-rd-full-access' json 'auto';")

table_name: use the name of the table that you created in the previous step inside the Redshift cluster.

CREDENTIALS 'aws_iam_role=arn:aws:iam::1234567:role/lamda-s3-rd-full-access

Use the command as is. YES, you have to write "CREDENTIALS" as is followed by a whitespace and ARN of the IAM role.

This brings us to the IAM role which we haven't discussed yet.

4) Create an IAM Role.

Go to IAM service and create a new role with access to S3 and Redshift service. At the moment I have given this role FullAccess to both services but I believe certain actions like writing to S3, deletion can be revoked.

Now in the second tab of "Trusted relationships", press Edit and Add below policy.

{
  "Version": "2012-10-17",
  "Statement": [
    {
      "Effect": "Allow",
      "Principal": {
        "Service": "redshift.amazonaws.com"
      },
      "Action": "sts:AssumeRole"
    }
  ]
}

By doing this we are allowing this new role to take action on the Redshift cluster. Action in our scenario is a COPY operation inside the table.

Now we have to associate this new role with the Redshift cluster as well. So switch to the Redshift cluster tab and open the Properties tab inside the cluster.

Now if we scroll down a bit inside Properties we see "Cluster Permission" where we have to click on "Manage IAM roles" and add the ARN of the newly added IAM role from the above step. Click Associate and give the cluster couple of minutes to take in the effect of changes.

At this point, we have associated the newly IAM role with the Redshift cluster and we can use the same IAM role inside our Lambda function as well.

So let's get back to step#3 where we left it and copy the arn of IAM role like below.

CREDENTIALS aws_iam_role=<arn_of_the_newly_created_role>

At this point we can upload a json file in S3 with three fields

{
     "id":1,
    "title":"AWS Redshift",
    "description": "description"
}

The upload operation will trigger the Lambda which is going to run the COPY command to copy the fields inside JSON into Redshift table.

Open Redshift query editor and run the select command, you should see new records getting populated there.

Connect to cluster from outside the VPC

If you are looking to use a SQL client instead of AWS's Redshift console to query the data you can use SQLWorkbench.

Download SQLWorkbench from this location

https://www.sql-workbench.eu/download-archive.html

Once downloaded, uncompress it and it will have sqlworkbench.exe* and ''SQL workbench.sh** which can be used for running workbench on windows and Unix platforms. Make sure Redshift cluster is accessible from outside the VPC, you can enable it from Properties-> Network settings.

From File -> Connection Windows you can create a new connection. Below is a screenshot of my sql workbench connection config to Redshift.

References

https://docs.aws.amazon.com/redshift/latest/dg/copy-usage_notes-copy-from-json.html

Looking for a video to learn about Redshift? I have one on my YT channel Introduction to Redshift

I post daily about programming. You can find me 👇

Youtube | Twitter | Instagram

Let’s learn together 💪💪

Happy Coding 💻

Setup Java development environment and create your first program with IntelliJ

Awdesh — Fri, 26 Mar 2021 06:16:46 +0000

Setup JAVA development environment on your machine and start coding in JAVA.
I have worked with Java on and off for the last 6-7 years but I still had a few fundamental questions/concerns like-:

1.) Why do I need JDK to write a Java Program?
2.) Should I install JDK vs JRE?
3.) Is Java 1.8 and Java 8 the same?
4.) Where should I install Java from?

and many more.

In this video, I am discussing answers to all of the above questions plus capturing how to install IntelliJ and setup Java from scratch.

TL;DR

Summary of the video

JDK contains Java compiler, java doc, java debugger, etc. All of them are integral to code and compile a java program.

A couple of years ago JRE and JDK used to come as a separate distribution but now JRE comes with JDK. Although JRE can also be downloaded separately.

Java versioning scheme has changed after Java 8 and there is no more 1.x in the versions anymore. With each new version we get Java x and Jdk x e.g. March 2021, Java 16 got released with Jdk 16. I am covering this topic in detail in the video.

I write and record videos on various platforms about programming. These days I am writing mostly about JAVA.

You can find me at

Youtube | Twitter | Instagram

Let’s learn together 💪💪

Happy Coding 💻

reference: https://stackoverflow.com/questions/1906445/what-is-the-difference-between-jdk-and-jre

Database access in Spring.

Awdesh — Thu, 25 Mar 2021 05:40:52 +0000

JPA is a standard for ORM. It is an API layer that maps Java objects to the database tables. All you need is to annotate your Domain object with @Entity.

In Spring Boot, Spring Data JPA brings the goodness of Spring Data and JPA together.

In the JDBC world we have to embed sql queries inside the codebase to access the database, JPA hides all that complexity by providing many CRUD related methods via JpaRepository.

Let's take a look

Above code is mapping User Object to User table in the database. User table consists two columns "first_name" and "last_name". @Column annotation is defining the column inside the User table.

JPA supports many annotations e.g. @Table annotation can define the indexes on the table. Take a look at the sample code below.

Above we are creating an index name “name_index” on the first_name column.

Data access layer without JPA:

JDBC is the prominent method to access the database. JDBC requires one to write sql queries to communicate with the database, it makes use of Statement, ResultSet etc. to prepare a sql statement and gets the result out of database respectively.

Let's take a look below-:

Statement stmt = conn.createStatement();
ResultSet rs = stmt.executeQuery("SELECT first_name FROM Customers WHERE last_name = 'Doe'");

Here we create a statement object and call executeQuery on it with supplying the SQL query. ResultSet object will contain all the returned result from the query. We can now use an iterator to iterate over items inside result set.

Similarly an insert statement could look like this.

Statement stmt = connection.createStatement();
stmt.execute("INSERT INTO user (FIRST_NAME,LAST_NAME) VALUES (1,'John','Dow')");

Data access layer with JPA

Let's see how JPA does above two database operations.

Spring Data Jpa expose JpaRepository which is comprises on all the CRUD methods. Once we define a repository for the domain object we are ready to call these methods.

Let's create a repository interface for User.

@Repository annotation tells Spring Boot to scan interface and make it available at startup. You'll notice that we haven't create any method inside our interface because we don't need to, atleast for the simple CRUD use cases.
All those operations are supported by JpaRepository out of the box and we are extending it.

Now let's compare same select and insert operation of Jdbc here in Jpa.

Like Select if we have to retrieve all the objects we can do

User user = userRepository.findAll();

Like Insert if we have to insert a user we can do

userRepository.save(user);

Much simpler than the JDBC implementation.

Let's take a look at another example.

Finding all the users with the given first name.

Use “findBy” to search on a particular column.

// find rows by the first name.
userRepository.findByFirstName(String firstName);

Similarly,

// find rows by the last name.
userRepository.findByLastName(String lastName);

I'll stop here for this post. In the next post I'll write how to handle more complex sql queries using JPA.

If you like to walk through video tutorial rather I have a Spring Boot playlist on YouTube 👉 Spring Boot Tutorial Series

I post daily about programming on different platforms with the intention of writing good tech content and keep them less spammy.

You can also find me 👇

Youtube | Twitter | Instagram

Let’s learn together 💪💪

Happy Coding 💻

Quick walk through of creating an API with Spring Boot.

Awdesh — Wed, 24 Mar 2021 00:10:28 +0000

In this post, I am discussing how we can create a simple API with Spring Boot. This post discusses about Repository, Controller/Resource and Model layer.

Let's get to it. 🚀

Prerequisite: Make sure you have Java 11 and maven installed.

Head over to start.spring.io from your favourite browser and create a starter project. Add these three dependency from the Add Dependency tab on right pane.

JPA : JAVA Persistence API. Provides lot of methods to interact with database.
H2 : In memory relational database.
Spring Web : Uses Apache Tomcat as default embedded container.

Click on Generate at the bottom to download the zipped folder. Extract it and open it in IntelliJ or any other favourite editor of your choice.

Your pom.xml with dependencies should look like below.

Just three dependencies that we added from the website. Simple and clean.

At this point we can run the service and it'll start the tomcat but it won't be very useful to us since we haven't defined any endpoints.

So let’s jump into the action and start creating classes. I'll start from bottom-up i.e. creating classes that are closer to the database and then move up to utilize those classes.

1. Model layer

The first thing I like to think about is the object that I want to store in the database. In this post I am using Video object. A video can contain a title and a description.

Let's create a class named Video.java.

Here is the quick summary of the annotations used in the class.

@id : Annotation tells that the field is a primary key.
@GeneratedValue : JPA will take care of auto generating this value for us. We don't need to manually send it with the object.
@Entity : Represents that the POJO can be persisted in the database.

2. Repository layer

Remember JPA that we added while generating the project. It exposes many methods that can be utilized to interact with the database. Methods like save(), findAll(), delete for regular CRUD operations.

No more hassle of constructing JDBC queries.👍

@Repository : Helps Spring Boot to scan the repository layer.

3. Controller/ Resource layer

Layer that expose object from data to the outside world and brings days from outside world.

In other words, it is where we define GET, POST and other REST mappings to create API endpoints.

@RestController : Signifies that the class is a controller class and contains REST endpoints.

That's it. 🎉🎉

Now you are ready to run the service. Look for the class ending with Application in your project. It should contain main method.

You can simply run the main method that will scan all the components based on the annotations that we have supplied and bootup the service.

If everything went well, you should be able to see tomcat running at port 8080. Fireup postman and go to http://localhost:8080 and GET, POST a Video object.

http://localhost:8080/h2-console will open the window to connect to in memory database. You don't need to change anything other than Jdbc_url which can be find from the logs inside the terminal window.

This is a very basic and simple implementation of creating an API with Spring Boot. There are many features of SB that comes out of the box which I will write about in the next few posts.

If you like to walk through video tutorial rather I have a Spring Boot playlist on YouTube 👉 Spring Boot Tutorial Series

I post daily about programming. You can find me 👇

Youtube | Twitter | Instagram

Let’s learn together 💪💪

Happy Coding 💻

My programmer friends, How are you drinking your coffee?

Awdesh — Sat, 11 Jul 2020 03:22:14 +0000

Coffee and software engineers match made in heaven, right? Well, that might be an overstatement but we have to agree that nothing beats a good cup of coffee to kick start your morning.

We have all read, watched, and talked about our office setup with a cool keyboard, mouse, and expensive headsets but coffee. I feel coffee deserves an article as well since it is an integral part of our dev space, at least for most of us.

I live in Coffee capital, Seattle where rain consumes most of the year. It's the coffee that helps you to get through the gloomy part of the season.

Being from an Indian background I always used to drink coffee with milk and sugar. Black Coffee isn't quite common back at home. When I started working in the US, I somehow picked up the black coffee and since then we are living happily together.

My journey with black coffee started with the basic drip coffee, you know the one that’s already brewed and boiled. Although I must admit that I always tend to put cream and sugar in my drip coffee mostly because I see cream, sugar, and cinnamon within the proximity of the drip coffee and it’s tough to resist sugar once you see it :P

From drip coffee, I moved to K-Cups, the one where you have crushed beans inside the cup which you throw in a K-cup machine. Machine poke a hole in the cup and pours the hot water through it and ”voila”, your hot cup of coffee is ready.

I remember the day 4-5 years back when after work on Friday, I rushed to Target to get a k-cup brewing machine and walked over 2 miles with rather uncomfortable to carry brewer 📦. All I wanted, coffee the next morning at home instead of going out to a nearby coffee house.

Everything has a journey and so did my K-cup brewer not because it broke but the coffee after a point was just hot brown water. Now, I was longing for a better option something fresh, like coffee beans which I can grind at home.

I decided to move on to an old-style where I can get powdered coffee and pour hot water over it to have a perfect cup of hot coffee.

The problem was: I didn’t have a coffee filter, pour-over mug, kettle, etc. and I didn’t want to spend more money especially when I am in the experimentation phase and more importantly when K-cup brewing machine is witnessing me ignoring her.

But I had a measuring cup that I can use to boil water in a microwave, a strainer that I could use to filter coffee grounds. So I started with that, zero investment other than buying a powdered filtered coffee. My technique was simple, boil the water in the microwave for 2 and half minutes, let it sit for 10 seconds, put coffee grounds on the strainer and pour the hot water over the coffee grounds, and through the strainer, you’ll have the hot cup of coffee into the mug.

Using a bare metal filter is not a good idea. For one, it doesn’t filter out all the coffee and some of the grounds can slip through it. You don’t want to taste the coffee grounds unless you are drinking the ‘Turkish coffee’. Secondly, the taste isn't great unless you use it with a paper filter.

⚠️ Another problem using the metal filter.

Unlike paper filters, metal filters are incapable of absorbing everything from the coffee grounds. Coffee contains the cafestol which is made up of a chemical compound ‘diterpenes’. Diterpenes are fundamentally an oily compound, Wikipedia says “Diterpenes is the base compound in Retinol”. No wonder all the skin creams contain retinol in them, claim to get rid of skin dryness.

Based on some more research online I found out that cafestol in your coffee can increase your LDL levels. I suffer from high LDL and have been told to stay away from oily food. Well, I didn’t know the oil was sneaking through coffee. If I am drinking a 2-3 cup of coffee daily I want to make sure I am not drinking something unwanted in it.

Is it just the problem with metal filters?

Yes, wherever we use it. Not just pour over but all other means of coffee filtering like the most popular french press which uses metal filter has the most amount of cafestol. To make the matter worse, the process of letting your coffee sit inside the french press jar increases the cafestol further.

If you drink 5 cups of french press a day it can increase your LDL levels from 6% to 8%.

I have finally switched to using the paper filter and a pour-over mug. The paper filter absorbs the diterpene, the oily compound just because of the nature of paper. The paper absorbs oil, metal doesn’t, makes sense.

Well, this is just my observation. At this point I would ask the ultimate question, How do you take your coffee?

All the images are taken from Pexels and Unsplash.

TIP: Use a pinch of salt in your coffee. Salt cuts the bitterness in the Coffee and enhances the flavor.

Money poor Time rich or vice versa

Awdesh — Thu, 20 Jun 2019 22:57:26 +0000

What kind of a job would you prefer?

Job-1 -: Working for one of the big tech company, aggressive work culture. Good base salary + bonus + stock.

Job-2 -: Working for a smaller company, not so aggressive work culture or deadlines, working from home. Ownership and decision making on projects. Competitive base, no bonus or stocks.

Summary of dev talks from the Dev conference I attended last week.

Awdesh — Wed, 05 Jun 2019 06:13:18 +0000

It’s been a while since I have posted an article. I thought this might be a nice article to share while stuff from the conference is still fresh in my memory. The conference was heavily focused on microservices, Kubernetes and cloud platforms.

I want to share some of the highlights from different sessions so to have a note for myself for the future reference :P

There were a lot of sessions around microservices. I’ll try to summarize my understanding from a lot of different talks on the same topic. The common theme of different talks was to focus on the evaluation of the need for microservices in your architecture.

Some of the things to consider before choosing microservices architecture.

Security -: Different services need to talk to each other and communicate by sending data over the network. Data in motion between services needs to be encrypted which is something you don’t need to worry in a monolith service architecture.

Network latency -: In Microservices architecture services are going to be spread around the network. Calling one service from another over the network could be slow because of network slowness.

Observability -: Adding centralized telemetry data around different services can be a challenging task.

Team dynamics -: Team dynamics can be tricky with each team working in the silo on their own small piece of service.

Versioning can be a pain -: Different microservices can have different versions based on the feature implementations. It is vital to keep track of which version is compatible with which version of other microservices.

Some interesting mentions of the tool for microservices in another talk.

Istio -: Service mesh to manage micro services.

Envoy -: Side car proxy to enable communication between services in a microservice architecture.

Mixer -: Gather telemetry data from different services.

Another talk was around going from Monolithic architecture to Microservices via mini services. I quickly wrote down the comparison chart in the talk.

Mini service architecture as I understood is an intermediate between the monolith and microservices architecture in which you neither have a bulky codebase with every possible implementation nor you go crazy by splitting every possible feature into a microservice.

In mini service, you only split features that require more work/ maintenance or whatever matrix you choose to split.

Web assembly talk

I really found this talk very interesting. I have read about web assembly before but never cared to understand it thoroughly. I found the talk to be a quick and good intro to web assembly.

Write code in different languages like C, C++, Go, Rust and have it compile into web assembly directly into the browser. The idea of web assembly is to get native desktop app performance on the browser with the same code base that you have used to write a desktop app thus bypassing rewriting the application in JavaScript.

Think about desktop games, Java applet applications running in the browser without asking the client to download runtime and without developer to port desktop app code to JavaScript.

You do not write code in web assembly rather you compile code in web assembly by using the language compilers.

Node Js 8 or higher supports web assembly.

80% of the browser supports web assembly.

Compiled web assembly is called .wasm which can be imported as an ES6 module.

Chaos Engineering was another term that I really found very interesting. Netflix uses it and the idea is to take servers offline from the architecture to see if other servers are able to take load successfully.

There was another interesting talk about Outcome driven development which focused on how to achieve efficiency within the engineering team by focusing on the outcome rather than the output.

I got introduced to Dev SecOps term in a cloud security talk. The talk was focused on using the security policies in the development environment so to not get surprised eventually when software doesn’t go through validation afterward.
Have a baseline of cloud infrastructure that can be agreed upon by Devs and Security team.

The closing talk was very informative from the director of AWS. The topic of the talk was how to create MLP (most loved product) not MVP. How we create MVP first and then keep adding features into it rather than improving MVP.

There were a lot of great insights about great UI from the work of Dieter Rams, the chief designer of Braun. His Wikipedia page talks about all the good design principles. https://en.wikipedia.org/wiki/Dieter_Rams

This is it.

Please feel free to send your feedback and comments to add further on the topics or correct me if I went wrong in some of my understanding from the talk.

My first week of learning Swift.

Awdesh — Fri, 14 Sep 2018 05:15:25 +0000

1.) Declaring constants and variables.

Variables

Constants: Once declared their value can't be changed. Swift will throw compile time error when trying to update the value.

2.) Declaring a function

Java's syntax of a regular function looks like below

3.) Class function

Like python, swift has class functions. Class functions are bound to a class rather than an instance of a class. Honestly, function followed by class in the syntax threw me off a bit when I first encountered it in the source code.

Python's syntax of a class function

4.) Using underscore `_`.

In my very short experience with Swift, I have seen the use of _ inside function calls. _ is used to define an unnamed parameter inside the function. Swift uses a name for each parameter so when we call a function we need to provide the name of the parameter.

Use of _ can bypass passing of the name altogether. Let's walk through an example-:

In general, when _ in front we can to ignore value. Another use case of _ would be something like below.

5.) Type Alias

As the name suggests, type alias allows giving aliases to existing types.

This is certainly not the best use case of using type aliases. The better use case is by aliasing closures inside the function. Functions and closures in swift have a parameter type and a return type which can be aliased.

6.) Closures

As per Apple docs

Closures are self-contained blocks of functionality that can be passed around and used in your code.

7.) `?` and `!`.

Both ? and ! is used for Optionals in swift. Use of optionals can make variable to have a value or nil.

? is used after the variable type indicate that the variable is optional.

! is used to unwrap the value of optional so to use it.

We could check for non-nil before unwrapping optional to get rid of runtime error.

As pointed out by Nuno Vieira in the comment section, force unwrapping is not a good practice rather we can use (if..let) which is called Optional binding method.

8.) Dictionary and Array

This is it for this post. Stay tuned for articles like this.

References

Offical swift tutorial from Apple-: https://docs.swift.org/swift-book/GuidedTour/GuidedTour.html
Great read about Optionals-: https://stackoverflow.com/questions/24003642/what-is-an-optional-value-in-swift

If you want me to write on a specific topic, please feel free to post them in the comment section.

You can support my work by buying me a coffee below. 💚💚💚💚💚💚 !!

Shuffling algorithms and randomization to improve algorithm‘s runtime.

Awdesh — Sat, 04 Aug 2018 09:50:26 +0000

Shuffling card is an essential part of every card game. There are many techniques for shuffling cards but overhand and riffle are the most popular ones.

Overhand shuffle

In this shuffle, a set of cards are transferred from bottom of the deck to the top of the deck and the same process gets executed recursively.

A deck of cards is essentially a fixed sized array of length 52. Overhand shuffle puts set of cards from the end of the array to the beginning of an array. This process gets repeated to get a good shuffle.

Riffle shuffle

This involves cutting the deck into 2 halves so we get two sets of cards and riffle them such that at the end both halves gets interleaved.

A quick implementation of riffle shuffle would be something like following.

There are shuffling algorithms in existence that runs faster and gives consistent results. These algorithms rely on randomization to generate a unique random number on each iteration.

As per Wikipedia

If a computer has access to purely random numbers, it is capable of generating a "perfect shuffle".

Fisher-Yates shuffle is one such algorithm for achieving a perfect shuffle using a random number generator. The algorithm is named after Ronald Fisher and Frank Yates who first described this algorithm in their book in 1938. Later Donal Knuth and Richard Durstenfeld introduced an improved version of the algorithm in 1964.

Unlike swapping items at two different indexes, algorithm generates a random number k between range of the elements inside an array. Every iteration updates the last element in the range thus random generator works on the new range on every iteration and generates a unique number every time.

Above algorithm works in linear time and faster than riffle shuffle. Putting some timing around both shuffle algorithm for an array of 100 integers produces below result.

Programming languages use a similar algorithm in their inbuilt implementation of shuffle method. Java's implementation of shuffle method could be used by invoking

collections.shuffle()

To shuffle a linked list which doesn't allow access of object by their index, Java converts it back to array first so to have random access, shuffles it and converts it back to list.

Shuffle method's implementation From Java docs

Can randomization improve the runtime of an algorithm.

A good shuffling algorithm has a function which generates a unique random number consistently. Quicksort which gives quadratic time performance on a sorted array can generate consistent O(nlogn) result by randomizing sorted array first and then fed it into quicksort algorithm.

There are two different types of randomization algorithms namely Las Vegas and Monte Carlo algorithms. IMHO, one can't get a better name than Las Vegas for a shuffling algorithm :)

Las Vegas algorithm guarantees to give result in an expense of the time complexity whereas Monte Carlo compromises guarantee of the result by exiting early if it doesn’t find the desired output. If we have to search an item inside an array Las Vegas algorithm will execute until it finds the expected item whereas Monte Carlo will execute for a couple of cycles and stops if it doesn't find the item. Rabin Karp algorithm for string searching uses Las Vegas algorithm to find all matching sub-string inside input string.

Applications

Randomized algorithms are useful in applications that require good results consistently irrespective of input to the algorithms. Software in rockets, satellites, airplane, cryptography utilizes randomization to get a high probability of good result on algorithm

Resources

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
https://www.geeksforgeeks.org/randomized-algorithms-set-2-classification-and-applications/

Images are taken from Google.

Conclusion

There is so much to learn and write about shuffling algorithms and randomization. In my next post, we'll sort back cards after shuffling them in here using inbuilt sort function in language.

If you want me to write on a specific topic, please feel free to post them in the comment section below.

You can support my work by buying me a coffee below. 💚💚💚💚💚💚 !!

Dual Pivot Quick Sort: Java’s default sorting algorithm for primitive data types.

Awdesh — Sun, 29 Jul 2018 07:00:09 +0000

What happens when we do Arrays.sort() in Java? which sorting algorithm does Java use in the background?

Since Java 7 release back in 2011, default sorting algorithm used is DualPivotQuickSort which is an enhancement over classic quicksort algorithm.

Dual pivot quicksort is a combination of insertion sort and quick sort. Insertion sort has faster runtime when the number of elements to be sorted is small, Double pivot quicksort uses this fact thus when the number of elements is <= 47 Java performs insertion sort under the hood.

When input size array is larger than 47 Java uses Double pivot quicksort. As the name suggests DualPivotQuickSort algorithm picks 2 pivots instead of 1. Unlike quicksort in which we partition the array around 1 pivot, we partition the array in three parts around 2 pivots.

1st sub array : items < LP
2nd sub array : LP <= items <= RP
3rd sub array =: items >= RP

Algorithm

LP: Left Pivot
RP: Right Pivot

1.) Left most item in an array is taken as the left pivot and Rightmost item as the right pivot.
2.) Swap Left pivot with Right Pivot if LP > RP
3.) Partition array in three sub-arrays around left and right pivot.

Once a partition is done we perform above 3 steps recursively on three sub-array.

Let’s walk through an example-:

No need to swap pivots in above image since LP < RP.
Now we partition the array following below schemes.

1st sub array : items < LP
2nd sub array : LP <= items <= RP
3rd sub array =: items >= RP

Now we have 3 sub-array over which we'll perform the same steps as above. Since the first two arrays have only 2 items, one will become left pivot and other will become right pivot. We'll swap left pivot with right pivot if the left pivot is greater than right pivot which is not the case for first two sub-arrays.

For the third sub-array as we can see in below image left pivot is greater than right pivot thus we'll swap them.

Swapping pivots.

We don't have any more elements in the array that we can partition further.

References

https://www.geeksforgeeks.org/dual-pivot-quicksort/
https://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort
http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

Conclusion
Similarly, Python uses Timsort which is a combination of insertion sort and merge sort. I’d like to read and write about different other variation of quicksort in the next few days.

If you want me to write on a specific topic, please feel free to post them in the comment section below.

You can support my work by buying me a coffee below. 💚💚💚💚💚💚 !!

Reverse a Word.

Awdesh — Wed, 25 Jul 2018 02:02:03 +0000

I wrote couple of posts previously here and here on how to find duplicates in an array and we saw different variety of that problem. I want to switch gear now to string related problems. Previous posts on arrays built a good foundation for us to solve string related problem because string is an essentially an array of characters.

We are given a word which contains only alphabetical characters. Considering string is an array of characters and one of the biggest advantage and vital key to solve certain array problems is to iterate an array from forwards and backwards at the same time.

We can use two pointers where one pointer start from beginning and other pointer move inwards from end of the array.

This information is vital to solve this problem. Let’s use that algorithm and write down code.

Could we use the same algorithm to reverse words inside a sentence? e.g. "This is a word" should change into "word a is This" by the algorithm.
If we split the string by a whitespace we'll get an array of strings and then we can use above algorithm to reverse a sentence.

Another problem where we could utilize same algorithm is to solve string palindrome problem. A word is a palindrome when it reads same from backwards as forward e.g. kayak, noon etc.

Now we know that we can traverse a string from forwards and backwards, we can use that knowledge to solve palindrome problem.

This is it for this post. I plan to write more on string related problems in my next posts.

Stay tuned. :)

Finding duplicates algorithm series- A given range of elements as an input.

Awdesh — Sun, 22 Jul 2018 05:09:15 +0000

In my previous posts in finding duplicates series here and here we have seen different variation of this problem. This is another interesting twist in the problem as now we have given input which falls in a given range.

Let's walk through an example-:

Below we are given an example where an array given contains elements that are in range 1-10.

When we have given input in a range, counting sort like algorithm is the best we can implement. More on counting sort is here

Inspired from counting sort algo, to solve this algorithm we’ll create another count array in which we store count of each item at the index i.e. at index 2 we’ll store item 2 in the count array.

Here is repl in Java.

We have learnt another variation of finding duplicate problem plus we also learnt about counting sort. In coming posts I want to work on String related problems.

Happy coding. Cheers.

DEV Community: Awdesh

Step by step guide to create an analytics application with AWS Redshift using AWS Lambda and S3

Why not use a regular RDBMS solution to run data analytics?

Connect to cluster from outside the VPC

Setup Java development environment and create your first program with IntelliJ

Database access in Spring.

Data access layer without JPA:

Data access layer with JPA

Quick walk through of creating an API with Spring Boot.

My programmer friends, How are you drinking your coffee?

⚠️ Another problem using the metal filter.

Is it just the problem with metal filters?

Money poor Time rich or vice versa

Summary of dev talks from the Dev conference I attended last week.

My first week of learning Swift.

1.) Declaring constants and variables.

2.) Declaring a function

3.) Class function

4.) Using underscore _.

5.) Type Alias

6.) Closures

7.) ? and !.

8.) Dictionary and Array

References

Shuffling algorithms and randomization to improve algorithm‘s runtime.

Can randomization improve the runtime of an algorithm.

Applications

Resources

Conclusion

Dual Pivot Quick Sort: Java’s default sorting algorithm for primitive data types.

Reverse a Word.

Finding duplicates algorithm series- A given range of elements as an input.

4.) Using underscore `_`.

7.) `?` and `!`.