I’m personally convinced that computer science has a lot in common with physics. Both are about how the world works at a rather fundamental level. The difference, of course, is that while in physics you’re supposed to figure out how the world is made up, in computer science you create the world. Within the confines of the computer, you’re the creator. You get to ultimately control everything that happens.
Linus Torvalds, The Beauty of Programming
Programming, or software engineering, as a profession is relatively young in the grand scheme of things. I’m reminded of a quote I saw once that I haven’t been able to find the source of that said essentially ‘when civil engineering was as young a profession as software engineering is, they hadn’t even discovered the right triangle’. Sure, maybe it isn’t completely an apples to apples comparison, but we’re clearly still in a highly experimental phase with people trying many different things and strong disagreements in every direction. This is a feature not a bug.
Hash Tables
In fact, hash tables are so efficient that they can, at times, seem like magic. Think of the Babel fish in the Hitchhiker’s Guide to the Galaxy trilogy—something so impossibly useful that it really has no business existing in the first place.
Conrad Barski, Land of Lisp
I came across this post over the weekend and it reminded me of something I realized a few years ago about a certain class of engineering interview questions. Every once in a while some pattern, tool, or technique gets discovered that solves huge swathes of problems that you run into while programming and it becomes so important that people start using it to assess where candidates are in their development.
A lot of times during engineering interviews you get faced with an optimization problem. Maybe the initial, naive implementation runs in polynomial time, you optimize a bit more and you get it to linear time, and the interviewer asks you if you can solve it in constant time. I’ve found more often than not this is code for “how would you implement this with a hash table?”. Which as it turns out is also a great question to ask yourself when you’re struggling with a programming problem!
Yes, hash tables’ constant time lookup is impossibly useful, so useful that for a while it made a lot of sense to make sure any new hires were comfortable with them. Even more evidence for how useful they are is that languages now have them built in to the language with special syntax to make it easy to use them. Javascript can even be thought of as a language that essentially asks “what if everything is a hash?”
Map
Another example of an incredibly useful discovery is the map function (and really any of the other collection operations like reduce, filter, etc). Frequently while programming you’ll find yourself doing or wanting something equivalent to this:
function addOneToEvery(listOfNumbers) {
for(var i = 0; i < listOfNumbers.length; i++) {
listOfNumbers[i] += 1;
}
return listOfNumbers;
}You find yourself with a bunch of things and you want to do something to each of them. Early on in programming you probably even come up with the above pattern basically on your own without really planning for it. What Map does is essentially the same thing, but returns a new, modified array after the operations are complete. Check out the implementation in underscore.js:
function map(obj, iteratee, context) {
iteratee = cb(iteratee, context);
var _keys = !isArrayLike(obj) && keys(obj),
length = (_keys || obj).length,
results = Array(length);
for (var index = 0; index < length; index++) {
var currentKey = _keys ? _keys[index] : index;
results[index] = iteratee(obj[currentKey], currentKey, obj);
}
return results;
}It is a little more complicated to make it more generic for any use case, but now that you have that function, you really only need to take the data you have and tell map what operation you want to run on each of the items and map spits out a new list of items for you.
Once you become comfortable with using it, a world of possibilities opens up for you. Problems that previously seemed hard or time consuming become trivial. In a similar way to the question you ask yourself about hash tables, you can also challenge yourself and ask "how would I solve this if I had to use Map here?"
Creating The World
If all you have is a hammer, everything looks like a nail
Maslow's Hammer
Which brings me to the way I understand what Linus is talking about when he says "...in computer science you create the world". In programming, nearly nothing is set in stone, and really the only limitation is your own creativity. As you learn to intuitively use more tools like Hash Tables and Map (and of course many others), you find they have the amazing property of being able to just cleanly solve your problem.
One mental barrier I had early on was that during the course of programming when you run into a problem you were on a linear path toward solving it and that was the state of the world. But that isn't the case. As you uncover more of the problem you're trying to solve, all code and data structures leading up to that point are also candidates for change. Once you have a hammer like a Hash Table or Map or any of the many others out there, you can just decide to turn your problem into a nail and it becomes trivial to solve.