Pop a list from beginning ? and memory saving...
mcherm at destiny.com
Wed Jun 19 20:23:02 CEST 2002
Holger Krekel wrote:
>> [Tim Peters]
>>> [James T. Dennis]
>>>> So, the critical question is:
>>>> Is the list's reverse() method done in place
>>>> and does it run in linear time
>>>> (or better?
>>> No. It does len(list)/2 swaps.
> O(n/2) is linear, but still slightly better than
>> in another thread we had some discussion about a
>> reverse-iterator. You could write
>> for item in iters.reverse(list):
>> # item iterates over list's items backwards
>> # but the list itself stays unmodified.
>> Do you agree that this would be a good idea?
>> please-share-your-brain-ly y'rs, holger
James T Dennis wrote:
> It might be better to have a hack to the implementation of the
> list primitives --- so they defer the shift of remaining elements
> until GC. The head of the list could point at the first none
> deleted item. Then pop(0) could be implemented in O(1) time and
> the garbage collector would eventually come along to do it's
I'm not sure that makes sense in Python. Most garbage is NOT collected
by a separate GC thread (as in Jython and Java) or in bursts of GC
activity. In cPython, nearly everything is garbage collected via
reference counting... the object is GC'ed when the last reference to it
As for the original question (is it a good idea), I'd say YES, but with
one caveat. I think that it is important that the "iterable" utilities
operate on ANY iterator ... and that isn't possible with the intelligent
implementation of reverse. So I think that if iterable.reverse() were to
check the type of it's argument and use the clever approach (counting
backwards) for types list and tuple, but fall back on creating a temp
list and reversing it for other types, then that'd be quite useful.
Optimize the common case, but don't lose the universality.
-- Michael Chermside
More information about the Python-list