7

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...)

Improve this question
8
  • 1
    are the lists part of a larger data structure, then numpy should be able to do the job Commented Jul 8, 2016 at 9:59
  • @ChristianSauer Thank you for the reply, and I apologize for not mentioning that I can not use any python 2.7 module which requires additional installation, like numpy. Commented Jul 8, 2016 at 10:01
  • 1
    Could you provide the length of each vector? If they are at the same length you can use zip. You can also use list comprehension thought it will be too ugly to read. Commented Jul 8, 2016 at 10:08
  • 1
    Could you maybe write the code in C/C++ and import it into Python (docs.python.org/2/extending/extending.html) ? Commented Jul 8, 2016 at 10:54
  • 2
    Since we do not know what data in your list means and what kind of operation you are trying to perform, it's hard to even conceptualize an answer. Bottom line is not how to speed up nested loop, is do I even need nested loop to achieve what I want. To rephrase - you need to find better algorithm to perform operation you want (or maybe rethink used data structure). Nested looping is always troublesome, as it effectively makes problem something like O(n^m) if lists are about same size n and there is m nested loops. Switching to compiled language won't change complexity. Commented Jul 8, 2016 at 11:13

3 Answers 3

Reset to default
8

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.

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

5 Comments

Thank you @spacegoing! Indeed the code is quicker now! Does it actually need to be put in three lines like you did it? And will it be even more quicker if it's only one line?
@marco You are welcome. That format style is only for your readability. The speed are all the same no matter how you format them.
Understood. Thank you once again. Is it possible to post your name, so that I can credit you in the source code?
@marco Thank you very much for your kindness. I'd rather you don't mention me in your code so people can't hate me back lol.
Understood. Thank you.
5

@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]
Improve this answer

12 Comments

Spasibo Alissa! I do use l1_index but I did not post the code which uses it. Nevertheless I can live without the l1_index variable. Believe it or not the upper code you posted actually takes more to execute then the one in my initial reply. It's 0.5 seconds slower. Is there some speed drawback in using list comprehensions?
that's strange, usually constructions like [smth(i) for i in someList] are faster than ones like for i in someList: newList.append(smth(i)) What would happen if you replace first lines with list_of_lists = [[find_next(l,element) for element in L2] for l in L1]?
by the way, do you have any control on your input? If you transform some of them into dicts, you could save a huge amount of time... You said there are coefficients, those usually can be stored in a dict
Hi @Alissa. Thank you for another suggestion. Sadly list_of_lists = [[find_next(l,element) for element in L2] for l in L1] resulted in the same run time as non threaded version. I also not sure why comprehension list yield the same run time. I do have control over inputs. Do you advise putting l1 elements in a L1_dictionary?
No, I meant that you could identify pairs of lists that are matched by simple rules and make them dicts. E.g. l3_index is an index of element matching certain element from L4. Can you make a dict that will have L4 elements for keys and l3 indices for value (you won't to iterate through L3 then)
|
1

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.