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

[James T. Dennis]

holger krekel <pyth at devel.trillke.net> 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

 I'm humbled that you might think that (output from) my brain is 
 worth sharing.

 On the one hand the function should be easy to add (in C)
 IFF there's a pointer to the far end of the list.  On the other
 hand it's hard to imagine an elegant syntax for expressing it
 (the example doesn't qualify) and it's hard to believe that this 
 feature would be used often enought to matter.

 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.

 Even if the memory was so tight that the GC was forced to run
 every hundred or so items (assuming they're being pop(0)'d from
 one list into another on a memory constrained system) we've 
 still reduced the work load from O(n**2) (performing n pop(0)s
 n times) by two orders of magnitude O(n/100).  That's because 
 the GC gets to wait for a 100 pops (or so) move each item over
 100 (or so) places in one O(n) pass and let the app get back to
 work.

 In other words, it should be unecessary to add syntax and methods
 when it's probably possible to tweak the implementation.  Then the 
 question becomes:

 Is the tweak worth it?

 (I don't know since I haven't even glanced at the Python sources).