Question about scientific calculations in Python

[Tim Peters]

[Bengt Richter (maybe)]
> 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?

No, theoretical worst case is O(n**2).  (1 + 2 + 3 + ... + n == ?)

[Andrew Dalke]
> Yes, it's true.

Only when the sky is falling too <wink>.

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

That used to be true, but over-allocation is always proportional to list
size now.  This had most benefit on assorted Windows flavors (which don't
act alike in this respect).  It made no difference at all on some assorted
Unixish systems (append often enough and it may get reassigned to its own
mmap'ed region; or it may get moved to the sbrk limit so that further
appends "just" bump the high-water VM mark without physical movement).

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

They're linear in the length of the list following the insert/delete
position.

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

Fast constant-time (modulo cache effects) random access is Python's chief
goal for Python lists.

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

Guido doesn't go for this kind of thing:  the more "advanced" the data
structure, the more specialized variants it sprouts, and there aren't enough
volunteers to maintain the ever-bulging code across all the platforms Python
runs on.