기차 경로에 대한 사전 최고의 데이터 구조?

Question

그래서 열차가 멈추고 한 정류장에서 다른 정류장까지가는 데 걸리는 시간이있는 파일 (메모장 파일)을 본질적으로 읽어야 할 의무가 있습니다. 예를 들면 다음과 같습니다.

Stop A  15 
Stop B  12 
Stop C  9 

이제 이러한 중지 및 시간에 액세스해야합니다. 나는 파일을 읽고 사전으로 저장하는 것을 생각하고 있었다. 제 질문은, 사전이 가장 좋을까요? 아니면 다른 유용한 python 도구가 있습니까? 어떤 생각이라도 감사 할 것입니다!

Answer 1

나는 곡식에 맞서 갈 것이다. 그리고 곧은 편평한 dict이 이것을 위해 최선이 아니라고 말한다.

알파벳순이 아니며 숫자가 아닌 100 개의 정류장과 경로가 있다고 가정 해 보겠습니다. 이제

시도하고 FDR 라 Fourche 사이의 시간을 계산하는 직선 파이썬 딕셔너리를 사용 : 파리 지하철은 생각 하는가? 여기에는 둘 이상의 다른 경로와 여러 옵션이 포함됩니다.

tree 또는 어떤 형태의 graph이 더 나은 구조입니다. dict는 1 대 1 매핑에 대해 훌륭합니다. 트리는 서로 관련이있는 노드에 대한 풍부한 설명을 제공합니다. 그런 다음이를 탐색하기 위해 Dijkstra's Algorithm과 같은 것을 사용할 것입니다.

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

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) 

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과 같은 다른 것이 필요할 수도 있고 다음 정지를 정의하는 정지를위한 작은 클래스 (그리고 다른 어떤 데이터라도 유지하려고합니다 정지), 또는 정지의 명부조차, 순서를 지키기 때문에.

필요한 데이터 액세스 유형이나 데이터로 수행하고자하는 작업에 따라이 중 아무 것이나 사용할 수 있습니다.

행운을 빈다.

Answer 5

사전은 집합 키의 해시에 의해 저장된 값 집합입니다. 사전 사용의 장점은 크기에 관계없이 특정 레코드를 찾는 데 필요한 시간 (종종 O(1)라고 함)입니다. 또는 목록을 사용한 경우 레코드를 찾는 데 걸리는 시간은 각 요소를 읽는 데 걸리는 시간과 동일하게됩니다 (종종 O(n)이라고하며 n은 목록의 요소 수와 같습니다).

Answer 6

사전 적 A의 값을 찾는 전적으로 적합한 nested dict of dicts or dict of lists 이후

는 재귀 예를 마련하기 쉬운, 그래프 특별한 중지. 그러나 정지 순서에 관한 정보는 저장하지 않으므로 어쨌든 별도의 목록이 필요합니다. 나는이 시간이 인접한 정류장 사이의 지연이라고 가정하고 있습니다. 따라서 임의의 쌍의 정지 사이에 도달하는 총 시간을 계산해야한다면 실제로 목록과 사전보다 편리한 2-tuples 목록을 찾을 수 있습니다 :

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

참고 : 이전에 시간이 멈추지 않으므로 처음으로 항상 0이됩니다. 또는 마지막 시간을 0으로 만들고 이전 중지와 비교하여 값을 저장할 수도 있지만 여기서는 첫 번째 경우로 가정했습니다.

이는 아주 간단하게 C A에서 총 시간을 계산할 수 있습니다 :

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입니다 (여기서 "그래프"는 꺾은 선형 차트 또는 유사하지 않은 노드 네트워크).