火车路线的字典最佳数据结构? [英] Dictionary best data structure for train routes?

问题描述

所以我的任务是读取一个文件(记事本文件)，该文件有一堆火车停靠点以及从一个停靠点到另一个停靠点所需的时间.例如它看起来像:

So I've been tasked with essentially reading in a file (notepad file) that has a bunch of train stops and the time it takes to get from one stop to another. For example it would look like:

Stop A     15
Stop B     12
Stop C     9

现在我需要返回并访问这些站点及其时间.我正在考虑读取文件并将其存储为字典.我的问题是，字典是最好的吗?或者有没有其他一些更有用的python工具?任何想法将不胜感激！

Now I need to go back and access these stops and their times. I was thinking of reading in the file and storing it as a dictionary. My question is, would a dictionary be the best for this? Or is there some other python tool that would prove more useful? Any thoughts would be appreciated!

推荐答案

我会反对——并说直接的扁平 dict 不是最好的.

I will go against the grain -- and say that a straight flat dict is not the best for this.

假设您有 100 个停靠点和多条非字母和非数字的路线.想想巴黎地铁:

Let's say you have 100 stops and multiple routes that are non-alphabetical and non-numeric. Think the Paris subway:

现在尝试使用直接的 Python dict 来计算 FDR 和 La Fourche 之间的时间?这涉及两条或更多条不同的路线和多种选择.

Now try and use a straight Python dict to calculate the time between FDR and La Fourche? That involves two or more different routes and multiple options.

树 或某种形式的 graph 是更好的结构.对于 1 到 1 的映射，dict 非常棒；树更适合对相互关联的节点进行丰富的描述.然后，您可以使用诸如 Dijkstra 算法 之类的东西来导航它.

A tree or some form of graph is a better structure. A dict is fabulous for a 1 to 1 mapping; tree are better for a rich description of nodes that relate to each other. You would then use something like Dijkstra's Algorithm to navigate it.

因为嵌套字典或列表字典是一个图，很容易想出一个递归的例子:

Since a nested dict of dicts or dict of lists IS a graph, it is easy to come up with a recursive example:

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths       

def min_path(graph, start, end):
    paths=find_all_paths(graph,start,end)
    mt=10**99
    mpath=[]
    print '	All paths:',paths
    for path in paths:
        t=sum(graph[i][j] for i,j in zip(path,path[1::]))
        print '		evaluating:',path, t
        if t<mt: 
            mt=t
            mpath=path

    e1=' '.join('{}->{}:{}'.format(i,j,graph[i][j]) for i,j in zip(mpath,mpath[1::]))
    e2=str(sum(graph[i][j] for i,j in zip(mpath,mpath[1::])))
    print 'Best path: '+e1+'   Total: '+e2+'
'  

if __name__ == "__main__":
    graph = {'A': {'B':5, 'C':4},
             'B': {'C':3, 'D':10},
             'C': {'D':12},
             'D': {'C':5, 'E':9},
             'E': {'F':8},
             'F': {'C':7}}
    min_path(graph,'A','E')
    min_path(graph,'A','D')
    min_path(graph,'A','F')

打印:

    All paths: [['A', 'C', 'D', 'E'], ['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'D', 'E']]
        evaluating: ['A', 'C', 'D', 'E'] 25
        evaluating: ['A', 'B', 'C', 'D', 'E'] 29
        evaluating: ['A', 'B', 'D', 'E'] 24
Best path: A->B:5 B->D:10 D->E:9   Total: 24

    All paths: [['A', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'D']]
        evaluating: ['A', 'C', 'D'] 16
        evaluating: ['A', 'B', 'C', 'D'] 20
        evaluating: ['A', 'B', 'D'] 15
Best path: A->B:5 B->D:10   Total: 15

    All paths: [['A', 'C', 'D', 'E', 'F'], ['A', 'B', 'C', 'D', 'E', 'F'], ['A', 'B', 'D', 'E', 'F']]
        evaluating: ['A', 'C', 'D', 'E', 'F'] 33
        evaluating: ['A', 'B', 'C', 'D', 'E', 'F'] 37
        evaluating: ['A', 'B', 'D', 'E', 'F'] 32
Best path: A->B:5 B->D:10 D->E:9 E->F:8   Total: 32

这篇关于火车路线的字典最佳数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！