On Sat, 8 Feb 2014 05:00:24 +1100
Chris Angelico
On Sat, Feb 8, 2014 at 1:59 AM, Antoine Pitrou
wrote: 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.
Indeed, since deque exists, it is the reasonable answer. This whole discussion happens in a hypothetical setting where deque wouldn't exist and there would be an opportunity to make list a one-size-fits-all sequence type. (note that my personal opinion is that built-in Python data types should be sufficiently powerful to cater for most use cases, rather than build a whole array of specialized collection types as in Java or C++) Regards Antoine.