火車路線的字典最佳數據結構？

Question

所以我一直負責基本上閱讀一個文件（記事本文件），有一堆火車站和從一站到另一站所需的時間。例如，它看起來像：

Stop A  15 
Stop B  12 
Stop C  9 

現在我需要回去訪問這些站點和他們的時間。我正在考慮閱讀文件並將其存儲爲字典。我的問題是，字典會是最好的嗎？還是有一些其他的Python工具可以證明更有用？任何想法，將不勝感激！

Answer 1

我會反對穀物 - 並說，一個平直的字典不是最好的。

假設您有100個停靠站和多個非字母和非數字路線。認爲巴黎地鐵：

現在嘗試和使用簡單的Python字典來計算FDR和La福什之間的時間？這涉及兩個或更多不同的路線和多個選項。

A tree或某種形式的graph是一個更好的結構。字典對於1比1的映射來說很棒;樹更好地描述彼此相關的節點。然後，您將使用類似Dijkstra's Algorithm的東西來導航它。

由於nested dict of dicts or dict of lists是曲線圖，它很容易想出一個遞歸例如：

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 

Answer 2

在這種情況下，字典是完全可以接受的。事實上，如果數據庫是不可用的給你，你有興趣在未來重複使用這本字典，你可以酸洗對象，並在另一個腳本中使用它：

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) 

Answer 3

字典適合做這個。

它可以讓您輕鬆訪問給定公交車站點（=鍵）的時間（=值）。

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

當然，如果你有一個有限和少量的巴士站，你也可以只保留一個列表或停止時間的元組。

time_per_stop_list = [15, 12, 9] 

Answer 4

字典可以很好，這是的。但是，如果您需要跟蹤旁邊停止的情況，您可能需要其他的東西，比如ordered dict，或者是一個定義下一個的Stop類的小類（以及任何其他您希望保留的數據停止），甚至停止列表，因爲它保持訂單。

根據您需要的訪問類型或您希望對此數據執行的操作，其中任何一種都可以爲您工作。

祝你好運。

Answer 5

字典是一組由一組密鑰存儲的值。使用字典的好處是無論大小是否固定（通常稱爲O(1)），查找特定記錄所需的時間。或者，如果您使用了列表，則查找記錄所需的時間將等於讀取每個元素所需的時間（通常稱爲O(n)，其中n等於列表中元素的數量）。

Answer 6

字典是完全適合用於查找值要特別停下來。但是，這並不存儲任何有關停靠點順序的信息，因此您可能需要一個單獨的列表。我假設這些時間只是相鄰站點之間的延遲，所以如果您需要計算任意一對站點之間的總時間，則實際上可能會找到比列表和詞典更方便的2元組列表：

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

注意：第一次總是假設爲零，因爲沒有以前的停止時間。或者，您可以將最終時間設爲零，並將值存儲在前一站中，但我在此假設了第一個案例。

這可以讓你從一個相當簡單的計算的總時間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"),) 

這可能更有效率相結合的列表和一本字典，但它並沒有多大區別，除非該名單非常長（至少有數百個站點）。

另外，一旦你引入了很多相互連接的列車線路，情況就會變得更加複雜。在這種情況下，您可以使用任意數量的數據結構 - 一個簡單的例子就是一個字典，其中關鍵是停止，值是所有行上相鄰停靠點的列表以及它們的時間。但是，通過這種方法尋找路線需要一些稍微不重要的（但非常知名的）算法，這超出了這個問題的範圍。

在任何一種情況下，如果您需要快速查找這些值，可以考慮預先計算所有停止對之間的時間 - 這被稱爲圖的transitive closure（其中「圖」在這個意義上是網絡的節點，而不是折線圖或類似的）。