python cache dictionary - counting number of hits

Question

I'm implementing a caching service in python. I'm using a simple dictionary so far. What I'd like to do is to count number of hits (number of times when a stored value was retrieved by the key). Python builtin dict has no such possibility (as far as I know). I searched through 'python dictionary count' and found Counter (also on stackoverflow), but this doesn't satisfy my requirements I guess. I don't need to count what already exists. I need to increment something that come from the outside. And I think that storing another dictionary with hits counting only is not the best data structure I can get :)

Do you have any ideas how to do it efficiently?

Answer 1

Having another dictionary to store the hit counts is probably not a bad option, but you could also do something like:

class CacheService(object):

    def __init__(self):
        self.data = {}

    def __setitem__(self, key, item):
        self.data[key] = [item, 0]

    def __getitem__(self, key):
        value = self.data[key]
        value[1] += 1
        return value[0]

    def getcount(self, key):
        return self.data[key][1]

You can use it something like this:

>>> cs = CacheService()
>>> cs[1] = 'one'
>>> cs[2] = 'two'
>>> print cs.getcount(1)
0
>>> cs[1]
'one'
>>> print cs.getcount(1)
1

Answer 2

For an alternative method, if you're using Python 3 (or are willing to add this module to your Python 2 project, which has a slightly different interface), I strongly recommend the lru_cache decorator.

See the docs here. For example, this code :

from functools import lru_cache

@lru_cache(maxsize=32)
def meth(a, b):
    print("Taking some time", a, b)
    return a + b

print(meth(2, 3))
print(meth(2, 4))
print(meth(2, 3))

...will output :

Taking some time 2 3
5
Taking some time 2 4
6
5   <--- Notice that this function result is cached

As per the documentation, you can get the number of hits and misses with meth.cache_info(), and clear the cache with meth.cache_clear().

Answer 3

You can subclass a built-in dict class:

class CustomDict(dict):
    def __init__(self, *args, **kwargs):
        self.hits = {}
        super(CustomDict, self).__init__(*args, **kwargs)

    def __getitem__(self, key):
        if key not in self.hits:
            self.hits[key] = 0
        self.hits[key] += 1
        return super(CustomDict, self).__getitem__(key)

usage:

>>> d = CustomDict()
>>> d["test"] = "test"
>>> d["test"]
'test'
>>> d["test"]
'test'
>>> d.hits["test"]
2

Answer 4

It will be much easier to just overload the built-in dict data type. This will solve your problem.

def CountDict(dict):
    count = {}

    def __getitem__(self, key):
        CountDict.count[key] = CountDict.count.get(key, 0) + 1
        return super(CountDict, self).__getitem__(self, key)

    def __setitem__(self, key, value):
        return super(CountDict, self).__setitem__(self, key, value)

    def get_count(self, key):
        return CountDict.count.get(key, 0)

This will give you lot more flexibility. Like you can have two counts one for number of reads and another for number of writes, if you wish without much of a complexity. To learn more about super, see here.

Edited to meet OP's need of keeping a count for reading a key. The output can be obtained by calling get_count method.

>>>my_dict = CountDict()
>>>my_dict["a"] = 1
>>>my_dict["a"]
>>>1
>>>my_dict["a"]
>>>1
>>>my_dict.get_count("a")
>>>2

Answer 5

You could try this approach.

class AccessCounter(object):
'''A class that contains a value and implements an access counter.
The counter increments each time the value is changed.'''

def __init__(self, val):
    super(AccessCounter, self).__setattr__('counter', 0)
    super(AccessCounter, self).__setattr__('value', val)

def __setattr__(self, name, value):
    if name == 'value':
        super(AccessCounter, self).__setattr__('counter', self.counter + 1)
    # Make this unconditional.
    # If you want to prevent other attributes to be set, raise AttributeError(name)
    super(AccessCounter, self).__setattr__(name, value)

def __delattr__(self, name):
    if name == 'value':
        super(AccessCounter, self).__setattr__('counter', self.counter + 1)
    super(AccessCounter, self).__delattr__(name)

Answer 6

DISCLAIMER: I'm the author of kids.cache

You might want to check kids.cache which is a simple library that uses dict by default as caching store, and will return cache statistics which includes hits and misses.

Example

>>> from kids.cache import cache

>>> @cache
... def meth(a, b):
...     print("Taking some time", a, b)
...     return a + b

One miss and a hit:

>>> meth(1, 2)        ## Miss !
Taking some time 1 2
3
>>> meth(1, 2)        ## Hit !
3

Let's add a miss:

>>> meth(1, 3)        ## Miss !
Taking some time 1 2
4

And now let's ask for the cache info:

>>> meth.cache_info()
CacheInfo(type='dict', hits=1, misses=2, maxsize=None, currsize=2)

To go further

You could check the source code of kids.cache to see how the caching info is implemented. Note that it does NOT store the statistic inside the cache store. It's the cache function that holds the value.

I believe this is the cleanest way as it allows you to use wide variation of cache stores (and some as simple as the good old dict) without having to implement the caching stats function in each of them. This last idea comes from Thomas Kemmer who wrote the excellent cachetools.

You could probably also use out of the box kids.cache which has extensive docs. It has no dependency, is only one file, work on python2 and python3, is straightforward to use, while allowing also complex caching if necessary.