Python: slow nested for loop
<p>I need to find out an optimal selection of media, based on certain constraints. I am doing it in FOUR nested for loop and since it would take about O(n^4) iterations, it is slow. I had been trying to make it faster but it is still damn slow. My variables can be as high as couple of thousands. </p>

<p>Here is a small example of what I am trying to do:</p>

<pre><code>    max_disks = 5
    max_ssds = 5
    max_tapes = 1
    max_BR    = 1
    allocations = []
    for i in range(max_disks):
     for j in range(max_ssds):
        for k in range(max_tapes):
            for l in range(max_BR):
                allocations.append((i,j,k,l)) # this is just for example. In actual program, I do processing here, like checking for bandwidth and cost constraints, and choosing the allocation based on that. 
</code></pre>

<p>It wasn't slow for up to hundreds of each media type but would slow down for thousands. </p>

<p>Other way I tried is :</p>

<pre><code>    max_disks = 5
    max_ssds = 5
    max_tapes = 1
    max_BR    = 1

    allocations = [(i,j,k,l) for i in range(max_disks) for j in range(max_ssds) for k in range(max_tapes) for l in range(max_BR)]
</code></pre>

<p>This way it is slow even for such small numbers.</p>

<p>Two questions:</p>

<ol>
<li>Why the second one is slow for small numbers?</li>
<li>How can I make my program work for big numbers (in thousands)?</li>
</ol>

<p>Here is the version with itertools.product</p>

<pre><code>            max_disks = 500
            max_ssds = 100
            max_tapes = 100
            max_BR    = 100
            # allocations = []
            for i, j, k,l in itertools.product(range(max_disks),range(max_ssds),range(max_tapes),range(max_BR)):
                pass
</code></pre>

<p>It takes 19.8 seconds to finish with these numbers.</p>

<p>Doing any operation in Python a trillion times is going to be slow. However, that's not all you're doing. By attempting to store all the trillion items in a single list you are storing lots of data in memory and manipulating it in a way that creates a lot of work for the computer to swap memory in and out once it no longer fits in RAM.</p>

<p>The way that Python lists work is that they allocate some amount of memory to store the items in the list. When you fill up the list and it needs to allocate more, Python will allocate twice as much memory and copy all the old entries into the new storage space. This is fine so long as it fits in memory - even though it has to copy all the contents of the list each time it expands the storage, it has to do so less frequently as it keeps doubling the size. The problem comes when it runs out of memory and has to swap unused memory out to disk. The next time it tries to resize the list, it has to reload from disk all the entries that are now swapped out to disk, then swap them all back out again to get space to write the new entries. So this creates lots of slow disk operations that will get in the way of your task and slow it down even more.</p>

<p>Do you really need to store every item in a list? What are you going to do with them when you're done? You could perhaps write them out to disk as you're going instead of accumulating them in a giant list, though if you have a trillion of them, that's still a very large amount of data! Or perhaps you're filtering most of them out? That will help.</p>

<p>All that said, without seeing the actual program itself, it's hard to know if you have a hope of completing this work by an exhaustive search. Can all the variables be on the thousands scale at once? Do you really need to consider every combination of these variables? When max_disks==2000, do you really need to distinguish the results for i=1731 from i=1732? For example, perhaps you could consider values of i 1,2,3,4,5,10,20,30,40,50,100,200,300,500,1000,2000? Or perhaps there's a mathematical solution instead? Are you just counting items?</p>

python performance linear-programming constraint-programming