如何從字典詞典中刪除所有項目的發生？

我有一本字典的字典。密鑰是圖中的節點。例如，讓我們假設圖中的節點i由字典中的密鑰i表示。與該鍵對應的值又是一個字典，其中鍵是圖中節點i的鄰居。這些鍵有默認值1。讓我們看看下面的示例 -如何從字典詞典中刪除所有項目的發生？

該圖中的節點是 - [1,2,3,4,5,6]

鄰居：

1->[2,4,5,6] 

2->[3] 

3->[4,6] 

4->[1,6] 

5->[1] 

6->[1,3,4]

所以詞典的詞典是這樣的：

{1:{2:1,4:1,5:1,6:1},2:{3:1},3:{4:1,6:1},4:{1:1,6:1},5:{1:1},6:{1:1,3:1,4:1}}

現在，在算法的不同階段，我想實現，我需要從其他節點的鄰居列表中刪除一個節點x的所有出現秒。如果x = 4，則刪除後，詞典的詞典應該是這樣的：

{1:{2:1,5:1,6:1},2:{3:1},3:{6:1},4:{1:1,6:1},5:{1:5},6:{1:1,3:1}}

我用字典的字典而不是列表的字典，使刪除效率。但它仍然是昂貴的。

這樣做的效率最高？

來源

2014-06-14 Satarupa Guha

這可能是因爲您所選擇的結構不是最有效的可能。套可能只適合賬單。

我不太明白你的連接是箭頭狀的單向連接還是雙向連接。我假設單向連接，因爲2是1的鄰居，但不是相反的。如果是這樣，我們需要跟蹤「從」和「到」。

我修改了代碼，以便使用集合而不是字典來提高效率。

pointing_to = { 
    1: set([2,4,5,6]), 
    2: set([3]), 
    3: set([4,6]), 
    4: set([1,6]), 
    5: set([1]), 
    6: set([1,3,4]) } 

pointed_by = { 
    1: set([4,5,6]), 
    2: set([1]), 
    3: set([2,6]), 
    4: set([1,3,6]), 
    5: set([1]), 
    6: set([1,3,4]) }

（當然，pointed_by可以用很短的一段代碼創建的，我只是寫出來，以顯示想法。）現在

，如果您需要刪除，並從所有連接節點tbr：

# remove tbr from pointing_to lists of all neighbours pointing to tbr 
# (connections from other nodes to tbr 
for n in pointed_by[tbr]: 
    pointing_to[n].remove(tbr) 
# after this tar is pointed by no neighbour 
pointed_by[tbr] = set() 

# repeat for opposite direction (connections from tbr to other nodes) 
for n in pointing_to[tbr]: 
    pointed_by[n].remove(tbr) 
pointing_to[tbr] = set()

這應該是相對快速和易於理解的。

如果只有雙向連接，一個字典和上面一半的代碼就足夠了。

關於表現的幾句話。

可以看出，這種方法有一個很短的循環。它只能通過節點一端的連接進行迭代才能被刪除。在該級別，連接的總數不重要，也不重要。

但是，集合和字典查找時間的深度並不獨立於這些字典和集合的大小。我的猜測是O（log n），其中n是點或連接的總數，但有人可能更好地知道實際的實現。

集合的使用比字典的使用略快，但差異很小，因爲它們幾乎與引擎蓋下面是同一個東西。簡單的設置操作往往非常快。

我的猜測是線性搜索方法對於非常小的數據集更快，因爲他們可能使用列表解析& c。數據量越大，效率越高。

來源

2014-06-14 19:32:09 DrV

我曾經保留過neighbors_of數據結構，但沒有想到使用set！謝謝。我決定改變方法，因爲我認爲在預處理階段需要做太多的工作來創建數據結構，如果圖形規模龐大，這可能會很昂貴。 –

恐怕你在內存和CPU週期數之間有一個權衡。如果您想要騰出內存，則只能存儲一次連接。如果你想快點，你可以將它們存儲兩次。創建反轉表畢竟是一個快速操作，只需很少的代碼行。（我猜如果你有幾千萬個連接，那麼你以後就不能和O（n）算法一起生活，因爲當你考慮所有的處理時，它們往往會變成O（n^2）。） – DrV

對。說得通。 –

使用字典理解：

{ok: {ik: iv for ik, iv in ov.iteritems() if ik != x} 
for ok, ov in yourdict.iteritems()}

此重建你的字典，一個省略匹配從內部字典x所有按鍵。

在Python 3.更換iteritems()爲items()

演示：

>>> yourdict = {1:{2:1,4:1,5:1,6:1},2:{3:1},3:{4:1,6:1},4:{1:1,6:1},5:{1:5},6:{1:1,3:1,4:1}} 
>>> x = 4 
>>> {ok: {ik: iv for ik, iv in ov.iteritems() if ik != x} 
... for ok, ov in yourdict.iteritems()} 
{1: {2: 1, 5: 1, 6: 1}, 2: {3: 1}, 3: {6: 1}, 4: {1: 1, 6: 1}, 5: {1: 5}, 6: {1: 1, 3: 1}}

來源

2014-06-14 19:09:27

的Martijn Pieters的我愛你。非常整潔 – yuvi

謝謝。花了我一些時間來理解它。你能否解釋一下複雜性會是什麼？ –

O（n），其中n是連接的總數，因爲它穿過內部和外部字典。這是否是一個問題很大程度上取決於n。你是什麼？ – DrV

這將在原地進行。您可以先使用copy.deepcopy將其作爲副本。

t = {1:{2:1,4:1,5:1,6:1}, 
    2:{3:1}, 
    3:{4:1,6:1}, 
    4:{1:1,6:1}, 
    5:{1:5}, 
    6:{1:1,3:1,4:1}} 

for k,v in t.iteritems(): 
    v.pop(4, None)  

print t 
{1: {2: 1, 5: 1, 6: 1}, 
2: {3: 1}, 
3: {6: 1}, 
4: {1: 1, 6: 1}, 
5: {1: 5}, 
6: {1: 1, 3: 1}}

你可以將其封裝爲一個輔助功能：

def remove_node(graph, node, inplace=True): 
    import copy 
    temp_graph = copy.deepcopy(graph) if not inplace else graph 
    for k,v in temp_graph.iteritems(): 
     v.pop(node, None) 
    return temp_graph

來源

2014-06-14 19:39:26 ely

如何從字典詞典中刪除所有項目的發生？

回答

相關問題