Python - Fastest way to find the average value over entire dict each time it gets modified?

Question

I'm trying to find the fastest/most efficient way to extract the average value from a dict. The task I'm working on requires that it do this thousands of times, so simply iterating over all the values in the dict each time to find the average would be entirely inefficient. Hundreds and hundreds of new key,value pairs get added to the dict and we need to find the average value each time this occurs. We also need to find the new average value each time a value gets updated, which occurs thousands of times.

Thanks in advance--this is such an awesome place.

Answer 1

Create your own dict subclass that tracks the count and total, and then can quickly return the average:

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