[poll] anyone else needs fast random element access off a dictionary?
Dan Schmidt
dfan at dfan.org
Tue Feb 11 14:04:17 EST 2003
Michal Vitecek <fuf at mageo.cz> writes:
| hello Skip,
|
| this is not possible because the data in the dictionary are very often
| changed -> in the worst case scenario the cached keys would have to be
| regenerated each time a distinct data is generated.
Yeah, but you can update the list in O(1) time, rather than calling
keys() every time the dict changes.
The dictionary is a mapping of key to a (value, list index) tuple,
where the list index is where that key is stored in the parallel list.
When you delete a key, you look up the appropriate list index, swap
the last element into it, and update the previously last element's
list index in the dict.
Dan
--
http://www.dfan.org
More information about the Python-list
mailing list