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循環

回答

相關問題