Forem: Sishaar Rao

[AskDev] How do You get Started?

Sishaar Rao — Fri, 25 May 2018 20:08:46 +0000

As of today, I'm completing my first week of a summer internship, and I've spent ~90% of my time just getting "set up". This means installing personal and company dev tools, understanding relevant codebases, and most importantly, troubleshooting when setup isn't working.

It's been pretty difficult, and I'm sure there's ways to improve my experience.

What are some things you suggest someone do when joining a new company, a new team, or even a new project?

Sleep Sort: Where Theory meets Sobering Reality

Sishaar Rao — Sat, 28 Oct 2017 18:38:02 +0000

Circa 6 years ago, an anonymous user posted on 4Chan:

He outlined this amazing undiscovered sort written in Shell which, sure enough, worked. Check out my repo to download the code and try it yourself!

I'll admit, I was bewildered at first. I could envision how this algorithm could be refined and implemented, whether it be cutting the time needed to output the value or scaling datasets accordingly. But then I thought to myself if this sort (which off the top of my heads looks like an O(n) runtime) really works, then why hasn't some genius at IBM/Sun/Oracle implemented this already? I couldn't be the first one wondering how to implement this. Why did people before me not go ahead with it? Why don't we use this in real life?

Because at the end of the day, computers are still machines. At the end of the day, Theory is Theory, and Reality will always still be Reality

How/Why does Sleep-Sort Work?

The code for Sleep-Sort is as follows:

#!/usr/bin/env bash

sort() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    sort "$1" &
    shift
done
wait

Let's dissect this part by part. (In case you were wondering, #!/usr/bin/env bash is called the Shebang.)

The function

sort() {
    sleep "$1"
    echo "$1"
}

This function is going to be called repeatedly by the code. It takes its first argument (denoted by "$1") and sleeps for that amount of time. Sleep is a command that pauses its current process (or more importantly its thread) for the given amount of seconds. For example, sleep 100 would mean that the process "sleeps" or pauses for 100 seconds.
It then calls echo on the first argument, which prints out the argument. Thus, the code sort 3 would first sleep for 3 seconds and then print out 3.

The while-loop

while [ -n "$1" ]
do
    sort "$1" &
    shift
done
wait

The while-loop's condition is [ -n "$1" ] As you can observe, we use the -n flag with the first argument. This flag returns true if the argument is nonzero. Thus, this loop will iterate until the argument at $1 is null.

We then call sort on the first argument sort "$1" The most important part of this, however, is the ampersand (&) at the end What this ampersand at the end does is begin the process described in the line, namely the sort function call, in a different thread. Check this out for more info.

On the next line, we call the built-in function shift. Since there are no parameters for the function, the default value to shift is 1. What shift does is it shifts the arguments we have over. The argument in $2 goes to $1, the argument in $3 goes to $2 and so on. The original first argument is subsequently lost.

Running the code

As you now from the code above, we take the first argument and instantiate a separate thread that's sleeping for that argument length. Once it awakens, it prints out it's value. The 1 sleeps for 1 second, the 2 sleeps for 2 seconds, the 5 sleeps for 5, etc. Since the lower values sleep less, they print out their values earlier, and thus the list is now sorted. Isn't it amazing?

Why Sleep-Sort Fails

Intuition told me that there's some fundamental flaw in this sort, and that for large datasets it breaks down. The success of sleep-sort relies on 3 fundamental assumptions, which often don't hold true as we go beyond a set of 5 or 10 numbers.

1. The Processor can instantly determine which sub-process is the "least"

To generalize, the processor inherently possesses some data structure in which it stores sub-processes. It could be a Tree, a Heap, or some other data structure that allows the Processor to efficiently traverse its elements and find which one has the "least" value. By finding the least value, we mean finding which process should be executed next.

On the scale of milliseconds, sleep-sort can break down here. If we're given values 3 and 3.00001, the processor may determine the wrong process as the "least" value, simply because it takes the processor time, no matter how small, to find the correct process.

2. How Many Threads does the Computer Have?

Sleep-Sort depends on being able to separate each value into a different thread, and therefore it assumes that for n elements, you subsequently have n available threads. When you go into element sets of higher orders of magnitude, this assumption simply won't hold. Your computer has a finite amount of threads, and if you exceed that, then Sleep-Sort will fail.

3. The Processor can rapidly switch between processes

Think of your processor as a miniscule ticker. When it executes multiple tasks in parallel, in reality our metaphorical ticker is rapidly switching back and forth between our tasks. It executes Task A for a millisecond, then Task B for a millisecond, and then back to Task A. It does this switching on such a small scale that, to the human eye, it seems that the two are running in parallel.

When you have a high number of tasks, this ticker begins to break down. As pointed in Issue #1, it struggles to determine which task to approach next, and it also may get bogged down by the task it is currently at. If it loses its efficiency to switch back and forth between tasks, Sleep-sort begins to break down as the tasks won't be perfectly executed in order.

What does Sleep-Sort Teach Us

Scalability is an issue every software engineer has to keep in the back of their mind when they build a system. Often, the best products are the ones who consider scalability from the very start.

What Sleep-Sort offered me, and what I hope it gave you, is a sobering reminder that what we believe works in a theoretical world may not work in a physical one. This statement seems obvious, but many create products that assume ideal situations and fail to account for scenarios where certain assumptions don't hold true.

We need to take a step back and understand to the core how our system works. Furthermore, when we scale our solutions up for larger or different data sets, we need to understand how functionality is affected when we do so. The only way to gain this insight is to acknowledge the limitations of your environment, and the limitations of your machine.

At the end of the day, your machine is still comprised of moving mechanical parts. Design your systems accordingly.

I hope this article was helpful in understanding Sleep-Sort. Check out my Sleep-Sort repo if you'd like to try/explore the sort for yourself! Above all, if you feel like I made any factual errors or if there's anything I can clarify/expand/modify to improve this post, please comment or reach out to me!

Demystifying the PageRank Algorithm

Sishaar Rao — Sat, 13 May 2017 19:38:39 +0000

PageRank is arguably the most widely-utilized and influential algorithm in our modern day - chances are you use it tens of times every single day. In this article, I hope to explain not only what PageRank is and how it became so influential but also the Matrix/Linear Algebra that powers it. I created a simple Python+Shell demo that you can check out to see PageRank in live action!

The Stone Ages of the Internet -- How Search Engines were born

Once upon a time, you had to know the address of a webpage if you wanted to visit it. Could you imagine how frustrating that would be? You could pretty much only find new websites by word of mouth.

But then Archie said "Let there be the world's first search engine."

How did these work? Well the world's first search engines more or less followed the same process:
1) Crawling: Getting a list of domain names/information:
The tool that consolidated all website data to be later searched became known as a webcrawler. This guy will find every site and then peruse the links on the page to get a complete look at what is really in it.
2) Indexing: Searching through (usually grepping) and finding relevant information:
This process searches through all the pages that the web crawler found and will return to you pages that match the search query. For example, if your query is "cat" the web crawler will get you every single web page, which the indexer will parse through to return pages with the keyword "cat" on it

Pros of these early search engines

The internet was a lot more accessible and useful to ordinary people. They could now find new information from websites they'd never known of before. Thus, the growth and usage of the internet exploded.

Cons of these early search engines

It sucked at finding what you wanted. The indexer would simply return whatever pages contained the query. The query "cat" could return you the web page for Caterpillar. You'd have to click through multiple links to find what you wanted.

Why does Everybody know Google?

In 1996, two Ph.D. students at Stanford named Larry Page and Sergey Brin wanted to create a Search Engine that could provide users with relevant results to queries. They went on to devise the PageRank algorithm which accomplished precisely this. Their search engine, originally dubbed BackRub, took off in popularity because for some reason it would find you exactly what you were searching for. They accomplished this by not only creating a search engine with the web crawler and indexer components but with the PageRank as a third step to sift through results and find the most relevant. The rest is history.

So what is the PageRank algorithm?

The PageRank algorithm: given a network of sites with links pointing to each other, determine the significance of each site
What do we mean by a network of sites? Something along the following:

In this example (which is utilized by the demo I created) we can see that Page 1 has links to Page 2 & 4, Page 2 has links to Page 1, 4, & 3, etc.

The main question however is - How can we determine "Significance"? How do we know which page is relevant to the query? When I first thought of this problem, I came up with a few approaches. Here's why they're wrong:

Approach 1: Use Artificial Intelligence to analyze text in the query and Webpage

Why this can't work: While this may be practical for a page or two, it's simply too costly. With over a billion pages, it'll take too long to determine the significance of every page given a query.

Approach 2: Simply Count the Number of Occurrences of a Keyword

Why this can't work: The most relevant pages aren't always the ones that mention the query the most. Irrelevant sites can easily boost their traffic by pasting the word on their page a million times. When I search "shoes", I want to see Nike, Adidas, and New Balance.

The Approach used by PageRank: Count the Number of Links pointing to that Webpage

The more the website is cited by others in the network, the more likely it's important. We can think of this as a "democratic voting" system. The key to this system is that every page gets one vote that is weighted by its significance

The Technical Details + Linear Algebra Basis

Given a page in the network, we will count how many links to other pages the current page possesses. We will then take the inverse of this number to get the portion of the current page's weighted vote delegated to each of those other pages. Let's take a network of 4 pages with links that look like this:

We can express the significances of each page with a system of equations where Xn is Page n. Page 1 has links from Page 3 & 4 (aka Page 3 has a link to Page 1, Page 4 also has a link to Page 1). Since Page 3 is pointing to only one page, it's casting its entire vote for Page 1. Since Page 4 is pointing to two pages, it's casting half a vote for Page 1. We proceed with this process for the rest of the pages in the network to create the system of equations:

We could go ahead and brute-force our way through this SOE but ain't nobody got time fo' that. If we look carefully, we can observe that all the variables in this system are defined in relation to each other: namely, Xn is given some value in relation to different values of n, and those different values of n may be defined in relation to the original value of n. Thus, we can express this system of equations in matrix form Ax = x. The matrix A is going to be populated with our coefficients from the system, and the matrix X is going to be populated with the coefficients X1, X2, X3, X4.

Note: All the columns in matrix A add up to 1 because each Page can cast a total of one vote whereas the rows are the sums of the weighted votes that each Page receives. Also, the "T" superscript indicated transposed, in that the matrix X is a 4x1 rather than a 1x4 matrix.

So now we have transformed the system of equations to a system of matrices. How does help us find the solution (namely the x matrix) for the system? This is where Eigenvalues & Eigenvectors come in.

A brief overview of Eigenvalues & Eigenvectors

Eigenvectors are special instances of vectors that, when multiplied by a transformation matrix (in our case the matrix is A), the vector does not change its direction. It can change in scale, however, the factor by which we call the Eigenvalue. These special-case scenarios can be expressed by the equation Ax = Î»x where Î» is our eigenvalue and x is the eigenvector. Note: Vector, in this case, is another name for the matrix.

In our system Ax = x we say Hey! The solution matrix X is an eigenvector for the system -- namely, it's the eigenvector when the eigenvalue (Î») is equal to 1!!!
We can then do the following steps which are characteristic of solving for an eigenvector:
1) Ax = Î»x
2) Ax - Î»x = 0
3) (A - Î»I)x = 0 <-- where I is the Identity matrix

From here, we can use row reduction to solve for our matrix x, when Î» = 1. In this particular instance, we get the following as our solution matrix x:

As we can see, we find that Page 1 is our most relevant ranking. This may seem counterintuitive given that Page 3 has the more links pointing to it, but remember, the votes are based on weighted significance.

The Genius of Google

Learning how the PageRank algorithm works should leave everyone awestruck. The scale at which they employ PageRank is exponentially larger than the example I provided. Never mind the fact that they handle millions of queries every day in a fraction of a second.

The Genius behind Google is that they employed Mathematical principles to provide a solution to a problem everybody was facing at the time. Going forward, when I look at the work I'm doing, it helps me to take a step back and think: What am I trying to solve? What am I trying to accomplish? How does my work provide value to people? This algorithm is an ode to that mindset, and I genuinely believe that if you work in this manner, regardless of your field, you'll find success.

I hope this article was helpful in understanding the PageRank algorithm. Check out the Python+Shell demo I created! Above all, if you feel like I made any factual errors or if there's anything I can clarify/expand/modify to improve this post, please comment or reach out to me!

The 3 Stages of Beauty in Emacs (from a 17 year old’s perspective)

Sishaar Rao — Thu, 27 Apr 2017 15:58:41 +0000

In a mostly overlooked corner of my school lies an antiquated yet working Apple II, in full glory. I decided one day to login only to find some odd IDE running on the terminal - I soon found out it was an Emacs instance. I’d heard this name before. Where was it? Oh yea! In the Social Network!

Circa 6 months ago when I was about to make this switch, Atom was my IDE of choice. It was decent and it got the job done, so what else could I want? When I heard about Emacs, I did some research and found that there seemed to be a rivalry between Emacs power-users and the more mainstream Vim-ers.

In the spirit of teenage rebellion, I cast away Ol’ Reliable Atom and shunned the mainstream Vim in favor for Emacs, my new idol to learn and utilize completely. I used this textbook to pick up some commands as well as the official GNU Emacs manual and the uber-helpful Emacswiki. And so began my 3-stage journey of learning this command-line based editor completely from scratch.

Stage 1: This SUCKS. Do people seriously use this?

The absolute first thing I had to learn with Emacs is how to move around. How do you move the cursor Forward? Backward? Up? Down? What the hell.C-x f for forward? C-x b for backward? It’s neat that the letters match up with the word, but how could anything possibly be more intuitive than the arrows? Or pointing and clicking?! This can’t disrupt my workflow: I haven’t even been able to start working because of how complicated this is!

Navigation in Emacs as newbie was probably the steepest part of the Emacs learning curve, so if anyone is out there learning or may have given up — keep practicing, it gets better I promise.

Just kidding, it gets even harder before it gets any easier. I learned about the all-important key-bindings, often by accidentally clicking some key while trying to navigate. Whoops, accidentally clicked C-s — oh wait, what’s Iterative-Search? That’s kinda neat. I learned how to open and save files, how to switch buffers, and how to shut down Emacs (believe it or not it took me a while to figure this one out, I would just shut down my Terminal app)

Stage 2: God Bless Eshell

I saw an instant jump in productivity when I discovered Eshell. (Check out this website for a general overview) Possessing a shell in an alternate buffer meant I could quickly hop around from working and writing code to testing it and modifying file structure. With a fully functional Shell at my side, I bypassed the tedious task of coding in an IDE, switching to my Terminal to run it, and switching back to modify code. When I became comfortable with Eshell, I began to notice that my productivity in Emacs was rising.

Stage 3: Hey, That’s Kinda Neat!

Emacs has some really cool features that boosted my productivity as well, so I’ll give them a special shoutout.

Macros

Macros allow you to chain a number of commands into one command. For example, if for a block of code you want to delete the first and last five characters of every other line, you can string together these commands and make it a macro, allowing you to complete such a task within a matter of seconds.

Key-Binding Customization

Emacs allows you to bind new commands to characters for the entire system. For example, I found this helpful Stackoverflow answer and followed the second answer to create a key binding that allows me to easily clear my Eshell screen! Key-Bindings are written in Emacs’ native language Lisp, so if you know the language you can create your own bindings to customize and improve your workflow!

Splitting Windows

Believe it or not, this feature took me some time to discover, but Emacs’ ability to split windows cleanly meant I could switch between and work on different files at a much faster pace than ever before. No longer was I stuck in the (now frustrating) process of switching tabs or windows. My workflow now looked something like this:

In Conclusion

I’d still say I’m a novice when it comes to Emacs. There are some power-users out there that use Emacs’ immense capabilities to its fullest extent, and I’m nowhere close to them. That being said, I’ve been using Emacs for about a year now and I hope that my experience outlined here could prove valuable to anybody thinking about switching or learning this environment. I often find myself using Emacs navigation commands in Google Docs and Gmail and all sorts of places (amazingly, they work!) so it’s safe to say that I’m not leaving Emacs anytime soon.

I may have made some factual errors here and there, so please comment if you spotted something!
Know any other cool features that I didn’t mention? Please comment those too! Thanks!

Hey! I'm Sishaar Rao!

Sishaar Rao — Wed, 29 Mar 2017 00:25:03 +0000

I have been coding for 4 years.

You can find me on Twitter as @Sishaar

I live in Ashburn, Virginia.

I mostly program in these languages: Python, Java, Shell, HTML/Javascript.

I am currently learning more about Swift.

Reach out to me by email: sishaar@gmail.com