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

[Michal Vitecek]

 hello Dan,

 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
 dictionary.

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.
>
>Dan

-- 
		fuf		(fuf at mageo.cz)