Python nested loop speed issues

Question

I am currently working on a program to test for ideal angle-values to construct something. Now I'm stuck at a nested-for-loop which I'm going to attach below. While idealy it would count each 'a' to 9000, it already takes almost forever if values are set like below. Is there a way to speed up this nested loop? Or can i somehow assign more ressources to python?

for a1 in  xrange(15, 91):
    for a2 in xrange(15, 91):
        for a3 in xrange(15, 91):
            for a4 in xrange(15, 91):
                for a5 in xrange(15, 91):
                    for ite in xrange(1, 1000):
                        ok = mathmatvec(a1, a2, a3, a4, a5, ite) 
                        if ok == 1:
                                v[0] = a1
                                v[1] = a2
                                .
                                .

Are you sure you need to check all 76 * 76 * 76 * 76 * 76 * 999 = 2532989850624 = 2.5 trillion combinations? Even if operation to perform would be nothing (replace last for statement body with "pass") it'll still take "almost forever". — Łukasz Rogalski
– Łukasz Rogalski, Commented May 28, 2016 at 14:20
what does mathmatvec() do? time complexity for that function? — Bharath Ram
– Bharath Ram, Commented May 28, 2016 at 14:22
it calculates multiple vector and matrix multiplications. It doesn't take a notable time if just used once on its own. for a little more details see my response to Rory Daulton — Rugir
– Rugir, Commented May 28, 2016 at 15:05
If you look for parameters in high dimensions, you might want to use a random search or even a minimization over a loss criterion — MaxNoe
– MaxNoe, Commented May 28, 2016 at 18:30

Raymond Hettinger · Accepted Answer · 2016-05-28 14:21:18Z

1

The itertools.product() function will greatly speed the nested for-loops.

That said, the running time will likely be dominated by the total number of calls to mathmatvec().

edited May 28, 2016 at 14:21

answered May 28, 2016 at 14:17

Raymond Hettinger

229k67 gold badges405 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ecir Hana · Accepted Answer · 2016-05-28 14:20:16Z

0

You could try to convert for loops into while loops, should be faster as the latter does not create any iterators. So instead of:

for a1 in xrange(15, 91):

write:

a1 = 15
while a1 < 91:
    ...
    a1 += 1

Or try to use PyPy.

answered May 28, 2016 at 14:20

Ecir Hana

11.6k13 gold badges74 silver badges133 bronze badges

Comments

Rory Daulton · Accepted Answer · 2016-06-02 13:01:52Z

0

Solution: Use a different algorithm.

As it is now, you execute the innermost loop 999*(76**5) == 2,532,989,850,624 times. This is probably too many, unless the innermost loop calculations are trivial.

You say you want "to test for ideal angle-values to construct something." If you can formalize what "ideal" means, you can use an optimization algorithm to zero in on what you want. If you give us more details on what you are searching for, we may be able to tell you about a better Python routine or algorithm.

If I understand you correctly, mathmatvec() takes only values 0 and 1, and you want to find values of a1,a2,a3,a4 for 15 <= a1 <= 90 etc. and ite for 1 <= ite <= 999 that make mathmatvec(a1, a2, a3, a4, ite) equal to 1 and where ite is as small as possible.

You can make this a multidimensional minimization problem by using the function

def func(a1, a2, a3, a4, ite):
    return ite - 1000 * mathmatvec(a1, a2, a3, a4, ite)

Then func() returns a positive number for mathmatvec() == 0 and a negative one for mathmatvec() == 1, and the negative values are minimized when ite is minimized.

Depending on how "smooth" your function mathmatvec() is, how connected it is, and its fitness landscape, one of the minimization routines in scipy.optimize may solve your problem well enough. The scipy.optimize.differential_evolution() function looks particularly interesting.

edited Jun 2, 2016 at 13:01

answered May 28, 2016 at 14:20

Rory Daulton

22.7k7 gold badges46 silver badges51 bronze badges

3 Comments

Rugir Over a year ago

while i can't put the formula in mathmatvec into trivial terms, it tests for which 5 angles, a minimal ite can be reached (ite value is *0.0001 in the formula) so my guess was to check each possible angle combination (range 15 to 90 degrees) if a minimal valid (result of the function) value for ite can be found.

Rory Daulton Over a year ago

I do not understand what you mean about "ite." But are you looking for the values of variables a1, a2, a3, a4, a5, ite that give you the smallest "valid" result of the function mathmatvec()? If so, what kind of values are returned and with what range? What is an "invalid" function result? It now sounds like you want a multi-dimensional minimizer: more detail will confirm or deny.

Rugir Over a year ago

a1-5 and ite are part of one big formula which must result in a value within a certain range. if it does, the result is "valid" and i return 1, otherwise 0. However, the final result which I need, is a minimal ite for any constellation of a1-5. So whenever all conditions are met AND the ite is smaller then what any constellation so far resulted in, i save all current values.

Collectives™ on Stack Overflow

Python nested loop speed issues

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related