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

[Dan Schmidt]

(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.

Right.

Dan

-- 
http://www.dfan.org