On Sat, Feb 8, 2014 at 1:59 AM, Antoine Pitrou
On Fri, 7 Feb 2014 22:45:33 +1100 Chris Angelico
wrote: But apart from maybe reducing the memory copying (the same optimization could mean that repeated pop(0) calls would incur less copying, too), there's not a huge gain.
If you think switching from O(n**2) to O(n) isn't a huge gain, then indeed :-)
Sure, that would be a huge gain. But anyone who's repeatedly calling pop(0) followed by insert(0,x) should be using deque rather than list. It's like optimizing str + str, only less common. Yes, there's an algorithmic complexity improvement, to be sure; but there's an alternative that has all the same improvement already there. A scheme such as I described would have a constant-time penalty for *every list*, so the benefit to a small number of lists is that much less likely to actually improve overall performance. ChrisA