CODEWITHSUNDEEP
pythonfor-loopnested
marco
marco

Reputation: 893

How to speed up nested for loops in Python

I have the following Python 2.7 code:

listOfLists = []
for l1_index, l1 in enumerate(L1):
    list = []
    for l2 in L2:
        for l3_index,l3 in enumerate(L3):
            if (L4[l2-1] == l3):
                value = L5[l2-1] * l1[l3_index]
                list.append(value)
                break
    listOfLists.append(list)

with the L1,L2,L3,L4,L5 lists being:

L1 = [[0.60, 0.95, 0.38, 1.02, 0.29, 0.43], [0.40, 0.09, 0.87, 0.85, 0.70, 0.46], [0.67, 0.91, 0.66, 0.79, 0.86, 0.06], [0.59, 1.81, 0.05, 1.88, 0.20, 0.48], [0.64, 0.34, 0.37, 1.39, 0.56, 0.27], [0.56, 0.34, 0.68, 2.79, 0.18, 0.42], [0.42, 1.67, 0.04, 0.44, 0.25, 0.94], [0.32, 1.92, 0.95, 2.85, 0.95, 0.96], [0.50, 0.68, 0.84, 1.79, 0.35, 0.09], [0.34, 0.66, 0.85, 0.35, 0.38, 0.59], [0.50, 0.79, 0.45, 2.93, 0.50, 0.92], [0.11, 0.11, 0.93, 1.11, 0.81, 0.49]]  # a list of 12 sublists
L2 = [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
L3 = [480, 120, 35, 0, 520, 300]
L4 = [120, 120, 120, 0, 300, 35, 35, 520, 300, 480, 120, 480, 0, 35, 0, 0, 300]
L5 = [5.4, 2.83, 1.16, 6.9, 0.76, 2.15, 5.61, 3.12, 1.57, 0.08, 5.36, 0.2, 1.2, 1.4, 2.9, 2.1, 3.5]

These are only examples; in reality the lists contain hundreds of thousands of numbers. The interpreter takes tens of seconds to calculate the three nested for loops.

Is it possible to somehow speed up this code, e.g. using itertools or any other module/function?

EDIT: I can not use non-standard python 2.7 modules (numpy, scipy...)

Upvotes: 7

Views: 34933

Answers (3)

marco
marco

Reputation: 893

The following code is a combination of both @spacegoing and @Alissa, and yields the fastest results:

L3_dict = {l3:l3_index for l3_index,l3 in enumerate(L3)}

list_of_lists = [[L5[l2 - 1] * l1[L3_dict[L4[l2-1]]]
     for l2 in L2]
 for l1 in L1]

Thank you both @spacegoing and @Alissa for your patience and time.

Upvotes: 1

Alissa
Alissa

Reputation: 714

@Rogalski is right, you definitely need to rethink the algorithm (at least try to).

But if you can't find a better algorithm, I think you could speed up a bit by some tricks while still using nested loops. Note that I will treat L* lists as some global variables, which I don't need to pass to every function. So, you need to either keep those lists visible to new functions or add them as parameters.

First of all, try to clean-up. For example, you seem to never use l1_index, so you can get rid of it. Then you can move everything that happens inside the first loop to a function. It will then look like this:

listOfLists = []
for l1 in L1:
    listOfLists.append(create_list(l1))

def create_list(l1):
    list = []
    for l2 in L2:
        for l3_index,l3 in enumerate(L3):
            if (L4[l2-1] == l3):
                value = L5[l2-1] * l1[l3_index]
                list.append(value)
                break
    return list

This is nice, but comprehensions are faster than loop with appends (here you can find a nice article on the topic). And the first loop is quite simple, so let's collapse it into listOfLists = [create_list(l1) for l1 in L1]. And we can perform same inner loop extraction on our create_list function

list_of_lists = [create_list(l) for l in L1]

def create_list(l):
    return [find_next(l, element) for element in L2]

def find_next(l, element):
    for l3_index, l3_element in enumerate(L3):
        if (L4[element - 1] == l3_element):
            return L5[element - 1] * l[l3_index]

now it looks more readable, and should work a bit faster. You could also try to use built-in list function for finding element in list (l3_index = l3.index(L4[element-1]), ), but I don't know if it will be any faster.

Note that lambdas are not faster than usual functions doing same thing in same way. But they do spoil stack-traces and thus make code harder to debug. As of itertools, you could use combinations, but then you will need to pre-generate the list_of_lists, because there is no contract on order in which combinations are given to you. And zip is just not what you need.

One of the problems with the code is that you loop through L3 in each round of the nested loop. Solution to this problem is to add some precalculations. What you need is to know for each element of L4 a corresponding index of L3. You could do it this way:

# this will allow you to get index by element at a constant time
# and it only takes O(N)
L3_dict = {element:index for element,index in enumerate(L3)}

list_of_lists = [create_list(l) for l in L1]

def create_list(l):
    return [find_next(l, element) for element in L2]

def find_next(l, element):
    # if you use dict, you reduce time of this method from O(N) to constant
    # as both access to dict item by key and to list item by index
    # are done in a constant time
    l3_index = L3_dict[L4[element-1]]
    return L5[element-1] * l[l3_index]

Upvotes: 5

spacegoing
spacegoing

Reputation: 5306

Since you said the readability is not important as long as it speeds up the code, this is how you do the trick:

[[L5[l2 - 1] * sl1 for sl1, l3 in zip(l1, L3)
     for l2 in L2 if L4[l2 - 1] == l3]
 for l1 in L1]

This code is 25% faster than for loop. But trust me I will shoot him whoever wrote this in my code.

Upvotes: 8

Related Questions