Timing Difference: insert vs. append & reverse
Bryan Olson
bryanjugglercryptographer at yahoo.com
Wed Aug 4 17:05:17 EDT 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:
http://perlmonks.thepen.com/17890.html
Would this be a PEP-size change, or just a small fix?
--
--Bryan
More information about the Python-list
mailing list