[poll] anyone else needs fast random element access off a dictionary?
David Eppstein
eppstein at ics.uci.edu
Wed Feb 12 10:08:32 EST 2003
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/
More information about the Python-list
mailing list