Many software developers resent competitive programming, or in general, algorithms and data structures. Competitive programmers, on the other hand, are perplexed by the real world use of data structures, and find it monotonous.
Here I try to explain with a simple real world illustration, that unlike what most people believe, the two programming paradigms are closely intertwined.
For a more detailed explanation, you can refer this blog: https://www.sohamkamani.com/blog/2016/03/14/wrapping-your-head-around-async-programming/
Callback hell is normally caused when you want the results of one asynchronous method in another one repeatedly. This is often a very big problem faced by js developers.
auto. According to the documentation, the function is explained as:
Determines the best order for running the AsyncFunctions in tasks, based on their requirements. Each function can optionally depend on other functions being completed first, and each function is run as soon as its requirements are satisfied.
I’ll explain in detail. Suppose you have many functions. Some of these functions need the results of some other functions to run. When you have many such functions and dependencies, determining the order of execution can be a bit tricky.
async.auto is used to solve this problem. Here is a simple code for explanation:
make_folder do not need any result so they don’t have any dependency mentioned.
write_file needs the results of
email_link needs the results of
async.auto determines the best order to run such functions, possibly in parallel, for faster execution as well as less pain for the user.
Okay, so the question now is, how is any of this connected to data structures and algorithms. Well, simple question: how would you implement
Let me put this in simpler terms: Given some tasks and their dependencies, how would you determine an order to fulfill all these dependencies or tell that there is no possible order to run the tasks?
I’ll try to explain the solution to this problem using the Graph data structure and Topological sort algorithm.
Graph and a Directed Graph
Taking the simple definition from wikipedia, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”. The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots for the nodes, joined by lines or curves for the edges.
A directed graph is a set of nodes connected with directed edges. A directed edge is just a connection between two nodes which has a sense of direction.
If we try to model our problem in terms of a graph, we can see that all the tasks can be imagined as different nodes in the graph, and dependencies as directed edges between these nodes.
The above graph is a model for the example
async.auto code written above.
Topological order of a directed graph, explained in simple terms, is a linear order of nodes such that every directed edge is facing rightwards. It’s quite clear in the image below.
So now, if we think about our original problem, it’s solution is basically to find the topological order of the graph we modeled. Why? Since dependencies are modeled as edges, we would want to find such an order of nodes, such that every dependency is satisfied i.e. every edge pointing towards a node should be rightwards.
There are plenty of algorithms to find the topological order of a directed graph. The algorithm used in the async library is Kahn’s algorithm which you can read about here: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
I hope I gave a clear understanding of importance of data structures and algorithms in software development. This was just a small example, and there exist countless similar examples to reiterate this.
If you’re interested in the actual implementation of
async.auto, then you can read it here: https://caolan.github.io/async/auto.js.html