编写一个高效的python邻接树生成脚本

Question

我正在编写一个脚本，该脚本生成数百万个项目的列表，然后基于第一个列表生成另一个列表。它非常快速地填充内存，脚本无法继续。 我认为将列表直接存储在文件中然后直接在文件行上循环可能是一个好主意。 什么是最有效的方法来做到这一点？

编辑：

我想按行生成一个行。 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() 

Answer 1

你的代码是为节点级的每一行创建单独列出我不能删除它，但你永远需要比以前更多行加上你现在产生的东西。

没有必要保留在内存多的信息，丢弃你不再需要使用：

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万亿个节点，上面的解决方案应该适合你，但是每个节点需要大约180个字节的内存，外加1.1万亿字节的列表索引来存放引用，占用48个字节信息。

之前，我们解决这个问题，我首先要指出的是，我已经改变了一些事情：

• 的Node类是现在负责生成新的ID，一个类属性Node._index来代替的全球。
• 我用__slots__ class attribute来节省内存开销。
• 的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时，发电机需要更长的时间，但您仍然可以在一个小时左右内生成一棵满树。

您的下一个问题将是磁盘空间之一。例如，一个包含约80亿个节点（平均情况）的CSV文件应该只需要250GB的存储空间。但是，可能的话，您最多可以生成1.111万亿个节点，从而生成一个62TB的CSV文件。

Answer 2

另一个深度优先，基于生成器的解决方案...

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