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. 

对于每种媒体类型的每一种类型，它都不会慢到数百种，但会慢到数千种。

我试过的其他方法是：

    max_disks = 5
    max_ssds = 5
    max_tapes = 1
    max_BR    = 1

    allocations = [(i,j,k,l) for i in range(max_disks) for j in range(max_ssds) for k in range(max_tapes) for l in range(max_BR)]

这样，即使对于如此小的数量，它也是缓慢的。

两个问题：

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

从评论中，我了解到您正在处理一个可以重写为ILP的问题。您有几个约束，需要找到(接近)最优的解决方案。

现在，ILPs很难解决，蛮力迫使它们很快变得棘手(正如您已经看到的)。这就是为什么在这个行业中有几种非常聪明的算法真正发挥了神奇的作用。

对于Python，有许多连接到现代解决程序的接口；有关更多细节，请参见此所以贴。您还可以考虑使用像SciPy optimize这样的优化器，但是这些优化器通常不执行整数编程。

Answer 2

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

Python列表的工作方式是分配一定数量的内存来存储列表中的项。当您填充列表并需要分配更多时，Python将分配两倍的内存，并将所有旧条目复制到新的存储空间中。这是很好的，只要它适合在内存-即使它必须复制列表的所有内容，每次它扩大存储，它必须这样做更少的频率，因为它不断翻倍的大小。当内存耗尽，必须将未使用的内存交换到磁盘时，问题就出现了。下一次尝试调整列表大小时，它必须从磁盘重新加载所有现在交换到磁盘的条目，然后再将它们全部交换，以获得写入新条目的空间。因此，这会产生许多缓慢的磁盘操作，这些操作会阻碍您的任务，并使其更慢。

你真的需要把每一件物品都存储在一个列表中吗？当你做完之后你打算拿它们做什么？你也许可以在你准备的时候把它们写到磁盘上，而不是把它们累积到一个巨大的列表中，尽管如果你有一万亿的数据，那仍然是非常大量的数据！或者你把他们中的大部分过滤掉了？那会有帮助的。

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