Pop a list from beginning ? and memory saving...

[Michael Chermside]

Holger Krekel wrote:
>> [Tim Peters]
>>> [James T. Dennis]
>>>> ...
>>>>  So, the critical question is:
>>>> 	Is the list's reverse() method done in place
>>> Yes.
>>>> and does it run in linear time
>>> Yes.
>>>> (or better?
>>> No.  It does len(list)/2 swaps.
> 	O(n/2) is linear, but still slightly better than 
> 	O(n)
> 
>> 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 
>  job.


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 
is released.

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