Home Original page

deque vs list: performance notes

Christian Tismer tismer at tismer.com
Sat Jun 3 09:37:07 EDT 2000 
Russell Turpin wrote:
...
> I wish the default implementation for lists were deques, so
> that I didn't have to worry about which end of a list I add
> to or remove from.

Fine, but for that you would throw the O(1) behavior of
lists away?

> Arithmetically-and-all-for-doing-it-from-both-ends'ly yrs,
> Russell

Please note that there is an alternative to using doubly linked
lists which takes much less memory and gives you fast modification
of both ends:

Take a simple list, together with a start and an end index.
Give this list an interface that re-implements the list behavior
with this slightly rearranged management.
Your list now becomes like a cyclic structure with a moving
gap in between.
Ok, there are some copy operations when the list has to grow,
but with a liberal allocation strategy this should be no
big problem.

Such an extension could be implemented on top of existing
lists quite easily. You'd have random access, and cheap
modification of both ends. Well, an insert into the middle
is still expensive.

but-one-can't-have-all-at-once-ly y'rs - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     where do you want to jump today?   http://www.stackless.com
More information about the Python-list mailing list