提高Python中BFS的性能

Question

如何提高以下Python代码的速度性能？

我的代码可以处理少量数据，但是当我放置大量数据时，它会停止。

一些约束如下：

1）要解决的问题：检查两个节点之间的距离是否小于max_distance

2）我必须导入格式类似的.txt文件

1,2

1,3

2,3

...

3）我无法导入模块或库，例如Selection。 （仅使用Python的基本语法）

任何人都可以给我建议以改善我的代码吗？

谢谢您的帮助。

class Graph:
    def __init__(self, filename):
        self.filename = filename

    def file_to_graph(self):
        g = {}
        with open(self.filename) as f:
            for line in f:
                (key, val) = line.split(',')
                if val[-1] == '\n':
                    val = val[:-1]
                if key in g:
                    g[key].append(val)
                else:
                    g[key] = [val]
        return g

    def check_distance(self, x, y, max_distance):    
        def path(x, y):
            graph = self.file_to_graph()
            start = str(x)
            end = str(y)
            queue = []
            queue.append([start])
            while queue:
                path = queue.pop(0) 
                node = path[-1]
                if node == end:
                    return path
                for adjacent in graph.get(node, []):
                    new_path = list(path)
                    new_path.append(adjacent)
                    queue.append(new_path)        
        p = path(x, y)
        if p == None:
            return False
        elif len(p)-1 <= max_distance:
            return True
        else:
            return False

Answer 1

多个指针：

1. 如果您多次调用检查距离，则必须重新创建图形
2. 在python中的标准列表上调用queue.pop(0)效率低下，请使用collections模块中的deque之类的东西

您可以尝试

from collections import deque

class Graph:
    def __init__(self, filename):
        self.filename = filename
        self.graph = self.file_to_graph()

    def file_to_graph(self):
        graph = {}
        with open(self.filename) as input_data:
            for line in input_data:
                key, val = line.strip().split(',')
                graph[key] = graph.get(key, []) + [val]
        return graph

    def check_distance(self, x, y, max_distance):          
        path = self.path(x, y)
        if path == None:
            return False
        else:
            return len(path) - 1 <= max_distance

    def path(self, x, y):
        start, end = str(x), str(y)
        queue = deque([start])
        while queue:
            path = queue.popleft()
            node = path[-1]
            if node == end:
                return path
            for adjacent in graph.get(node, []):
                new_path = list(path)
                new_path.append(adjacent)
                queue.append(new_path)