のpython MemoryError：

Question

異なる種類の大きなリストを格納し、私はpython2.7で働いていると私はfollowindデータ構造体を構築する必要があります： それは、すべてのトリプレットは、保存する必要があります。x < yの< zの< N（Nが指定されています）。 私は三つ組をランダムに選ぶことができます。 データベースからトリプレットが削除されている場合はそのトリプレットを削除し、データベースにない場合は「False」を返す入力を持つPop関数を使用します。

Nは非常に大きくなる可能性があります。

私のコード：私のPCで

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

MemoryErrorがあるN=1000で。私は[]の代わりにdatastructを必要とします。 N（最低でもNの場合、私のPCのディスクスペースより小さく）

モジュールやそれ以外に使用できるモジュールはありますか？

Answer 1

私があなたの質問を理解する限り、その空のリストを回避し、追加を繰り返す必要があります。

私はあなたのプログラムを実行すると、私のローカルマシンで、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の場合、すべてのトリプレットを保存することはできません。 サイズのリストを3つ作成します - 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)