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

Helen Dawson helend at accessone.com
Thu May 31 02:30:58 EDT 2001


Tim Peters wrote:

> [Bruce Dawson]
> > ...
> > Now obviously I can fix this problem - switch from list to array,
>
> No, array doesn't even do as much as lists used to do to avoid quadratic
> behavior.  Your test case simply didn't try arrays big enough for this to

Darn.

> Maybe.  As I mentioned in another msg, when I did a straight C realloc
> double-the-size test (no Python) and put it in a loop, the end result was
> that Win98SE froze on about the 6th iteration.  If you haven't noticed yet
> in other contexts, take the hint <wink>:  Win9x is not a robust platform.

Oooohhhh yeah. I've managed to avoid doing any significant development
on Win9x - I've run NT variants for seven years - but my code still needs
to run on Win9x. Such a pity.

As further proof of how bizarre the Win9x behavior is, I hypothesized that
if I went:

range(4000000)

in the PythonWin interactive window before running my script that I might
get better performance. Indeed I do. Win9x will then run my script to
completion, and *much* faster also.

The range(4000000) statement creates a list with four million elements
(obviously) which forces a large heap to be created. Since the list is
immediately destroyed, the heap is empty and available. Then, all
subsequent growing of my other lists run quite nicely because the
allocations all fit in the large heap, so realloc() works without any
copying.

A truly gross hack, mentioned purely for amusement purposes.





More information about the Python-list mailing list