在不冻结的情况下对大型行分隔文件进行迭代

Question

我正在尝试实现一个强连通图搜索算法，并尝试将一个带有图的边的大文件加载到内存中。你知道吗

文件如下：

1 2 // i.e. a directed edge from 1 to 2

1 3

2 3

3 1

...

对于算法的这一部分，我需要反转图形，我希望将每个节点与其他一些对算法很重要的值一起存储在字典中。你知道吗

此代码适用于较小的文件，但仅适用于我的大文件（72.7mb）的暂停/挂起，如果您有任何建议可以使其适用于大文件，我将不胜感激：

def begin():
    graph = {}
    for line in open('/home/edd91/Documents/SCC.txt'):
        tempArray = []
        for e in line.split():
            if e != ' ' and e!='\n':
                tempArray.append(int(e))            
        if tempArray[1] in graph.keys():
            graph[tempArray[1]]['g'].append(tempArray[0])
        else:
            graph[tempArray[1]] = {'g': [tempArray[0],], 's': False, 't': None, 'u': None }
    print len(graph)

Answer 1

没什么要做的，但由于有点太复杂，速度会受到影响。 您可以这样提高程序速度：

def begin():
    graph = {}
    for line in open('/home/edd91/Documents/SCC.txt'):
        # consider only first 2 fields: avoids the loop and the append: that's the best saver
        # there must not be 2 spaces between the numbers (in your original program neither so not a problem)
        tempArray = line.split()  
        v1 = tempArray[1]  # copy to get rid of array
        if v1 in graph:  # no need to use .keys()
            graph[v1]['g'].append(tempArray[0])
        else:
            graph[v1] = {'g': [tempArray[0],], 's': False, 't': None, 'u': None }
    print len(graph)

你可以先用一个中等大小的文件来比较速度和你原来的程序。你知道吗

Answer 2

当然，如果每一行都由一对数字组成，您可以通过一次为每一行获取tempArray并解包来节省一些时间，还可以使用defaultdict：

import collections

graph = collections.defaultdict(lambda: {'g': [], 's': False, 't': None, 'u': None })
for line in ... :
    k, v = map(int, line.split())
    graph[v]['g'].append(k)