How Algorithms Exploit Laziness[Technique Tuesdays]

How Computers reach peak performance by not doing things

Nov 16, 2022

To learn more about the newsletter, check our detailed About Page and the detailed FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

I know this title makes it seem like I’m trolling you,

But trust me. There’s a family of tricks that all involve your code doing as little as possible. Good software programs use these tricks all the time to hit performance without eating up all your computational resources. And understanding how they work is a great way to build better solutions.

But first, I have a very important question to ask you. Some readers have told me that they get overwhelmed by the daily structure of the newsletter. Others have told me that daily emails help them stay regular with their practice. I wanted to know which of these two camps aligns with your experience. Make sure you vote because what you say will determine how I proceed.

Sparknotes Highlights

Lazy Evaluation- Time to start with the OG. To quote Wikipedia, “In programming language theory, lazy evaluation, or call-by-need,[1] is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation)”. This has several benefits. Firstly, if a costly routine is called very rarely, then it won’t be run until it’s actually needed. Secondly, if you’re prototyping a small part of a system, you don’t need to build the entire system. This article is a great read about Lazy evaluation. I found their point about Dynamic Programming solutions being a kind of lazy evaluation very insightful. Drawing such parallels helps you learn better. Here is example-
```
p= function (args) #the code won't actually compute what p is here
.... 
if (p == value) #this is where the code will finally call function(args). Before this point we have not run a thing. 
```
Partial Evaluation- Imagine I gave you a complex boolean algebra statement with 1000s of predicates. Is there any way you can speed up the calculation, without going through everything? Why, yes there is!! If you had a statement like ( (A1 boolOp A2) and (A2 boolOp A4) and (Aq boolOp Ap) ….), where boolOp stands for a boolean operation. Then all you need do is find the first (Aq boolOp Ap) calculation that is false. Since this is a series of ands, just one such value has to be false for the whole statement to be false. Here’s a challenge for you- How can we use partial evaluation to catch a large statement that is true? Let me know.
Just-in-time compilation- This is a way of executing computer code that involves compilation during at run time rather than before execution. Think of video games with huge maps. If the game loaded all of the map at once, then it would put a lot of unneeded strain on the system. Instead what it will do is run only the part of the map you are on. As you’re at one level/part of the map, the other parts don’t need to be loaded.
You don’t need to load other graphics till you encounter them. Image Source
In AI- We have even seen this concept make its way to AI. Although the implementation is slightly different. These days more and more ML people have gone over to the Sparsity trend. Instead of relying on an entire neural train for a single task, the idea is to use only a small portion of it for any one task. This can lead to lower costs. Hypothetically, this allows us to use very large networks, that are capable of more powerful tasks, while also keeping costs manageable. The video below goes over my favorite of implementation of Sparsity.

Each of these techniques has its own nuance, so I will do individual breakdowns for each of them. If there’s any you really want me to cover, you know how to reach me.

I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 20% off for upto a whole year.

Get 20% off for 1 year

Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.

Special Request

This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.

There is a simple form in Substack that you can fill up for it. Here it is. Thank you.

https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform

To get your Substack URL, follow the following steps-

Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.

Click on the circled place to get your URL

You will be redirected to your URL. Please put that in to the survey. Appreciate your help.

In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs

If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.

https://forms.gle/XfTXSjnC8W2wR9qT9

I see you living the dream.

Go kill all and Stay Woke,

Devansh <3

To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below

Get 20% off for 1 year