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

[David Eppstein]

In article <mailman.1045037156.22685.python-list at python.org>,
 Michal Vitecek <fuf at mageo.cz> wrote:

>  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:

Use lazy deletion from the list -- replace the value you want to remove 
by "None" (an O(1) operation), keep a count of how many removed 
positions there are, and keep an index to a position in the array that 
is less than or equal to the first nonempty item.  When you want to find 
a nonempty item, increment the index until it points to one.  When the 
count of removed items gets too large, replace the list by a compacted 
one in which all the removed items are actually removed.
Result: constant amortized time per operation.

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/