Python - Le moyen le plus rapide de trouver la valeur moyenne sur toute dict chaque fois qu'il est modifié?

Question

J'essaie de trouver le moyen le plus rapide/le plus efficace d'extraire la valeur moyenne d'un dict. La tâche sur laquelle je travaille exige que cela se fasse des milliers de fois, donc il suffit d'itérer sur toutes les valeurs de la dict pour trouver la moyenne qui serait totalement inefficace. Des centaines et des centaines de nouvelles paires valeur/clé sont ajoutées à la dict et nous devons trouver la valeur moyenne chaque fois que cela se produit. Nous devons également trouver la nouvelle valeur moyenne chaque fois qu'une valeur est mise à jour, ce qui se produit des milliers de fois.

Merci d'avance - c'est un endroit génial.

Answer 1

Créer votre propre sous-classe dict qui suit le nombre et le total, puis peut revenir rapidement à la moyenne:

class AvgDict(dict): 
    def __init__(self): 
     self._total = 0.0 
     self._count = 0 

    def __setitem__(self, k, v): 
     if k in self: 
      self._total -= self[k] 
      self._count -= 1 
     dict.__setitem__(self, k, v) 
     self._total += v 
     self._count += 1 

    def __delitem__(self, k): 
     v = self[k] 
     dict.__delitem__(self, k) 
     self._total -= v 
     self._count -= 1 

    def average(self): 
     if self._count: 
      return self._total/self._count 

a = AvgDict() 
assert a.average() is None 
a[1] = 1 
assert a.average() == 1 
a[2] = 10 
assert a.average() == 5.5 
assert a[2] == 10 
a[1] = 5 
assert a.average() == 7.5 
del a[1] 
assert a.average() == 10 

Answer 2

Hérite de dict et de calculer la valeur moyenne chaque fois que __setitem__ est appelée. Étant donné que vous pouvez stocker la moyenne précédente dans votre classe de dictionnaire et ne faire que la moyenne et la nouvelle valeur ajoutée, cela devrait être rapide - la première fois qu'un nouvel élément est ajouté, la valeur moyenne est simplement celle de cette valeur.

Answer 3

Ce qui suit est basée sur la moyenne en cours d'exécution, donc si vous connaissez la moyenne précédente:

At = (A0 * N + E)/(N + 1) 

At is the average after addition of the new element 
A0 is the average before addition of the new element 
N is the number of element before addition of the new element 
E is the new element's value 

Son frère plus simple fonctionne si vous gardez l'onglet de la somme des éléments:

At = (T + E)/(N + 1) 

T is the total of all elements 
A0 is the average before addition of the new element 
N is the number of element before addition of the new element 
E is the new element's value 

Lorsque une valeur est supprimée, vous pouvez faire une chose semblable:

At = (A0 * N - E)/(N - 1) 

Et quand une valeur est mise à jour:

At = (A0 * N - E0 + E1)/(N) 

E0 is value before updating, E1 is value after updating.