[poll] anyone else needs fast random element access off a dictionary?

Skip Montanaro skip at pobox.com
Tue Feb 11 17:57:37 CET 2003


    Michal>  currently one can get a random key stored in a dictionary
    Michal>  object like this:

    Michal>     random.choice(dict.keys())

    Michal>  the same goes for a random value stored in a dictionary:

    Michal>     random.choice(dict.values())

    Michal>  both those methods have one big drawback - they create a list
    Michal>  of either keys or values each time a random element is needed

Why not wrap your code in a class, then cache dict.keys()?  Only update the
cached copy if the dictionary is modified.  Something like this untested
code:

    class KDict(UserDict.UserDict):
        def __init__(self, *args):
            UserDict.UserDict.__init__(self, *args)
            self._updatekeys()

        def _updatekeys(self):
            self._keys = UserDict.UserDict.keys(self)

        def keys(self):
            return self._keys

        def __delitem__(self, key):
            UserDict.UserDict.__delitem__(self, key)
            self._updatekeys()

        def __setitem__(self, key, value):
            UserDict.UserDict.__setitem__(self, key, value)
            self._updatekeys()

        def setdefault(self, key, value=None):
            UserDict.UserDict.setdefault(self, key, value)
            self._updatekeys()

        def popitem(self):
            item = UserDict.UserDict.popitem(self)
            self._updatekeys()
            return item

        def clear(self):
            userDict.UserDict.clear(self)
            self._updatekeys()

The above should work unless the cost of storing an extra copy of your
dictionary's keys is overwhelming (in which case you probably have other
memory-related issues to consider).

Skip






More information about the Python-list mailing list