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

[Chris Angelico]

On Sat, Feb 8, 2014 at 5:13 AM, Antoine Pitrou <solipsis at pitrou.net> wrote:
>> 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.

Well, yes. In the absence of deque, this would be a more plausible
optimization; if nothing else, it would make destructive iteration far
more efficient, even without the insert() optimization. It'd still
require some deep analysis to figure out just how often the
optimization would help, vs how often the complexity would add
unnecessary cost, but I can imagine a way of doing it that wouldn't
cost too much. (Just advance the base pointer and increment a
"pre-list spare space" value. Then regular operations can ignore the
spare space; only deallocation/resize need to worry about it (to get
the real pointer for free()), and insert() can try to take advantage.
It could even guess that it might be worth adding some wasted space,
to cope with multiple insert()s.) And if someone proposed that,
someone else would then say "It'd be so much more efficient if we
explicitly tell the list constructor that it should do this, rather
than have it do it all the time", and there you are, right back at
deque. :)

This, btw, is why I like Python's data type model ("have lots of 'em")
rather than PHP's ("the Array will do everything, so use it"). If my
code is slow because I used OrderedDict instead of list, I can fix my
code. If my code is slow because I used Array instead of Array.....
s'not a lot I can do about that.

ChrisA