python - 在 python 中生成图形的高内存消耗

Question

我正在使用 python 从文件生成图表。当我运行我的代码时，它使用了大约 7 GB 的 RAM!! (该图有 1,600,00 个节点)

输入文件是这样的:

1 2
1 3
1 4
2 4

每一行代表一条边。在这个例子中，我们有 4 个节点和 4 个边。

这是我的代码:

class Graph(object):

    def __init__(self):
        self.node_list = []
        self.edge = []
        self.neighbors = {}
        with open(infile, "r") as source_file:
            for row in csv.reader(source_file, delimiter='\t'):
                self.node_list.append(int(row[0]))
                self.node_list.append(int(row[1]))
                self.edge.append(row)
        for node in self.edge:
            if node[0] in self.neighbors:
                self.neighbors[node[0]].append(node[1])
            else:
                self.neighbors[node[0]] = [node[1]]
            if node[1] in self.neighbors:
                self.neighbors[node[1]].append(node[0])
            else:
               self.neighbors[node[1]] = [node[0]]
        self.node_list = list(set(self.node_list))

g = Graph()

提前致谢。

Answer 1

您以错误的方式使用了错误的数据结构。

您的代码在节点列表中创建了大量冗余条目。使用您的示例，节点列表将是:

[1, 2, 1, 3, 1, 4, 2, 4]

当处理 1'600'000 个节点时，这将大大增加您的数据需求。然后将输入文件的完整副本存储在永远不会发布的 self.edge 中。

你甚至不需要为你正在做的事情上课:

import collections

graph = collections.defaultdict(list)
with open(infile) as inf:
    for line in inf.read():
        p, q = line.split()
        if p not in graph[q]:
            graph[q].append(p)
        if q not in graph[p]:
            graph[p].append(q)

graph 现在包含输入文件的最小表示。这是 rather old pattern效果很好。您可能会找到类似 NetworkX 的包裹如果您想对创建的图形执行任何操作，这将非常有用。