Comment supprimer toutes les occurrences d'un élément d'un dictionnaire de dictionnaire?

Question

J'ai un dictionnaire de dictionnaire. Les clés sont les noeuds dans un graphique. Par exemple, supposons que le nœud i du graphique est représenté par une clé i dans le dictionnaire. La valeur correspondant à cette clé est à nouveau un dictionnaire où les clés sont les voisins du nœud i dans le graphique. Ces clés ont une valeur par défaut 1. Considérons les exemple- suivants

Les nœuds du graphe sont - [1,2,3,4,5,6]

voisins:

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

2->[3] 

3->[4,6] 

4->[1,6] 

5->[1] 

6->[1,3,4] 

Ainsi, le dictionnaire du dictionnaire ressemble à ceci:

{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}} 

maintenant, à différentes étapes de l'algorithme que je suis en train de mettre en œuvre, je dois supprimer toutes les occurrences d'un nœud x dans la liste voisine d'un autre noeud s. Si x = 4, puis après la suppression, le dictionnaire du dictionnaire devrait ressembler à ceci:

{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}} 

J'utilise un dictionnaire de dictionnaire au lieu d'un dictionnaire de listes afin de rendre la suppression efficace. Mais c'est toujours cher.

Quel est le plus efficace de faire cela?

Answer 1

Il se peut que la structure que vous avez choisi n'est pas le plus efficace possible. Les ensembles pourraient juste faire l'affaire. Je n'ai pas très bien compris si vos connexions sont des connexions unidirectionnelles de type flèche ou des connexions bidirectionnelles. Je suppose que les connexions unidirectionnelles, comme 2 est voisine de 1, mais pas vice versa. Si c'est le cas, nous devons garder une trace de "de" et "à".

J'ai modifié votre code pour utiliser des ensembles plutôt que des dictionnaires pour des raisons d'efficacité.

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]) } 

(Bien sûr, le pointed_by peut être créé avec un petit morceau de code, je viens d'écrire ce pour montrer l'idée.)

Maintenant, si vous devez supprimer toutes les connexions et de noeud 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() 

Cela devrait être relativement rapide et simple à comprendre.

S'il n'y avait que des connexions bidirectionnelles, un dictionnaire et la moitié du code ci-dessus suffiraient.

---

Quelques mots sur la performance.

Comme on peut le voir, cette approche a une boucle très courte. Il itère uniquement à travers les connexions avec une extrémité au noeud à supprimer. A ce niveau, le nombre total de connexions n'a pas d'importance, ni le nombre total de points. Cependant, plus l'ensemble et les temps de recherche de dictionnaire ne sont pas indépendants de la taille de ces dictionnaires et ensembles. Ma conjecture est O (log n), où n est le nombre total de points ou de connexions, mais quelqu'un peut mieux connaître l'implémentation réelle.

L'utilisation d'ensembles est légèrement plus rapide que l'utilisation de dictionnaires, mais la différence est faible, car ils sont presque la même chose sous le capot. Les opérations simples ont tendance à être assez rapides. Je pense que les méthodes de recherche linéaire sont plus rapides avec de très petits ensembles de données, car elles peuvent utiliser des listes de compréhension & c. Avec des données plus importantes, cela sera plus efficace.

Answer 2

Utilisez une compréhension dictionnaire:

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

Ce dictionnaire avec votre reconstructions qui omet toutes les clés correspondant à x des dictionnaires internes.

Remplacer iteritems() pour items() en Python 3.

Démo:

>>> 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}} 

Answer 3

Ceci le fera sur place. Vous pouvez d'abord utiliser copy.deepcopy pour l'obtenir comme copie.

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}} 

Vous pouvez résumer comme une fonction d'assistance:

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