Question about scientific calculations in Python

[Andrew Dalke]

Bengt Richter:
>On Tue, 12 Mar 2002 22:15:43 -0700, "Andrew Dalke"
<dalke at dalkescientific.com> wrote:
>[... good optimization advice, nicely elaborating the idea of precomputing
...]
>>If your lists are really long (O(100,000) or more?) then you might find
>>that the append starts taking too long -- append is asymptotically O(n**n)
>whoa! can that be true? I hope not. It is very cheap to tie a singly linked
>list into a circle and point to the last node when pointing to the list as
a whole.

Yes, it's true.  This comes up on the list about once every six
months or so.  As I recall, Python's standard lists grow by 10 elements
at a time for small lists (less than 500 in length), then 100 at a time
for larger lists.  So if you have 5000 or fewer elements then the growth
is linear enough.  To date, few have reported this as a problem.

Insertions and deletions are also linear in the length of the list.

Yes, we all know there are better ways to deal with this, for different
people's definition of the meaning "better."  It isn't going to change
in Python.  Best I think would be a standard module of data structures
(priority queue, doubly-linked lists, stack, etc.)  But it hasn't bothered
me enough to go ahead and do it.

                    Andrew
                    dalke at dalkescientific.com