このPythonコードの代わりに？

Question

私は完全に理解していないクラスのコード行を持っています。これは、お互いに接続されている辺のリストであるweightListを使用し、グラフから対応する値が最も低いエッジグリッド（隣接行列）を返します。これは、プリムの最小スパニングツリーの問題です。

edge = sorted(weightList, key=lambda e:graph[e[0]][e[1]])[0];

Answer 1

少しそれを打破することは十分に可能性があります。これはどう？

get_edge_weight = lambda e: graph[e[0]][e[1]] 
sorted_weights = sorted(weightList, key=get_edge_weight) 
edge = sorted_weights[0] 

Answer 2

すべてのエッジについて、最も低いグラフの値を見つけます。

i, j = current_edge = weightList[0] 
current_min = graph[i][j] 

for edge in weightList[1:]: 
    i, j = edge 

    if graph[i][j] < current_min: 
     current_min = graph[i][j] 
     current_edge = edge 

あなたはweightListからの最初のエッジで開始し、その後は低い値を試してみて、見つけるために、他のすべてのエッジに繰り返します。ループを終了すると、current_edgeが最小値のエッジになります。

あなたのコードを試して理解する価値があると言われています。私はあなたがsortedが何をしているかを知っていると仮定します。 weightListをソートするには、sortedはパラメータkeyを使用します。これは値を返す関数です。あなたの場合、関数は、あなたの端の位置にの値を返します。 sortedはこの値を使用してエッジを一緒に比較します。

このように、これにより、値が最も小さいものから最も高い値のものにすべてのエッジがソートされます。次にソートされると、最も低い値のエッジである最初の要素を取得します。

アルゴリズムでは、sortedをこのジョブに使用することは、時間複雑度がO(n log n)であるため、アルゴリズムとしてはお勧めできません。比較すると、私のアルゴリズムはO(n)です（ただし、sortedがC言語で実装されていると仮定しているため、おそらく低速です）。あなたはコードが少し小さい「コンパクトにしたい場合は

edge = min(weightList, key=lambda (i,j): graph[i][j]) 

Answer 3

：代わりに、あなたは確かにすべての3つのうち最も効率的で読みやすいオプションである、minを使用して標準機能を使用してO(n)で同じ結果を得ることができますweightListでの最初のエッジに等しくなるように最短エッジを設定し

shortest = weightList[0] 

for edge in weightList: 
    if graph[edge[0]][edge[1]] < graph[shortest[0]][shortest[1]]: 
     shortest = edge 

は、そのリストを通過し、任意のエッジが短い場合は以下を参照してください」、これはトリックを行う必要があります。

Answer 4

複雑さを軽減しようとすると、私はいつも自明に物事を打破する方法を探し、モジュラー機能：

def distance(adjacency_matrix, start_node, end_node): 
    return adjacency_matrix[start_node][end_node] 

sorted_edges = sorted(weightList, key=lambda e: distance(graph, e[0], e[1])) 
edge = sorted_edges[0];