[poll] anyone else needs fast random element access off a dictionary?
fuf at mageo.cz
Wed Feb 12 09:03:23 CET 2003
actually you can't update the list in O(1) time because of its internal
working. by updating i do not only mean changing a value already stored
in it but also removing a value off it:
afaik, when an item is removed from a list all items that are "behind"
the one being removed are moved one place "forward" (to allow for O(1)
item lookup), so again in a worst case scenario (when you always remove
from the beginning of the list) you have O(N) time.
but okay, it seems nobody else needs random element access from a
Dan Schmidt wrote:
>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.
fuf (fuf at mageo.cz)
More information about the Python-list