3

そのため、基本的に、多数の列車の停留所と、ある停留所から別の停留所に移動するのにかかる時間を含むファイル (メモ帳ファイル) を読み取ることを任されました。たとえば、次のようになります。

Stop A     15
Stop B     12
Stop C     9

ここで、戻ってこれらの停留所とその時間にアクセスする必要があります。ファイルを読み込んで辞書として保存することを考えていました。私の質問は、これには辞書が最適でしょうか? または、より便利であることが証明される他の python ツールはありますか? どんな考えでも大歓迎です！

4

6 に答える 6

10

私は穀物に逆らって行きます-そして、まっすぐなフラットディクテーションはこれには最適ではないと言います.

100 の停留所と、アルファベットでも数値でもない複数のルートがあるとします。パリの地下鉄を考えてみてください。

パリの地下鉄

FDR と La Fourche の間の時間を計算するために、ストレートな Python dict を使用してみてください。これには、2 つ以上の異なるルートと複数のオプションが含まれます。

ツリーまたは何らかの形式のグラフは、より優れた構造です。dict は 1 対 1 のマッピングに最適です。tree は、相互に関連するノードの詳細な説明に適しています。次に、ダイクストラのアルゴリズムのようなものを使用してナビゲートします。

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"),)

これは、リストと辞書を組み合わせてより効率的にすることができますが、リストが非常に長い場合 (少なくとも数百ストップ) でない限り、大きな違いはありません。

また、相互に接続する多くの列車路線を導入すると、事態はさらに複雑になります。この場合、任意の数のデータ構造を使用できます。簡単な例の 1 つは、キーが停車駅で、値がすべての路線の隣接する停車駅とそれらの時刻のリストである辞書です。ただし、これを介してルートを見つけるには、この質問の範囲を超えている、やや自明ではない（しかしかなりよく知られている）アルゴリズムが必要です。

どちらの場合でも、これらの値をすばやく調べる必要がある場合は、ストップのすべてのペア間の時間を事前に計算することを検討できます。これは、グラフの推移閉包として知られています (この意味での「グラフ」はノードのネットワークです)。 、折れ線グラフなどではありません)。

于 2013-03-20T21:04:03.467 に答える
1

この状況では、口述は完全に受け入れられます。実際、データベースが利用できず、将来この辞書を再利用することに興味がある場合は、オブジェクトをピクルして別のスクリプトで使用できます。

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、または次のストップを定義する Stop の小さなクラスなど、何か他のものが必要になる場合があります (および保持したいその他のデータは何でも)停車地について)、または停車地のリストでさえ、順序を保持します。

必要なアクセスの種類、またはこのデータで何をしたいかによって、これらのいずれかが機能する可能性があります。

幸運を。

于 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 に答える