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

[Duncan Booth]

Michal Vitecek <fuf at mageo.cz> wrote (net of rearrangement and snipping) in 
news:mailman.1045037156.22685.python-list at python.org:
> Dan Schmidt wrote:
>>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.
>>
> 
>  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.

He was suggesting that instead of deleting an item from the end of the list 
you replace it with the element at the end of the list and drop the element 
off the end of the list. If you do it that way you do indeed get O(1) time 
to drop an element from a list. You change the order of elements in the 
list, but that isn't important here.

(Please don't top-post, it makes it a lot of work to produce appropriately 
trimmed quotes in a followup)

-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?