[poll] anyone else needs fast random element access off a dictionary?
dfan at dfan.org
Wed Feb 12 15:57:58 CET 2003
(sorry for the one-line followup, I trimmed as much as I could)
Duncan Booth <duncan at NOSPAMrcp.co.uk> writes:
| Michal Vitecek <fuf at mageo.cz> wrote:
|| Dan Schmidt wrote:
||| 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.
|| 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.
More information about the Python-list