A silly excuse I just invented to share with you random bits of theory from some dark corner of Computer Science and make it as beginner-friendly as possible π
Today I want to talk about *Algorithmic Complexity *.
To get started, take a look at the following code. How long do you think it will take to run it?
Let's make that question more precise. How long do you think it will take to run it in the worst-case scenario?
We can see that the code will run slower if:
π your computer is older;
π the array is longer; or
π x happens to be further to back, or not present at all.
Can we turn these insights into an actual formula? We will have to get rid of ambiguous stuff like "old computers".
1οΈβ£ First, let's consider an abstract computer in which all "atomic" operations take exactly 1 unit of time.
π€ Defining exactly what is an "atomic" operation is far from trivial. For now, assume it's things like arithmetic operations, indexing, invocation.
2οΈβ£ Second, we'll count the number of operations *with respect to* the size of an arbitrary array.
We will say something like "this will cost 2 units of time for each element of the array".
3οΈβ£ Finally, we will consider the worst-case scenario.
So we assume, in this example, that the element x is not in the array. More generally, we will always think about the maximum number of operations that could potentially happen.
With these ideas in mind, we are ready to define the *Algorithm Complexity* of this algorithm.
Let's count how many operations are performed in each step, assuming our array has length N:
Depending on how detailed you want to be counting, you could say we have something like π₯3*N+1π₯ operations in the ultimate worst-case scenario.
β Now, why do we care about this?
The reason is that we can now compare different algorithms.
For example, if your implementation takes π₯5*N+3π₯, then it is worse, right?
Well, it's not π
Here's the deal: we have been assuming that all "atomic" operations are equally costly, but this is not true...
Hence, it makes no sense to compare my implementation with your implementation by looking at those tiny differences. My 5 * N could be faster than your 3 * N if my "atomic" operations are simpler.
π‘ We want a complexity measure that smooths away all implementation details.
To achieve this, we will take away everything unimportant when N becomes very large. We will consider that:
π N+a and N+b are the same;
π a*N and b*N are the same;
... for any finite values a and b.
π And instead of saying 3*N+4, we will say the asymptotic algorithmic complexity is O(N).
This is called big-O notation.
π‘ We call this *linear complexity* because the number of operations grows linearly *with respect to* the size of the array.
π§ Formally, it means that your function's cost is something that is bounded by a linear function.
π‘ Intuitively, what this means is that in the long run, small differences like specific operations matter less than the capacity your algorithm has to *scale* with more data.
The reason is simple, an algorithm with a lower asymptotic complexity will eventually win. Take for example binary search.
It takes a bit of thinking, but we can prove the asymptotic notation to be O(log N).
Binary search is doing much more work in each iteration than linear search. It could be 20 * log N vs 3 * N. Hence, with very small arrays, linear search could be better.
π But there is always a value of N after which binary search will win, and in any hardware.
β€οΈ And that's it. We have just arrived at the intuitive notion of asymptotic complexity!
Calculating it can be daunting for some non-trivial algorithms, but here are some tips for estimating it:
1οΈβ£ Every nested for loop from beginning to end usually means another exponent.
For example, two nested loops usually mean O(N^2), three nested loops, O(N^3), and four nested loops means you really need to take a break and, afterwards, please refactor that code.
2οΈβ£ An invocation to function F inside a loop means you have to multiply N times the complexity of F.
For example, if we call binary search for each element of the array, the resulting algorithm is O(N log N)
3οΈβ£ In recursive methods, if you split at the middle and recurse down only one branch, that's O(log N). If you recurse down both branches, you usually have O(N log N).
These are special cases of a more general rule for recursive methods:
There seems to be a recent surge in the "HTML is/isn't a programming language" discussion.
While there are a lot of honest misconceptions and also outright bullshit, I still think if we allow for some nuance there is a meaningful discussion to have about it.
My two cents π
First, to be bluntly clear, if a person is using this argument to make a judgment of character, to imply that someone is lesser because of their knowledge (or lack of) about HTML or other skills of any nature, then that person is an asshole.
With that out the way...
Why is this discussion meaningful at all?
If you are newcomer to the dev world and you have some misconceptions about it, you can find yourself getting into compromises you're not yet ready for, or letting go options you could take.
One of the very interesting questions that really got me thinking yesterday (they all did to an important degree) was from @Jeande_d regarding how to balance between learning foundational/transferable skills vs focusing on specific tools.
@Jeande_d My reasoning was that one should try hard not to learn too much of a tool, because any tool will eventually disappear. But tools are crucial to be productive, so one should still learn enough to really take advantage of the unique features of that tool.
@Jeande_d One way I think you can try to hit that sweet spot is practice some sort of dropout regularization on your common tool set.
In every new project, substitute one of your usual tools for some convenient alternative. It will make you a bit less productive, to be sure...
β Today, I want to start discussing the different types of Machine Learning flavors we can find.
This is a very high-level overview. In later threads, we'll dive deeper into each paradigm... ππ§΅
Last time we talked about how Machine Learning works.
Basically, it's about having some source of experience E for solving a given task T, that allows us to find a program P which is (hopefully) optimal w.r.t. some metric M.
According to the nature of that experience, we can define different formulations, or flavors, of the learning process.
A useful distinction is whether we have an explicit goal or desired output, which gives rise to the definitions of 1οΈβ£ Supervised and 2οΈβ£ Unsupervised Learning π
A big problem with social and political sciences is that they *look* so intuitive and approachable that literally everyone has an opinion.
If I say "this is how quantum entanglement works" almost no one will dare to reply.
But if I say "this is how content moderation works"...
And the thing is, there is huge amount of actual, solid science on almost any socially relevant topic, and most of us are as uninformed in that as we are on any dark corner of particle physics.
We just believe we can have an opinion, because the topic seems less objective.
So we are paying a huge disrespect to social scientists, who have to deal every day with the false notion that what they have been researching for years is something that anyone, thinking for maybe five minutes, can weigh in. This is of course nonsense.