Question about scientific calculations in Python

[Jason Orendorff]

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...

  http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/py
    thon/dist/src/Objects/listobject.c?rev=2.103&
    content-type=text/vnd.viewcvs-markup

and check out the source for yourself.

## Jason Orendorff    http://www.jorendorff.com/