3

因此，我的任务基本上是读取一个文件（记事本文件），其中包含一堆火车停靠站以及从一个站点到另一个站点所需的时间。例如，它看起来像：

Stop A     15
Stop B     12
Stop C     9

现在我需要回去访问这些站点及其时间。我正在考虑读取文件并将其存储为字典。我的问题是，字典会是最好的吗？还是有其他一些 python 工具会被证明更有用？任何想法将不胜感激！

4

6 回答 6

10

我会反对这一点 - 并说平直的字典不是最好的。

假设您有 100 个站点和多条非字母和非数字的路线。想想巴黎地铁：

巴黎地铁

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

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

由于dicts 的嵌套 dict 或列表的 dict是一个图，因此很容易提出一个递归示例：

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 '\tAll paths:',paths
    for path in paths:
        t=sum(graph[i][j] for i,j in zip(path,path[1::]))
        print '\t\tevaluating:',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+'\n'  

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
于 2013-03-20T21:03:18.070 回答
2

字典完全适合查找特定站点的值。但是，这不会存储有关停止顺序的任何信息，因此无论如何您可能都需要一个单独的列表。我假设这些时间只是相邻停靠点之间的延迟，因此如果您需要计算在任意对停靠点之间到达的总时间，您实际上可能会发现 2 元组列表比列表和字典更方便：

train_times = [("A", 0), ("B", 15), ("C", 12), ("D", 9)]

注意：第一次可能总是为零，因为没有以前的停止时间。或者，您可以将最后时间设为零并将值存储在上一站的位置，但我在这里假设了第一种情况。

这使您可以非常简单地计算从 A 到 C 的总时间：

def get_total_time(start_stop, end_stop):
    total_time = None
    for stop, this_time in train_times:
        if total_time is None and stop == start_stop:
            total_time = 0
        if total_time is not None:
            total_time += this_time
            if stop == end_stop:
                return total_time
    raise Exception("stop not found")

print "Time from A to C: %d" % (get_total_time("A", "C"),)

结合列表和字典可以提高效率，但除非列表很长（至少数百个站点），否则不会有太大区别。

此外，一旦您引入许多相互连接的火车线路，事情就会变得更加复杂。在这种情况下，您可以使用任意数量的数据结构 - 一个简单的示例是字典，其中键是停靠点，值是所有行上相邻停靠点的列表以及它们的时间。但是，通过此找到一条路线需要一些稍微不平凡（但非常知名）的算法，这些算法超出了这个问题的范围。

在任何一种情况下，如果您需要快速查找这些值，您可以考虑预先计算所有停靠点对之间的时间 - 这被称为图的传递闭包（其中“图”在这种意义上是一个节点网络，而不是折线图或类似图表）。

于 2013-03-20T21:04:03.467 回答
1

在这种情况下，dict 是完全可以接受的。事实上，如果您无法使用数据库，并且您有兴趣在将来重用此字典，则可以腌制该对象并在另一个脚本中使用它：

import pickle

output = open('my_pickled_dict', 'wb')
pickle.dumb(my_dict, output)
output.close

然后在你的下一个脚本中：

import pickle

my_pickled_file = open('my_pickled_dict', 'rb')
my_dict = pickle.load(my_pickled_file)
于 2013-03-20T20:54:53.180 回答
1

一本字典可能对此有好处，是的。但是，如果您需要跟踪旁边的停靠点，您可能需要其他东西，例如有序的 dict，或者定义下一个停靠点的小类（以及您想要保留的任何其他数据）关于停止），甚至是停止列表，因为它保持顺序。

根据您需要什么样的访问权限或您希望如何处理这些数据，其中任何一个都可能适合您。

祝你好运。

于 2013-03-20T20:55:28.740 回答
0

字典适合这样做。

它使您可以轻松访问给定巴士站（= 键）的时间（= 值）。

time_per_stop = {"Stop A": 15, "Stop B": 12, "Stop C": 9}

当然，如果您的公交车站数量有限且数量很少，您也可以只保留停车时间的列表或元组。

time_per_stop_list = [15, 12, 9]
于 2013-03-20T20:55:26.727 回答
0

字典是由一组键的散列存储的一组值。使用字典的优点是定位特定记录所需的时间是固定的（通常称为O(1)），而不管大小如何。或者，如果您使用列表，则定位记录所需的时间将等于读取每个元素所需的时间（通常称为O(n)其中 n 等于列表中元素的数量）。

于 2013-03-20T20:55:56.350 回答