Dan Schmidt dfan at dfan.org
Tue Feb 11 14:04:17 EST 2003

• Previous message (by thread): [poll] anyone else needs fast random element access off a dictionary?
• Next message (by thread): [poll] anyone else needs fast random element access off a dictionary?
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

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

---

• Previous message (by thread): [poll] anyone else needs fast random element access off a dictionary?
• Next message (by thread): [poll] anyone else needs fast random element access off a dictionary?
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

More information about the Python-list mailing list