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