How to Solve Iterable Problems in Python
I would like to start this blog with a problem I need you to solve before you continue reading. Assume we have a list of consecutive integer numbers and it is sorted, and we want to find the sum of that list. How would you solve it? Note that we need the optimal solution in terms of “speed”.
Everyone with different background would tackle such problems like this in their way. Sometimes no matter what is the way they solve the problem but when you have limited time, resources, labor, etc the way the problem is solved has a significant role if the final solution is correct or not. You wouldn’t stumble on an article like this unless you try to find the better solution to your problem using programming as a tool either for college assignments or a task in the workplace. And here is a piece of advice to myself before anyone else to improve my problem skills.
Now let’s start solving the problem.
Let’s declare our sorted list:
# Declare my list which is from 1 - 1000
my_sorted_list = range(1, 1001)Like most of us, we would directly think of a solution with a “for loop” especially if we are at the begging of our journey in programming.
Simple Solution:
On my machine, it took 0:00:00.001154 to get the results. It is definitely nothing we could notice right?! Right, but imagine if the list that we have is 100k times bigger than we already have?! We calculated it and it turns out it took 0:00:08.774443 to get the results.
Other people might tell you just use the built-in function in python or any other lang to calculate the sum! Built-in functions are usually optimized to such problems as iterables. Always think of “do they implement a built-in function for my problem?” This could be extended to more complicated problems such as “sorting”.
Built-in function solution:
The code looks so clean, and it is faster it took 0:00:00.000110 to calculate the sum of the number from 1 to 1000. Even if we expand the list to be 100k times bigger than the original one the time it took to calculate is equal to 0:00:00.165064.
If you have been exposed to machine learning problems you definitely have been using NumPy. For the ones who don’t know what is NumPy, it is a python library that provides a multidimensional array object and a collection of routines for fast operations on arrays, including mathematical, logical, sorting, linear algebra, statistical operations, and much more.
NumPy Solution:
Surprise it actually slower than the built-in function. Took 0:00:00.000125 and that does not include the converting step. Hence, build your code from the start with what is optimal because if we declared a NumPy array with not only 1000 elements instead of 10000000 and that's is 100k times bigger than the original one.
It finished with less than 0.01 seconds! (0:00:00.009971 to be precise). A question might raise now, why NumPy is better? NumPy runs in “the background” C code and that is generally faster than python but besides that, it uses vectorization. Ok, the short answer to what is vectorization? is not using loops, alternately they implement everything using vectors so it can use array operations instead. If you have the chance to use NumPy please do! not for the sake of speed also, for space.
Before I close the NumPy part, this is how long it takes to convert a python list of 10000000 elementals 0:00:01.989980 so please structure your code from the start to use NumPy or the overhead time to convert will probably be the bottleneck to improve the code.
Wait a minute! Don’t they always say “A problem well stated is a problem half solved”. So let’s go back to the problem for a minute, the question started with an assumption that says we have a sorted list of integer numbers. and if we want to represent that in a mathematical formula it would be something like this:
Α = {𝕞, 𝕞+1, ..., 𝕞-𝕟, 𝕟} : 𝕞,𝕟 → ℕSince the question mentioned the list is sorted so assuming m≤n.
The second part of the question says we want to find the sum of that list.
Now we should know the answer ahead of time! By using our math knowledge. This is how we formulate the problem:
Math Solution:
This solution took only 0:00:00.000109. Compared to all other solutions it might not “outperform” them on a small scale (i.e., 1000 elements). However, this would be optimal for any scale, and it would take the same amount of time with a massive list size. For a list of length equals 1 Billion elements to took only 0:00:00.000153.
Overall, these numbers perhaps are not accurate, and it differs from one machine to another. Regardless of the results, what I want is to focus on now the conclusion of this blog.
Conclusion
Finally, this problem does not seem like a real-world problem. Nonetheless, I would not write this blog if I did not face a problem like this in the workplace. Finding the best solution would demand A LOT of research and refining the problem. Research requires an excellent definition of a problem so the best problem-solving (as mentioned at the beginning of the blog as an essential skill) effort can succeed. On the other hand, you are likely not the first trying to solve the problem, that is why it is very important to know what other people have done to solve your problem. In addition, it is perfectly ok to start with other people’s solutions as a starting point. And there is no one universal way to a problem, and indeed the way you solve a problem has to meet your requirements.
If I had an hour to solve a problem I’d spend 55 minutes thinking about the problem and 5 minutes thinking about solutions. — Albert Einstein.
