如何从字典词典中删除所有项目的发生？

我有一本字典的字典。密钥是图中的节点。例如，让我们假设图中的节点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

如何从字典词典中删除所有项目的发生？

回答

相关问题