1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
+++
author = "Kumar Damani"
title = "Romanticism in Programming"
date = "2022-11-29"
draft = true
description = "How programming is romantic."
tags = [
"personal"
]
+++
Why there is art in programming.
<!--more-->
During the early days as a CS student we were learning about loops,
and saw "Hello World!" getting printed out to the console N-thousands of times
in just 3 functional lines of code.
for 1 to 1000:
print "Hello World!"
This felt like having the Elder Wand at the time.
But there was more to our lesson.
The TA then asks us to put our newly found power to use by computing the
sum of 1 to 100. Of course, it was a natural application of our topic:
sum = 0
for i in 1 to 100:
sum = sum + i
Sure enough we saw the answer 5050 in the console.
But then the TA reminds us that we are making our computers work too hard.
It needs to do 100 basic ADD instructions in order to make this computation happen.
What if it the number was a million? How well would our method scale?
Well then it would take a million basic ADD instructions.
Seems like this scales with "linearly" with the input size.
Later we would formalize this to O(n).
The TA hinted that there is a better way, and that we already know of the better way in math.
sum = n(n+1)/2
With this we are no longer using loops, but a known mathematical fact about sequences.
This one-liner solves our problem with 3 basic (ADD, MULTIPLY, DIVIDE) instructions.
It does not depend on the size of the input like our previous solution, thus
no matter the input, it always takes 3 instructions to compute!
This is a HUGE win!
Later we would formalize this to O(1), or "constant" scaling.
> IRL the complier would optimize the loop solution such that it does not take N instructions
but for the purposes of learning we were not allowed to depend on that.
Looking back at it now,
Both solutions are equally correct, and modern compilers would optimize the first solution
in the final instructions such that any performance differences would be negligible.
Objectively, the first solution is more readable, and friendly to a new observer than the second.
Yet I am still so drawn to the second solution.
The first solution reminds me of the saying "to a hammer, eveything looks like a nail".
Its a brute force approach.
In comparison, with the second solution, using the exact tool for our particular problem
somehow feels personalized and even "romantic".
Most often in programming, we don't have such clear optimizations. It often comes down to
using the correct data-structures for the correct situation, and elegance emerges as a result.
|
