From the course: Faster Python Code

Cheating example - Python Tutorial

From the course: Faster Python Code

Start my 1-month free trial

Cheating example

“

- [Narrator] Let's say you're competing with Amazon and use robot walkers with an algorithm to pack shipments into a minimum number of boxes. We're going to simplify the problem and look only at volume. We'll get a list of items, each with its own volume, and the volume of the bin, called bin size, and return the optimal solution with the minimum number of bins that can hold all of these items. Let's see a solution to this problem. This is a recursive algorithm that tries all options and return the best one. So at line four, we have bin pack of items bin size and a list of bins, and we initialize the list of bins to be empty if it's the first call. And then we recursively try all the combinations and at line 23, we return the minimal with the key of len. And we want the minimal number of bins. Let's save this code and try it out. So ipython. And run pack of py. So we do a bin pack of the items with volumes one, two, and three, in bins of size four. And we pack two items in one bin and the third item in the next one. Can try it again, let's try a bigger list. This time with five items and we get the packing, which is optimal. All the bins are full except the last one. And let's time it now. So I'm going to use time just for one function code. We'll do bin pack of one, two, and three times 10 so it's 30 items in bins of size of four. This is almost one and a half seconds for 30 items. That's not good. This problem is known as bin packing or the nap sack problem. These problems are what's called empty heart problems. We assume they cannot be solved in the polynomial type. Looking at the complexity chart, we see that two to the power of n is rising much, much higher than n to the power of two. The bin packing algorithm has been studied a lot, and there are many approximation algorithms for it. Let's try a greedy first fit algorithm. If an item fits in a bin, we continue from there and don't try more solutions. So here is our code with greedy bin pack. We go over every item and if it fits in the bin, we edit for the current bin. And if not, we create a new bin for it. And we return the number of bins. Let's save this code and try it out. So run pack.py. And now we can do a greedy bin pack of one, two, and three in bins of four, and we get something which is close to what we did before. Next two out number. However, if you len of greedy bin pack of one, two, and three times three in bins of four, we'll get six bins. Now let's compare it to the optimal solution. The len of bin pack of one, two, and three, and it's five. So we have one box more. And let's time. So time equal greedy bin pack of one, two, and three times ten and four. And this is 92.7 microseconds, which is roughly a millisecond, which means comparing to our run time of 1.3 seconds, we are about 1500 times faster. It was shown that in the worst case, the first fit solution returns twice as many boxes as the optimal solution. As the business owner, it's your call if this extra speed is worth the trade off for extra boxes. Think of places in your code where you can return an approximation. It might speed it up a lot.

Contents