Python：慢嵌套for循环

我需要根据某些约束找出最佳的媒体选择。我在FOUR嵌套for循环中做，因为它会需要O（n^4）迭代，它很慢。我一直在努力让它更快，但它仍然很慢。我的变量可能高达数千。Python：慢嵌套for循环

这里是什么，我试图做一个小例子：

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

通过这种方式，即使是这些小数字慢。

两个问题：

为什么第二个是小数字慢？
如何让我的程序适用于大数字（以千计）？

这里是版本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秒用这些数字来完成。

来源

2016-09-19 Pretty

带有列表理解的第一个例子比第二个例子快*。它们在其他方面是等价的，但'allocations.append'属性查找和随后的方法调用减慢了嵌套循环。您可能想在这里查看'itertools.product（）'，并避免创建一个包含所有可能组合的巨大列表对象（而不是逐个处理这些项目）。 –

我也试过itertools.product（）。但那也没有成千上万的工作。 – Pretty

你是否坚持建立一个分配清单？你已经知道你正在构建的列表的一般结构，所以你不能单独处理分配？ –

从评论中，我得知你正在研究一个可以改写为ILP的问题。您有几个约束条件，需要找到（近乎）最佳解决方案。

现在，ILP很难解决，而且它们很快就会变得棘手（正如你已经见证过的那样）。这就是为什么有几个真正聪明的算法在行业中使用，真正发挥魔力。

对于Python来说，有很多接口可以连接现代求解器;有关更多细节，请参阅这个SO post。你也可以考虑使用优化器，如SciPy optimize，但那些通常不会进行整数编程。

来源

2016-09-19 09:20:26

在Python中做任何操作一万亿次将会很慢。但是，这并不是你正在做的。通过尝试将所有万亿项目存储在单个列表中，您将大量数据存储在内存中，并以一种为计算机创建大量工作的方式进行操作，以便在内存不再适合内存时交换内存。

Python列出的工作方式是他们分配一定量的内存来存储列表中的项目。当你填充列表并且需要分配更多时，Python将分配两倍的内存并将所有旧条目复制到新的存储空间中。只要它适用于内存，即使它在每次扩展存储时都必须复制列表中的所有内容，它也不会那么频繁地执行，因为它会使其大小加倍。问题出现在内存不足时，必须将未使用的内存交换到磁盘。下一次它尝试调整列表大小时，它必须从磁盘重新加载所有现在换出到磁盘的条目，然后再次将它们全部交换出来以获得写入新条目的空间。因此，这会造成大量缓慢的磁盘操作，这些操作会阻碍您的任务并使其更慢。

您是否真的需要将每个项目存储在列表中？完成后你会怎么做？你也许可以把它们写到磁盘上，而不是将它们堆积在一个巨大的列表中，但如果你有一万亿个，那仍然是一个非常大的数据量！或者也许你正在过滤大部分？这将有所帮助。所有这些说，没有看到实际的程序本身，很难知道你是否希望通过详尽的搜索来完成这项工作。所有的变量能否一次成千上万？你真的需要考虑这些变量的每一个组合吗？当max_disks == 2000时，你真的需要区分i = 1732和i = 1732的结果吗？例如，你可能会考虑i 1,2,3,4,5,10,20,30,40,50,100,200,300,500,1000,2000的值？或者，也许有一个数学解决方案呢？你只是计数物品？

来源

2016-09-19 09:24:32 Weeble

Python：慢嵌套for循环

回答

相关问题