[poll] anyone else needs fast random element access off a dictionary?
Skip Montanaro
skip at pobox.com
Tue Feb 11 11:57:37 EST 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