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>From the comments, I got that you're working on a problem that can be rewritten as an <a href="https://en.wikipedia.org/wiki/Integer_programming" rel="nofollow">ILP</a>. You have several constraints, and need to find a (near) optimal solution.</p>

<p>Now, ILPs are quite difficult to solve, and brute-forcing them quickly becomes intractable (as you've already witnessed). This is why there are several really clever algorithms used in the industry that truly work magic.</p>

<p>For Python, there are quite a few interfaces that hook-up to modern solvers; for more details, see <em>e.g.</em> this <a href="http://stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming">SO post</a>. You could also consider using an optimizer, like <a href="http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html" rel="nofollow"><code>SciPy optimize</code></a>, but those generally don't do integer programming.</p>

python performance linear-programming constraint-programming