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

Dan Schmidt dfan at dfan.org
Tue Feb 11 20:04:17 CET 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