Timing Difference: insert vs. append & reverse

Bryan Olson bryanjugglercryptographer at yahoo.com
Wed Aug 4 23:05:17 CEST 2004

Duncan Booth wrote:
> Bryan Olson:
[Duncan Booth had written:]
> >> If you expected insert to be faster, perhaps you thought that Python
> >> used a linked-list implementation. It doesn't do this, because in
> >> practice (for most applications) a [array] based implementation gives
> >> better performance. 
> > 
> > True, but an array implementation can easily support amortized 
> > constant-time insert/delete at *either* end (without breaking 
> > constant-time indexing).  The same trick of keeping extra space 
> > at the tail end can work at the head; it requires keeping one 
> > additional offset to show where the occupied cells start.
> If the OP had said he expected insert and append to be the same speed I 
> might buy that but [...]

Hmmm ... let me clarify what I'm selling:  We can make lists 
perform efficiently as double-ended queues without breaking 
anything or perceptibly hurting anyone's efficiency.  Until this 
thread, I hadn't realized that Python's lists are much slower 
than Perl's in important cases:


Would this be a PEP-size change, or just a small fix?


More information about the Python-list mailing list