Question about scientific calculations in Python
jason at jorendorff.com
Thu Mar 14 13:52:04 CET 2002
Bengt Richter wrote:
> Andrew Dalke wrote:
> > ...
> > Insertions and deletions are also linear in the length of the list.
> Tim Peters wrote:
> > They're linear in the length of the list following the insert/delete
> > position.
> Does that mean the whole tail is rebuilt? Is there any instrumentation
> left over that logs access patterns? I wonder what real life uses show.
It's not a linked list. It's more like a Java or Scheme "vector".
The "whole tail" is indeed "rebuilt" but that usually amounts to a
single memmove() call. It's crazy fast, but it's still O(N) on the
length of the tail.
Glue this URL together...
and check out the source for yourself.
## Jason Orendorff http://www.jorendorff.com/
More information about the Python-list