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 TB信息。

在我们解决这个问题之前，我首先要指出我已经改变了一些东西：

  • 该类Node现在负责生成新的 id，使用类属性Node._index而不是全局属性。
  • 我使用__slots__类属性来节省内存开销。
  • write_rootsand函数返回它们生成的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 文件。

于 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 回答