O(n^2) is bad - can it be fixed?

[Tim Peters]

[Isaac To Kar Keung]
> ...
> Yes, it rarely happens.  But is the solution really so difficult
> that we have any excuse not doing it right?

You need to define "the problem" first.  I'm really not clear on what it is
you think needs to be solved!  If you define it carefully, then I wager
you'll discover, e.g., that Bruce Dawson's complaint cannot be solved on
Win9x even if you use an explicit capacity field and do growth by doubling
(he doesn't realize that yet either).  It can be *delayed*, but Win9x VM
management is such that address space will still get fragmented beyond hope
unless Python also takes over allocating heaps.  This gets absurd.

> ...
> I see this as a fundamental design problem: it ties the conceptual list
> to physical memory allocation.

It's a design question, and Guido picked a particular answer 10 years ago;
in practice it works fine.  There would be much more sympathy for a list
implementation that was friendlier to insert and remove at both ends,
because people actually bump into that now (it's rare, but still much more
frequent than gripes about append behavior).

> The user should have their own right to say that the list is to
> step between 397 and 398 elements (or whatever number they are in mind),

Says who?  I feel no need for this.  If you think it's a need, write an
extension module implementing it and then sell that on real-life merit.  If
people find it gives them a real advantage, they'll agitate to move it into
the core.

> and the performance of the library shouldn't be in completely different
> orders (e.g., from constant time, linear space to linear time,
> quadratic space) in such cases.  This would make Python completely
> useless.

"If we don't do X, Python would be completely useless."  Python doesn't do
X.  Yet neither is it completely useless (according to me).  I don't know,
but suspect there may be a lapse in this argument <wink>.

> ...
> The answer is far from the difficulty you've implied.

That's because you haven't faced what it takes to worm around all provokable
problems on Windows.  Don't argue about it:  write some code and *try* it,
then come back when "it's solved".

I'm not arguing about the extra space again, because it's pure waste on
Linux, doesn't actually solve the problem on Win9x, and Guido rejected the
idea last time this went around anyway.

it's-not-like-there-aren't-useful-things-that-need-doing-too-ly y'rs  - tim