Question about scientific calculations in Python

[Andrew Dalke]

[Bengt Richter (maybe)]
[Nope (that was me)]
> 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)

[Here's Bengt Richter's response (at least, it wasn't mine)]
> whoa! can that be true?

[timbot (perhaps)]
> No, theoretical worst case is O(n**2).  (1 + 2 + 3 + ... + n == ?)

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

Oops!  I didn't notice the n**n -- I either read it as n*n or n**2,
so didn't catch the error in my proofing.


[timbot (again)]
> but over-allocation is always proportional to list size now.

[Me (who might be Andrew)]
> 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.

[PSU member #2 again ... if there was a PSU, which there isn't.  (Who is #1?
    You are #6 :)]
> 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.

I was thinking of standard more like mxStack or kjbuckets.  Something
which wasn't a standard part of the distribution but was the standard
answer to questions about data structures.

                    Andrew (who might still be Andrew)
                    dalke at dalkescientific.com