[Python-ideas] Question about `list.insert`

[Chris Angelico]

On Sat, Feb 8, 2014 at 1:59 AM, Antoine Pitrou <solipsis at pitrou.net> wrote:
> On Fri, 7 Feb 2014 22:45:33 +1100
> Chris Angelico <rosuav at gmail.com> 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