How to optimize a nested loop in python?

Question

I want to process all entries of the messages_grouped dictionary with all of the remaining. However, it is taking a lot of time to process since I'm repeating some computations with the two for loop. But I can't find an easy way to avoid those repetitions, once I'm new in python. Basically I want to calculate the line for each drone and then get the intersection with each of the remaining drones. I'm using sympy library (Line1.intersection(Line2)) and inside Line_analysis function aswell. I know I'm repeating some computations, I just can't find a way to avoid that. I haven't finished the code yet to save the intersections.

def Collision_checker(messages_grouped):
    """
    messages_grouped as example:{Drone0: (list of dictionaries), Drone1: (list of dictionaries), ...}
    """
    for key in messages_grouped:
         X_new=messages_grouped[key][1]['X (ENU)']
         Y_new=messages_grouped[key][1]['Y (ENU)']
         Z_new=messages_grouped[key][1]['altitude']
         X_old=messages_grouped[key][0]['X (ENU)']
         Y_old=messages_grouped[key][0]['Y (ENU)']
         Z_old=messages_grouped[key][0]['altitude']
         for key in messages_grouped:
             X2_new=messages_grouped[key][1]['X (ENU)']
             Y2_new=messages_grouped[key][1]['Y (ENU)']
             Z2_new=messages_grouped[key][1]['altitude']
             X2_old=messages_grouped[key][0]['X (ENU)']
             Y2_old=messages_grouped[key][0]['Y (ENU)']
             Z2_old=messages_grouped[key][0]['altitude']
             Line1=Line_analysis(X_new,Y_new,Z_new, X_old, Y_old, Z_old)
             Line2=Line_analysis(X2_new,Y2_new,Z2_new, X2_old, Y2_old, Z2_old)

             if Line1 is not None and Line2 is not None:
                 Intersection=Line1.intersection(Line2)
             else:
                 pass

I really appreciate some help. Thanks!

Can you explain the problem you are solving? To identify a more efficient algorithm, one would need to know that — Olivier Melançon, Aug 14 '19 at 13:21
Perhaps better suited to [codereview.se] but in its current format, it looks like it'd be off topic — Sayse, Aug 14 '19 at 13:22
Basically I wanto to calculate the line for each drone and then get the intersection with each of the remaining drones. I'm using sympy library (Line1.intersection(Line2)) and inside Line_analysis function aswell. I know I'm repeating some computations, I just can't find a way to avoid that. — Saul Santos, Aug 14 '19 at 13:24
Do you want to get all intersections? Because right now it seems you are throwing every single result away. — Olivier Melançon, Aug 14 '19 at 13:28
Also, please update your question, do not just comment this information — Olivier Melançon, Aug 14 '19 at 13:29
Maybe iam wrong as iam not acquainted with `Line_analysis()` and `intersection()` but it look likes like you are using some kind of Spatial Data.. So why not use a RDMS to optimize this? When using indexing the RDMS should be able to do the intersection pretty fast without loop nesting in the joins/intersection.. — Raymond Nijland, Aug 14 '19 at 13:44

score 3 · Answer 1 · answered Aug 14 '19 at 13:29

Take advantage of the itemgetter function from the operator module and tuple unpacking. Also, use itertools.product to reduce this to a single loop (product encapsulates the second one).

from operator import itemgetter
from itertools import product


def Collision_checker(messages_grouped):
    """
    messages_grouped as example:{Drone0: (list of dictionaries), Drone1: (list of dictionaries), ...}
    """

    get_triple = itemgetter('X (ENU)', 'Y (ENU)', 'altitude')

    for (key1, value1), (key2, value2) in product(messages_grouped.items(), repeat=2):
        old1, new1 = [get_triple(value1[x]) for x in (0,1)]
        old2, new2 = [get_triple(value2[x]) for x in (0,1)]

        Line1 = Line_analysis(*new1, *old1)
        Line2 = Line_analysis(*new2, *old2)

        if Line1 is not None and Line2 is not None:
            Intersection = Line1.intersection(Line2)

It's still computing `Line_analysis` N^2 times instead of N times… So the code is more concise but still slow. — Nowhere man, Aug 14 '19 at 13:42

score 1 · Answer 2 · answered Aug 14 '19 at 13:40

I'm assuming that Line_analysis will always return the same result given the same arguments (the technical term is that it's referentially transparent, or a "pure" function).

Also, warning: I can't run your code, so I can 't profile it. And it is always best to start doing optimization when having measured what actually takes time (sometimes, even a bad algorithm doesn't compare to the time spent doing I/O, for example).

In your current code, you will execute N^2 passes of the internal loop if you have N drones. Which means you're wasting calls to Line_analysis. You should cache those results once and for all:

def Collision_checker(messages_grouped):
    """
    messages_grouped as example:{Drone0: (list of dictionaries), Drone1: (list of dictionaries), ...}
    """

    line_analyses = {}

    for key in messages_grouped:
         X_new=messages_grouped[key][1]['X (ENU)']
         Y_new=messages_grouped[key][1]['Y (ENU)']
         Z_new=messages_grouped[key][1]['altitude']
         X_old=messages_grouped[key][0]['X (ENU)']
         Y_old=messages_grouped[key][0]['Y (ENU)']
         Z_old=messages_grouped[key][0]['altitude']
         line_analyses[key] = Line_analysis(X_new,Y_new,Z_new, X_old, Y_old, Z_old)

    for key1 in messages_grouped:
        Line1 = line_analyses[key1]
        for key2 in messages_grouped:
            Line1 = line_analyses[key2]

             if Line1 is not None and Line2 is not None:
                 Intersection=Line1.intersection(Line2)
             else:
                 pass

It is better. However it is still doing the N^2 computations, which keeps making it a little bit slow. — Saul Santos, Aug 14 '19 at 14:07
If you want to compute something about each element of a cartesian product, you usually need the N^2 steps… — Nowhere man, Aug 14 '19 at 14:10
Yes you are right! But the intersection of Drone0 line with Drone1 line is the same of Drone1 with Drone0. Sorry for not being that ilustrative. — Saul Santos, Aug 14 '19 at 14:13
Haha, I almost wrote that you could avoid computing the same intersection twice. First, it is not obivous from the code that you can. The intersection method might not be commutative. Second, it would be an improvement, but it might be negligible. (hence always optimizing with profiling data in hand) — Nowhere man, Aug 14 '19 at 14:17
Also, avoid those "wasted" computations would make the code significantly more complex. Sometimes, way simpler, more robust, and just a bit slower, is a very good choice. — Nowhere man, Aug 14 '19 at 14:18

score 0 · Answer 3 · answered Aug 14 '19 at 13:31

Generally speaking for loop optimization, the more complex loop should be the inner loop (looks correct), and you can vectorize operations. Beyond that you can use some JIT compilers like Numba, and ultimately Cython could improve performance 10 fold with prange(). Even compiling as is in Cython would likely improve it 2-3 fold.

Here's some info on vectorization: How to optimize a nested for loop in Python

Cython compilation will require Cython (pip install), a setup.py / distutils compilation or the cython magic; https://cython.readthedocs.io/en/latest/src/tutorial/cython_tutorial.html Youtube can be helpful, all the files confused me at first.

Can also be used in ipynb, with the magics:

%load_ext cython #in one cell, once.

%%cython #in each cell using cython.

for prange (to optimize further), you'll need to turn off GIL and can play with various steps etc. Further reading: https://cython.readthedocs.io/en/latest/src/userguide/parallelism.html

How to optimize a nested loop in python?

3 Answers3