2

何百万ものアイテムのリストを生成し、最初のリストに基づいて別のリストを生成するスクリプトを書いています。メモリが非常に速くいっぱいになり、スクリプトは続行できません。リストをファイルに直接保存してから、ファイル行を直接ループするのは良い考えだと思いました。これを行う最も効率的な方法は何ですか?

編集：

行ごとにツリーを生成しようとしています。row5_nodes は何百万ものアイテムを取得でき、row6_nodes の生成に使用するため削除できません

import random

class Node:
    def __init__(self, id, name, parent=None):
        self.id = id
        self.name = name
        self.parent = parent

def write_roots(root_nodes, roots):
    global index
    index = 0
    for x in xrange(0,roots):
        node = Node(index,"root"+str(x))
        root_nodes.append(node);
        f.write(str(node.id)+","+str(node.name)+","+str(node.parent)+"\n")
        index += 1;
    return

def write_row(parent_nodes, new_nodes, children):
    global index
    for parent_node in parent_nodes:
        for x in xrange(0,children):
            node = Node(index,"cat"+str(parent_node.id)+"-"+str(x), parent_node.id)
            new_nodes.append(node);
            f.write(str(node.id)+","+str(node.name)+","+str(node.parent)+"\n")
            index += 1;
    return

f = open("data.csv", "wb")
roots = 1000
root_nodes =[]
row1_nodes =[]
row2_nodes =[]
row3_nodes =[]
row4_nodes =[]
row5_nodes =[]
row6_nodes =[]
row7_nodes =[]
row8_nodes =[]
row9_nodes =[]

write_roots(root_nodes, roots)
print "1"
write_row(root_nodes, row1_nodes, random.randrange(0,10))
print "2"
write_row(row1_nodes, row2_nodes, random.randrange(0,10))
print "3"
write_row(row2_nodes, row3_nodes, random.randrange(0,10))
print "4"
write_row(row3_nodes, row4_nodes, random.randrange(0,10))
print "5"
write_row(row4_nodes, row5_nodes, random.randrange(0,10))
print "6"
f.close()
4

2 に答える 2

6

あなたのコードは、ノードのレベルの行ごとに個別のリストを作成していますが、前の行と現在生成しているもの以上は必要ありません。

それほど多くの情報をメモリに保持する必要はありません。使用する必要がなくなったものは破棄してください。

import csv
import random

class Node(object):
    _index = 0
    __slots__ = ('id', 'name', 'parent')

    def __init__(self, name, parent=None):
        self.id = Node._index
        Node._index += 1

        self.name = name
        self.parent = parent

def write_roots(roots, writer):
    nodes = []
    for x in xrange(roots):
        node = Node('root{}'.format(x))
        root_nodes.append(node)
        writer.writerow([node.id, node.name, ''])
    return nodes

def write_row(parent_nodes, writer, children):
    nodes = []
    for parent_node in parent_nodes:
        for x in xrange(children):
            node = Node('cat{}-{}'.format(parent_node.id, x), parent_node.id)
            nodes.append(node)
            writer.writerow([node.id, node.name, node.parent])
    return nodes

roots = 1000

with open("data.csv", "wb") as f:
    writer = csv.writer(f)

    nodes = write_roots(roots, writer)

    for i in xrange(9):
        print 'Writing row {}'.format(i + 1)
        nodes = write_row(nodes, writer, random.randrange(1, 11))

アイテムを指数関数的に作成しているため、これはおそらくまだメモリに収まりません。ここに最大 1000 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 == 1000^9 == 1 兆個のリーフ ノードを作成しています。メモリに 1.1 兆個のノードを収めることができる場合、上記のソリューションはうまくいくはずですが、各ノードには約 180 バイトのメモリと、参照を保持するためのリスト インデックス用の 1.1 兆バイトが必要で、48 テラバイトのフットプリントになります。情報。

この問題を解決する前に、いくつか変更を加えたことを最初に指摘しておきます。

  • クラスは新しい IDのNode生成を担当するNode._indexようになり、グローバルの代わりにクラス属性が使用されます。
  • __slots__クラス属性を使用して、メモリのオーバーヘッドを節約しました。
  • write_rootsおよび関数はwrite_row、渡された変更可能な空のリストを変更する代わりに、生成された新しいノードのセットを返します。
  • csvモジュールが使用されます。CSV ファイルを作成している場合、このモジュールを使用すると、その作業が大幅に簡素化されます。
  • csv.writer()インスタンスは、ファイル オブジェクトをグローバルとして使用する関数ではなく、パラメーターとして関数に渡されます。
  • 代わりrandrange(1, 11)に、レベルで0の子を生成しないようにしました。ランダムな深さが必要な場合は、xrange(9)代わりに外側のループ ( ) を変更します。

ノードが CSV ファイルに書き込まれる順序にこだわらない場合は、代わりにジェネレーターの使用に切り替えることができます。次のバージョンでは、最初のバージョンの息を先に書くのとは対照的に、深さから先にノードを書き込みますが、使用するメモリは大幅に少なくなります。

import collections

def write_roots(roots, writer):
    for x in xrange(roots):
        node = Node('root{}'.format(x))
        writer.writerow([node.id, node.name, ''])
        yield node

def write_row(parent_nodes, writer, children):
    for parent_node in parent_nodes:
        for x in xrange(children):
            node = Node('cat{}-{}'.format(parent_node.id, x), parent_node.id)
            writer.writerow([node.id, node.name, node.parent])
            yield node

roots = 1000

with open("data.csv", "wb") as f:
    writer = csv.writer(f)

    nodes = write_roots(roots, writer)

    expected_total = leaf_nodes = roots
    for i in xrange(9):
        childcount = random.randrange(1, 11)
        leaf_nodes *= childcount
        expected_total += leaf_nodes
        print 'Generating row {} with {} nodes per parent'.format(i + 1, childcount)
        nodes = write_row(nodes, writer, childcount)

    print 'Writing out {} nodes'.format(expected_total)
    # we need to loop over the last `nodes` generator to have everything written to a file:
    collections.deque(nodes, maxlen=0)  # empty generator without storing anything

このソリューションでは、一度に最大 10 個のノードをメモリに保持するだけでよく、それ以上は必要ありません。

より低い制限でテストを実行すると、randrange()ほんの一瞬で 50 万のノードが作成されました。選択された子の乱数が深さごとに 10 に近づくと、ジェネレーターに少し時間がかかりますが、完全なツリーを 1 時間ほどで生成できます。

次の問題は、ディスク容量の問題です。たとえば、約 80 億のノード (平均的なケース) を含む CSV ファイルは、わずか 250 GB のストレージしか必要としません。ただし、最大 1 兆 111 億のノードを生成できる可能性があり、その結果、62 TB の CSV ファイルが生成されます。

于 2013-05-07T10:31:21.753 に答える
1

別の深さ優先のジェネレーターベースのソリューション...

import random

next_id = 0

def gen(depth, parent_id=None):
    global next_id
    if parent_id is None:
        nodes = 1000
    else:
        nodes = random.randrange(0, 10)
    for i in range(nodes):
        next_id += 1
        if parent_id is None:
            name = 'root%d' % i
            yield '%d, %s, NULL' % (next_id, name)
        else:
            name = 'cat%d-%d' % (parent_id, next_id)
            yield '%d, %s, %s' % (next_id, name, parent_id)
        if depth > 1:
            for s in gen(depth-1, next_id):
                yield s

f = open('data.csv', 'wb')
for l in gen(6):
    f.write('%s\n') % l
f.close()
于 2013-05-07T10:52:02.893 に答える