在Python中創建嵌套列表的時間複雜性

我在Python 2.6.6中創建了嵌套列表時遇到了一個奇怪的問題。在Python中創建嵌套列表的時間複雜性

考慮以下兩個功能：

def lists(n): 
    start_time = time.time() 
    lists = [None]*n 
    for i in xrange(n): 
      lists[i] = [None]*n 
      for j in xrange(n): 
        lists[i][j] = [] 
    print time.time() - start_time 

def simple_lists(n): 
    start_time = time.time() 
    lists = [None]*n 
    for i in xrange(n): 
      lists[i] = [None]*n 
      for j in xrange(n): 
        lists[i][j] = False 
    print time.time() - start_time

它們都分配大小爲n×n個的陣列。一個賦值爲「False」，一個賦值爲空列表。據我所知，它們都應該在O（n^2）中運行。然而，這似乎並不如此......遵守以下測試運行：

>>> for i in [4000, 8000, 16000]: simple_lists(i) 
2.11170578003 
8.67467808723 
34.0958559513 
>>> for i in [1000, 2000, 4000]: lists(i) 
1.13742399216 
7.39806008339 
78.0808939934

正如你所看到的，simple_lists（）似乎大致成長爲O（n^2），而列表（）似乎成長超過O（n^3）！

這是怎麼回事？這個怪癖完全徹底地破壞了我的代碼的複雜性，我無法解釋爲什麼它的行爲如此。有沒有人有任何想法？

編輯：列表解析似乎會導致相同的複雜性問題。

重新定義列表（）一樣

def lists(n): 
    start_time = time.time() 
    lists = [[[] for y in xrange(n)] for x in xrange(n)] 
    print time.time() - start_time

導致以下結果

>>> for i in [1000, 2000, 4000]: lists(i) 
0.388785839081 
4.45830011368 
65.6449248791

...這仍然是明顯處於增長速度快於爲O（n^2）（甚至更快比O（n^3） - sheesh）。

edit2：在進一步調查問題後，它似乎是由垃圾收集器引起的。運行gc.disable()後，這是與原始名單（）的結果定義：

>>> for i in [1000, 2000, 4000]: lists(i) 
... 
0.155457019806 
0.616811990738 
2.38965821266

這真的是太整齊爲O（n^2）。

道德故事：不要相信垃圾收集器！

來源

2011-11-05 quakes

@ [X [x]（N）]中的[[E for y in]（x）] –

@CatPlusPlus：嘗試了您的建議（請參閱編輯），但沒有幫助解決複雜性問題。 – quakes

哦，我不知道複雜性，但它肯定是一個更好的語法。如果你需要固定大小的有效的多維數組，你應該使用NumPy。 –

結果怪異的行爲是由垃圾收集器造成的。將其關閉與gc.disable()產生以下：

>>> for i in [1000, 2000, 4000]: lists(i) 
... 
0.155457019806 
0.616811990738 
2.38965821266

哪個適合爲O（n^2）像手套。

來源

2011-11-06 10:09:46 quakes

在我的機器

for i in [1000, 2000, 4000]: lists(i)

給

0.994000196457 
4.31200003624 
17.9900000095

這是一個很好整潔爲O（n^2）。最後一個消耗1GB內存，因此列表（8000）會使硬盤驅動器崩潰並導致我的機器出現故障。 delnan可能是對的，我會在操作過程中檢查你的機器的可用內存和python的內存消耗。

來源

2011-11-05 23:58:10

在Python中創建嵌套列表的時間複雜性

回答

相關問題