Woke up at 3:30 and can’t get back to sleep so I guess I’ll make a post!
So earlier I made a glowing post about how I found out about line comprehension and how I was totally in love with them. WELL, THE HONEYMOON IS OVER.
Well, not really, they are totally useful and clean looking but like all things they have their place and use and I was apparently abusing them like an episode of Friends abuses the laugh track.
My learning moment here was with another Euler problem that involved using proper divisors. Specifically abundant numbers which are defined as numbers which have proper divisors that add up to greater than the actual number. For example:
12 has divisors 1, 2, 3, 4, and 6. The sum of those divisors is 16 which is greater than 12, so we call 12 ‘abundant’. These mathematicians really have a lot of time on their hands to think about things like this.
So in this particular Euler Project problem, I had to use a list of proper divisors ranging from 1 to 28124 to find out what integers between that same range could NOT be a sum of any two abundant integers. In other words: imagine you had to make anywhere between 1 and 100 dollars in change from a register, but you only had a single $1, $5, $10, $20, and $50 bill. What amounts of change in that range could you make with any two of those bills? Doing it in your head you could make $6, $11, $21, $15, $25, and $30, simple when there are a few to choose from, harder when there are hundreds if not thousands of abundant numbers in your set.
So in good form, I recycled my ‘propd’ function from the last post and went about generating the list of proper divisors. This was the snippet of code:
abnum = [x for x in range(1,28124) if sum(propd(x)) > x]
Reads as follows:
- For any integer ‘x’ from 1 to 28123 (the range function excludes the upper limit when creating a list of iterable values)
- If the sum of the proper divisors of ‘x’ returned by my beautiful propd function is greater than ‘x’ itself then save that number into my list of abundant numbers.
Simple and sweet, and it worked.
Next, I had to check each integer from 1 to 28123 to see which ones I could not “make change” with the “bills” of abundant numbers that I had just generated. This was some but not all of the code (I don’t wanna give away the answers!)
intct = [x for x in range(1,28124) if abnumsum.count(x) == 0]
This bit’s logic is this:
- For any integer ‘x’ from 1 to 28123 I will check if ‘x’ is in a list that I generated called ‘abnumsum’. (‘abnumsum’ is basically a complete list of all the sums of any two abundant numbers in the range which I generated in an unshown line of code.)
- If ‘x’ is not in that list, meaning the ‘count’ of it in the list is zero, then add that to the list of integers that can’t be the sum of two abundant numbers.
This took a while to get right, I was learning some new functions, but it worked as well. However, this was the result of timing the program:
Without finding abundant numbers operation took: 50.452989 seconds to complete.
Total operation took: 60.543015 seconds to complete.
The first line of code that I showed took about 10 seconds to complete, the second line of checking over the HUGE number of integers and the HUGE list ‘abnumsum’ took 50 seconds.
I then checked the forum and proceeded to crap myself when some people were doing in less than 60 seconds. Some even did it in less than 10 seconds! Meaning their entire operation took less time than it took me to just get my list of abundant numbers. “Crap,” I exclaimed (of course more creative language with f-bombs were used but I’m keeping it pg. Sorta.)
That meant it was time to do some learning.
First, I looked at this one programmer’s piece of code who also wrote it in Python. I rewrote their code in my own style (learning trick alert) and it is shown below:
Once again, reads as follows:
- For any integer ‘n’ that we want to generate proper divisors up to we make a list of empty lists, ‘pd’ that will hold the proper divisors for each integer up to ‘n’.
- For every integer in range from 1 to (n/2) rounded up, we do this:
a. set k = 2 (this is what we use to find multiples of the divisor, we set it to 2 because we don’t need to find the divisor itself… we already know it.
b. while we have this divisor number, we will just keep finding multiples of it and add it to the divisor list of that number, for example: divisor = 3, therefore we add it to the list of divisors for 6, 9, 12, 15, 18, … , up to possibly n rounded up. - Once we have done that for every divisor up to (n/2) rounded up we return the big list of proper divisors for each integer, ‘pd’.
My EUREKA moment was realizing the fundamental but not obvious difference between my original line of code ‘propd’ and this more efficient ‘genpropd’. My code defining ‘propd’ brute forced each integer given to it, finding every possible proper divisor using a loop. However, the elegant code above doesn’t TEST each number, it GENERATES it from scratch. So it is able to skip over a huge number of iterations. If you have the right generating algorithm you don’t need to check each integer with a number of iterations equal to that integer/2 (‘propd’ does that) which saves immense computational power.
‘propd’ is wonderful if you need to find the proper divisors of a single integer ‘n’ or a couple of them. Using it to find the divisors of a large number of integers is the computational equivalent of trying to cut your lawn with scissors. Instead, ‘genpropd’ knows what integer ‘n’ you’re going up to so it just does upward counting, skipping ‘k*divisor’ iterations each go through. As the algorithm runs, it runs through the list faster and faster.
The difference? My brute force ‘propd’ method took 10 seconds. ‘genpropd’ took ~0.06 seconds. *insert choice expletive here*
Applying a similar method to the rest of the program, and a rather ingenious way of testing if an integer can be the sum of two abundant numbers within a list that I’m still trying to wrap my head around, the entire runtime goes from the ~60.5 seconds that my CPU slammed its soft supple head against the wall to a blistering ~2.9 seconds. By my scientific calculations that is a computational load decrease of a holy f-ckton.
So what did I learn?
- Testing a very large pool of numbers one by one with a computationally costly algorithm to get another list isn’t the best option if you can just generate that second list in a computationally efficient manner.
Duh. You moron. - Try not to be enamored with one way of doing things (list comprehension), it might not work well for what you’re trying to do. Sometimes tried and trusted methods are just as good or better than the new super-cool looking method that smokes behind the bleachers after school.
Otherwise, you’re just trying to cram a square peg into a circular black hole that represents all the time you wasted on your crap code! - It’s okay to make mistakes and it’s even better to learn from them. You improve by looking at other people’s work and comparing your own. Your time is never wasted if you learn from it. (Just kidding, I already knew this one, but you should know it too.)
Through the Eyes of a Life Long Learner 