[poll] anyone else needs fast random element access off a dictionary?
peter at engcorp.com
Wed Feb 12 14:52:51 CET 2003
Duncan Booth wrote:
> 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:
> > 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.
Need a small correction to the above to avoid confusion: change first
line to read "He was sugggesting that instead of deleting an item from
the *middle* of the list ...."
More information about the Python-list