python MemoryError：存儲不同類型的大列表

我正在使用python2.7，我需要構建followind數據結構：它必須存儲所有三元組，例如：x < y < z < n（N is given ）。我可以隨機選擇一個三元組。我有一個「流行」函數與輸入，如果它存在或從數據庫中刪除三重或返回「假」，如果它不在數據庫中。python MemoryError：存儲不同類型的大列表

N可以非常大。

我的代碼：

N = 1000 
Root = [] 
for x in range(0,N-2): 
    xNode = [x, []] 
    for y in range(x+1,N-1): 
     yNode = [y, []] 
     for z in range(y+1,N): 
      yNode[1].append(z) 
     xNode[1].append(yNode) 
    Root.append(xNode) 
    print "Loading [{0:.2f}%]".format(float(100*x)/(N-2))

在我的電腦

與N=1000有一個MemoryError。我想要一個datastruct而不是[]，它將部件存儲到內存中。我不在乎它是否慢，只要它不受N（至少N小於我的電腦中的磁盤空間）

是否有一個模塊或其他可以使用？

來源

2016-07-23 Guy Barash

請使用*代碼塊*（符號'{}'在編輯器），以包括Python代碼*不*堆片段（符號'<>'在編輯器）。堆棧片段僅適用於HTML/CSS/JavaScript *可運行*示例，它們不適用於其他語言。 – Bakuriu

在任何情況下，由於您使用的是python2，您應該使用'xrange'而不是'range'。另外，取決於你想用'Root'來做什麼，你可以在最內層的循環中存儲'xranges'：'yNode = [y，xrange（y + 1，N）]; xNode.append（yNode）'。這應該使用更少的內存，並且要快得多。缺點是你不能*修改* xrange'，但所有其他操作仍然有效。 – Bakuriu

據我瞭解你的問題，你想要一個解決方案，爲空列表和重複附加。

當我運行您的程序，在我的本地機器，輸出爲N = 4，是這樣的：

>>> N = 4 
>>> Root = [] 
>>> for x in range(0,N-2): 
...  xNode = [x, []] 
...  for y in range(x+1,N-1): 
...   yNode = [y, []] 
...   for z in range(y+1,N): 
...    yNode[1].append(z) 
...   xNode[1].append(yNode) 
...  Root.append(xNode) 
... 
>>> for i in Root: 
... print i 
... 
[0, [[1, [2, 3]], [2, [3]]]] 
[1, [[2, [3]]]]

我這裏假設你至少要輸出到似乎是這樣的：

[0, 1, 2] 
[0, 1, 3] 
[0, 2, 3] 
[1, 2, 3]

要實現這一點，您需要對代碼進行一些小改動。而不是臨時的xNode和yNode，你可以直接在最內層的循環中追加每個列表。現在

>>> N = 4 
>>> Root = [] 
>>> for x in xrange(0, N-2): 
... for y in xrange(x+1, N-1): 
...  for z in xrange(y+1, N): 
...  Root.append([x, y, z]) 
... 
>>>

，對於N = 1000，列表的近似長度將O(N^3)或周圍10^9其是用於在本地機器相當大的。爲了給你一個想法，列表中的每個元素都由3個整數組成。假設整數的大小爲4 bytes，則列表中的每個元素的大小將爲12 bytes。將完整列表存儲在內存中所需的總內存將爲12*(10^9) bytes，大約爲11 GB。

關於檢查和突然離開元素的主要問題，你可以按如下做到這一點：

的想法是假設所有的有效三胞胎在內存初始存在（雖然我們不能將其存放因爲你提到N可能非常大，我們不能存儲所有的三元組用於更大的值N）。我們將製作三個N大小的列表 - x,y和z。每當我們彈出一個三元組時，我們將在這些列表中標記相應的值。在稍後的時刻，如果我們遇到相同的三元組，那麼我們可以在O(1)時間內檢查它是否已經彈出或不彈出。空間複雜度爲O(N)，時間複雜度爲O(queries)。

N = int(raw_input()) 
# number of queries 
queries = int(raw_input()) 
x = [0]*N 
y = [0]*N 
z = [0]*N 
for i in xrange(queries): 
    a, b, c = map(int, raw_input().split()) 
    if a < b and b < c and c < N: 
     # Basic idea is if (x[a], x[b], x[c]) = (1, 1, 1), then it has already 
     # popped off, else, we pop it and mark it as popped. 
     if x[a] == 1 and x[b] == 1 and x[c] == 1: 
      print 'Triplet not in memory to remove' 
     else: 
      x[a] = 1 
      x[b] = 1 
      x[c] = 1 
      print 'Triplet (%d, %d, %d) popped off memory' % (a, b, c)

來源

2016-07-24 09:33:59 Shubham

很好的答案...爲我工作.. – NSPratik

python MemoryError：存儲不同類型的大列表

回答

相關問題