Python:慢嵌套for循环

Question

我需要找出一个最佳的媒体选择，基于一定的限制。我在四个嵌套的for循环中执行它，因为它需要大约O（n^4）次迭代，所以速度很慢。我一直想快点，但还是很慢。我的变量可能高达几千个。在

下面是一个小例子，说明我要做的事情：

    max_disks = 5
    max_ssds = 5
    max_tapes = 1
    max_BR    = 1
    allocations = []
    for i in range(max_disks):
     for j in range(max_ssds):
        for k in range(max_tapes):
            for l in range(max_BR):
                allocations.append((i,j,k,l)) # this is just for example. In actual program, I do processing here, like checking for bandwidth and cost constraints, and choosing the allocation based on that. 

对于每种媒体类型，它的速度并不慢，但对于数千种媒体来说，速度会慢下来。在

我尝试的另一种方法是：

^{pr2}$

这样的话，即使对这么小的数字也很慢。在

两个问题：

1. 为什么第二种方法对小数字来说速度慢？在
2. 如何使我的程序适用于大数（以千为单位）？在

这是带有itertools.product在

            max_disks = 500
            max_ssds = 100
            max_tapes = 100
            max_BR    = 100
            # allocations = []
            for i, j, k,l in itertools.product(range(max_disks),range(max_ssds),range(max_tapes),range(max_BR)):
                pass

完成这些数字需要19.8秒。在

Answer 1

在Python中执行一万亿次的任何操作都会很慢。然而，这并不是你所做的全部。通过尝试在一个列表中存储所有的万亿项，你在内存中存储了大量的数据，并以一种在内存不再适合内存的情况下为计算机创建大量的交换内存的工作。在

Python列表的工作方式是分配一些内存来存储列表中的项。当您填充了列表并且需要分配更多的内存时，Python将分配两倍的内存，并将所有旧条目复制到新的存储空间中。只要它能放入内存就可以了——尽管每次扩展存储时它都要复制列表中的所有内容，但由于它的大小一直在翻倍，所以它必须减少复制的频率。当内存不足，必须将未使用的内存交换到磁盘时，问题就出现了。下一次尝试调整列表大小时，它必须从磁盘重新加载现在交换到磁盘的所有条目，然后再次将它们交换回磁盘，以获得写入新条目的空间。因此，这会造成大量磁盘操作的缓慢，这些操作会阻碍您的任务，并使其更慢。在

你真的需要把每一项都存储在一个列表中吗？你做完后打算怎么处理他们？你可以把它们写在磁盘上，而不是把它们放在一个巨大的列表中，尽管如果你有上万亿个，那仍然是一个非常大的数据量！或者你把大部分都过滤掉了？那会有帮助的。在

尽管如此，如果没有看到实际的程序本身，很难知道您是否有希望通过彻底搜索来完成这项工作。所有的变量都能同时达到千级吗？你真的需要考虑这些变量的每一个组合吗？当max_disks==2000时，您真的需要区分i=1731和i=1732的结果吗？例如，也许您可以考虑i 1,2,3,4,5,10,20,30,40,50100200030050010002000的值？或者也许有一个数学解？你只是在数东西吗？在

Answer 2

从评论中，我知道您正在处理一个可以重写为ILP的问题。你有几个约束条件，需要找到一个（接近）最优的解决方案。在

现在，ilp很难解决，而暴力强迫很快就变得很棘手（正如您已经看到的）。这就是为什么有几个真正聪明的算法在行业中使用，真正发挥神奇的作用。在

对于Python，有很多接口连接到现代求解器；有关更多详细信息，请参见例如thisSO post。您也可以考虑使用优化器，如^{}，但这些通常不进行整数编程。在