Inversion de dictionnaire sur place en Python

Question

J'ai besoin d'inverser un dictionnaire de listes, je ne sais pas comment l'expliquer exactement en anglais, alors voici un code qui fait ce que je veux. Cela prend juste trop de mémoire.

def invert(oldDict): 
    invertedDict = {} 
    for key,valuelist in oldDict.iteritems(): 
     for value in valuelist: 
      try: 
       entry = invertedDict[value] 
       if key not in entry: 
        entry.append(key) 
      except KeyError: 
       invertedDict[value] = [key] 
    return invertedDict 

L'original est une liste de listes, et le résultat est une liste de listes. Cela "l'inverse".

test = {} 
test[1] = [1999,2000,2001] 
test[2] = [440,441] 
test[3] = [440,2000] 

print invert(test) 

Cela donne:

{2000: [1, 3], 2001: [1], 440: [2, 3], 441: [2], 1999: [1]} 

Je dois savoir si cela peut être fait en place, parce que ma stratégie actuelle dépasse la quantité de mémoire physique sur ma machine avec le dictionnaire, je travaille avec. Pouvez-vous penser à un moyen de le faire avec des générateurs?

Answer 1

Cela ne fait pas en place, mais consomme oldDict en utilisant popitem()

from collections import defaultdict 
def invert(oldDict): 
    invertedDict = defaultdict(list) 
    while oldDict: 
     key, valuelist = oldDict.popitem() 
     for value in valuelist: 
      invertedDict[value].append(key) 
    return invertedDict 

J'ai le sentiment que dict de ne sont jamais redimensionnées à moins que la taille augmente, de sorte que vous devrez peut-être ajouter + supprimer un article factice périodiquement. Voir Shrinkage rate

from collections import defaultdict 
def invert(oldDict): 
    invertedDict = defaultdict(list) 
    i=0 
    while oldDict: 
     key, valuelist = oldDict.popitem() 
     for value in valuelist: 
      invertedDict[value].append(key) 
     i+=1 
     if i%1000==0: # allow the dict to release memory from time to time 
      oldDict[None]=None 
      del oldDict[None] 
    return invertedDict 

Answer 2

fait, je ne vois pas comment l'utilisation de la mémoire de votre algorithme actuel pourrait être considérablement amélioré. Vous utilisez des itérateurs plutôt que de créer de nouvelles listes/dicts, donc la seule utilisation significative de mémoire vient du dictionnaire original et du nouveau dictionnaire inversé.

Si vous n'avez pas assez de RAM pour exécuter cet algorithme avec le dictionnaire que vous utilisez actuellement, tout ce que je peux penser est d'éviter en quelque sorte de garder en même temps le dict original et le dict inversé en mémoire. Une façon de le faire serait de supprimer des éléments de la dict originale que vous les ajoutez à la dict inversée, ce qui pourrait être fait comme ceci:

def invert(old_dict): 
    inverted = collections.defaultdict(list) 
    while old_dict: 
     k,v = old_dict.popitem() 
     for vi in v: 
      inverted[vi].append(k) 
    return inverted 

(avis que j'ai aussi utilisé defaultdict pour simplifier le code, mais si vous avez vraiment besoin d'un dict pur, pas une sous-classe, vous pourriez faire quelque chose comme ce que vous aviez à l'origine avec le try/except)

Si vous voulez conserver les deux dictionnaires originaux et renversez disponible après l'algorithme est terminé, tout ce que je peut penser à est de les stocker dans des fichiers de disque, et de trouver un moyen de ne charger qu'une seule pièce à la fois. Je ne connais pas de module Python standard capable de stocker un dict sur le disque et de n'en charger qu'une partie à la fois, vous devrez donc écrire votre propre code pour cela.

Answer 3

Je n'ai pas de réponse directe. Voici une partie de ma pensée.

1. Je pense que ce que vous voulez faire peut être appelé Inverted index

2. Je ne crois pas que cela puisse être fait en place, et je ne pense que c'est la bonne stratégie. Vous devriez regarder la solution basée sur le disque. Peut-être trier ou organiser votre structure de données d'origine, l'écrire dans un ou plusieurs fichiers, puis le relire et les fusionner dans votre structure de données finale.

Answer 4

Il faut probablement plusieurs millions d'entrées pour manquer de RAM sur une machine moderne si l'algorithme est correct.En supposant cela, vous devez utiliser un stockage persistant pour que les données ne traitent que des segments à la fois. Pourquoi ne pas utiliser une table de base de données simple avec 2 colonnes pour stocker le dict?

key value 
1 1999 
1 2000 
1 2001 
2 440 
2 441 
... 

Ensuite, vous pouvez utiliser la colonne comme une clé en sélectionnant avec order by sur la colonne nécessaire et le regroupement des valeurs d'autres colonnes avec le code python simple.