使用dict（python）中的特定鍵構建列表？

我正在Python中實現Dijkstra搜索算法。在搜索結束時，我使用前導映射重建最短路徑，從目標節點的前任開始。例如：使用dict（python）中的特定鍵構建列表？

path = [] 
path.append(destination) 
previous = predecessor_map[destination] 
while previous != origin: 
    path.append(previous) 
    previous = predecessor_map[previous]

有沒有什麼辦法可以用較少的代碼行（例如list comprehension）來做到這一點？

來源

2011-10-12 XåpplI' -I0llwlg' I -

這是非常清楚的，因爲它是。不要試圖把它作爲一個班輪來破壞它。我想你可以創建一個迭代器來產生每個前導，並使用列表理解，但這只是隱藏了邏輯。 –

你真的沒有一個列表來重複理解，所以我猜不。你的代碼很簡單，你可能完成的任何事情都將是純代碼高爾夫。 – millimoose

是我唯一的建議是擺脫輕微的重複代碼：

path = [] 
previous = destination 
while previous != origin: 
    path.append(previous) 
    previous = predecessor_map[previous]

除此之外，我覺得你的代碼其實很清楚，是不可能從任何企圖受益縮短。

最後，值得注意的是，當destination == origin時，上述方法也適用，而您的原始版本最有可能不會（取決於predecessor_map是如何填充的）。不知道這是否與你的用例有關。

來源

2011-10-12 14:36:23 NPE

@SvenMarnach：謝謝。我已經更新了我的答案以反映這一點。 – NPE

這與原始代碼有所不同，請注意，在原始返回列表中*至少有*一個元素，目的地 –

@ÓscarLópez：請參閱我的答案的最後一段。 – NPE

我不認爲你可以用理解來做這個迭代。也許你可以把它簡化一下，像這樣：

path, previous = [], destination 
    while True: 
     path.append(previous) 
     previous = predecessor_map[previous] 
     if previous == origin: 
      break

上述循環看起來與do..while更好，但是Python缺乏它

來源

2011-10-12 14:35:50

def backwalk(mymap, start, origin): 
    yield start 
    current = mymap[start] 
    while current != origin: 
     yield current 
     current = mymap[current] 

path = list(backwalk(predecessor_map, destination, origin))

這分隔了步行和收集任務。

如果你能保證你永遠不與原點開始，您可以簡化到

def backwalk(mymap, start, origin): 
    current = start 
    while current != origin: 
     yield current 
     current = mymap[current]

來源

2011-10-12 14:37:08 glglgl

如果我正在閱讀代碼，我會比這個更快地理解原始版本。 –

不是特別短，但是迭代器對於假設的可重用圖類中的客戶端來說是更好的API。 – millimoose

這可能會實現：

path = [destination] 
path += iter(lambda: predecessor_map[path[-1]], origin)

它的行爲與您的原代碼。但是你已經寫得很好。

如果destination可以等於origin：

path = [] 
path += iter(lambda: predecessor_map[path[-1]] if path else destination, origin)

它的行爲一樣@aix's code。

來源

2011-10-12 14:52:44 jfs

很好，除了你不能'+ ='iter（）'到'list'。但是如果你使用'path.extend（）'，它應該可以工作。 – glglgl

@glglgl你可以把'+ ='iter（）'變成'list'。該代碼有效。 –

哎呀，我沒有意識到這一點。我想過'[] +（）'的行爲 - 很不一致...... – glglgl

可以遞歸遍歷假設predecessor_map邊緣是dict映射節點到父節點，並且None是根：

predecessor_map={0: None, 1: None, 2: 1, 3: 1, 4: 0, 5: 1}

定義橫穿樹反向遞歸函數：

def path(node, predecessors): 
    return [None] if node is None else [node] + path(predecessors.get(node), predecessors)

或者，如果你敢，Y組合器：

在使用（使用列表理解）：

>>> print [node for node in path(None, predecessor_map)] 
[None] 
>>> print [node for node in path(0, predecessor_map)] 
[0, None] 
>>> print [node for node in path(1, predecessor_map)] 
[1, None] 
>>> print [node for node in path(2, predecessor_map)] 
[2, 1, None] 
>>> print [node for node in path(3, predecessor_map)] 
[3, 1, None] 
>>> print [node for node in path(4, predecessor_map)] 
[4, 0, None] 
>>> print [node for node in path(5, predecessor_map)] 
[5, 1, None]

來源

2011-10-12 16:02:15

還有一個可能的解決方案是使用函數編程風格與遞延輸出：

from itertools import tee, chain, imap, takewhile 

predecessor_map = {2:1, 3:2} 
destination = 3 
origin = 1 

def backwalk(predecessor_map, start, origin): 

    def deffered_output(): 
     for i in output: 
      yield i 

    result, a = tee(deffered_output()) 
    b = imap(predecessor_map.get,a) 
    output = takewhile(lambda x: x!=origin,chain([start],b)) 

    return result 

print(list(backwalk(predecessor_map,destination,origin)))

我個人不會使用這種方法。但是，這對培訓很有意思。

說明的關鍵要素是deferred_output其推遲到output呼叫。然後我們將output分成2個迭代器，使用tee。然後，我們將predecessor_map.get應用於稱爲a的第二個迭代器，並將新迭代器分配給b。然後我們用takewhile控制輸出，當達到origin時停止輸出。

來源

2011-10-12 16:15:55 ovgolovin

使用dict（python）中的特定鍵構建列表？

回答

相關問題