如何在Python中加速嵌套的for循环

Question

我有以下Python 2.7代码：

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列表如下：

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 循环。

有没有可能通过使用 itertools 或其他模块/函数来加速此代码？

编辑：我不能使用非标准的 Python 2.7 模块（如 numpy、scipy...）

- marco

---

如果这些列表是较大的数据结构的一部分，那么NumPy应该能够胜任。 - Christian Sauer

你能提供每个向量的长度吗？如果它们长度相同，你可以使用 zip。你也可以使用列表推导式，但这可能会让代码难以阅读。 - spacegoing

你可以用C/C++编写代码，然后将其导入到Python中（https://docs.python.org/2/extending/extending.html）吗？ - Pylinux

由于我们不知道您列表中的数据意味着什么以及您正在尝试执行什么样的操作，因此即使是构思答案也很困难。最重要的是不是“如何加速嵌套循环”，而是“我是否需要嵌套循环来实现我的目标”。换句话说，您需要找到更好的算法来执行所需的操作（或者重新考虑使用的数据结构）。嵌套循环总是麻烦的，因为它有效地使问题变成类似于“O(n^m)”的东西，如果列表大小相同，则为“n”，并且有“m”个嵌套循环。切换到编译语言不会改变复杂性。 - Łukasz Rogalski

谢谢你提供的信息，Rogalski。我不认为实际数字的意义会有太大帮助。它们本质上是校正系数、流速和方向。 为什么上面发布的数值不足够呢？ - marco

Answer 1

既然您说“只要代码运行速度快，可读性并不重要”，那么这就是实现的方法：

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

这段代码比 for 循环快 25%。但相信我，我会射杀写这段代码的人。

- spacegoing

---

谢谢@spacegoing！的确，现在代码更快了！ 它实际上需要像您这样分成三行吗？ 如果只有一行，它会更快吗？ - marco

@marco 不用谢。那种格式只是为了方便你阅读。无论你如何格式化，速度都是一样的。 - spacegoing

明白了。再次感谢你。 请问您能否提供您的姓名，以便我在源代码中注明您的贡献？ - marco

@marco 非常感谢你的好意。我宁愿你不要在你的代码中提到我，这样人们就不会讨厌我了哈哈。 - spacegoing

明白了。谢谢。 - marco

Answer 2

@Rogalski是正确的，你肯定需要重新思考算法（至少尝试一下）。

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

首先，尝试清理一下。例如，你似乎从来没有使用过l1_index，所以可以将其去掉。然后，您可以将发生在第一个循环内的所有内容移动到一个函数中。然后它会像这样：

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函数中执行同样的内部循环提取。

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])），但我不知道它是否会更快。

请注意，lambda表达式并不比同样方式执行同样任务的普通函数更快。但它们会破坏堆栈跟踪，使代码更难调试。至于itertools，你可以使用组合，但是你需要预先生成list_of_lists，因为没有关于给出组合顺序的协议。而zip并不是你所需要的。

代码的一个问题是，在嵌套循环的每一轮中都要遍历L3。解决这个问题的方法是添加一些预计算。你需要知道每个L4元素对应的L3索引。你可以这样做：

# 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]

- Alissa

---

谢谢你，Alissa！我确实使用了l1_index，但我没有发布使用它的代码。尽管如此，我仍然可以不使用l1_index变量。信不信由你，你发布的上面的代码实际上比我初始回复中的代码执行时间更长，慢了0.5秒。在使用列表推导式时是否存在速度问题？ - marco

很奇怪，通常像 [smth(i) for i in someList] 这样的结构比 for i in someList: newList.append(smth(i)) 更快。如果您用 list_of_lists = [[find_next(l,element) for element in L2] for l in L1] 替换第一行会发生什么？ - Alissa

嗨@ Alissa。感谢您的另一个建议。不幸的是，list_of_lists = [[find_next(l,element) for element in L2] for l in L1]的运行时间与非线程版本相同。我也不确定为什么列表推导式会产生相同的运行时间。 我对输入有控制。您建议将l1元素放入L1_dictionary中吗？ - marco

谢谢你，Alissa。但是为了创建那个字典，我需要对L3列表进行循环吗？ - marco

谢谢Alissa。 L3_dict = {element:index for element,index in enumerate(L3)} 应该改为 L3_dict = {element:index for index,element in enumerate(L3)}，这是唯一的更改吗？ - marco

Answer 3

下面的代码是@spacegoing和@Alissa的结合，可以得到最快的结果：

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]

感谢 @spacegoing 和 @Alissa 的耐心和时间。

- marco