如何在Python中加快嵌套for循环 [英] How to speed up nested for loops in Python

问题描述

我有以下Python 2.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)

L1，L2，L3，L4，L5列表为:

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]

这些仅是示例；实际上，列表包含数十万个数字.解释程序需要数十秒才能计算出三个嵌套的for循环.

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.

是否有可能以某种方式加快此代码的速度，例如使用itertools或任何其他模块/功能?

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

我不能使用非标准的python 2.7模块(numpy，scipy ...)

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

推荐答案

@Rogalski是正确的，您肯定需要重新考虑算法(至少尝试这样做).

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

但是，如果找不到更好的算法，我认为您可以通过一些技巧来加快速度，同时仍然使用嵌套循环.请注意，我会将L *列表视为一些全局变量，不需要将其传递给每个函数.因此，您需要使这些列表对新功能可见，或者将它们添加为参数.

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.

首先，尝试清理.例如，您似乎从未使用过l1_index，因此可以摆脱它.然后，您可以将第一个循环内发生的所有事件移至一个函数.然后它将如下所示:

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

这很好，但是理解比带附加循环要快(此处您可以找到有关该主题的不错的文章).而且第一个循环非常简单，因此让我们将其折叠为listOfLists = [create_list(l1) for l1 in L1].而且我们可以在create_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] 

现在，它看起来更具可读性，并且应该可以更快地工作.您也可以尝试使用内置列表功能在列表中找到元素(l3_index = l3.index(L4[element-1])，)，但是我不知道它会不会更快.

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.

请注意，lambda的速度并不比通常的函数以相同的方式完成相同的事情的速度快.但是它们确实破坏了堆栈跟踪，因此使代码更难调试.从itertools开始，您可以使用组合，但是随后需要预先生成list_of_lists，因为没有顺序将组合提供给您.而zip并不是您所需要的.

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.

代码的问题之一是您在嵌套循环的每一轮中都遍历了L3.解决此问题的方法是添加一些预先计算.您需要为L4的每个元素知道L3的对应索引.您可以这样操作:

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]

这篇关于如何在Python中加快嵌套for循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！