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

[Tim Peters]

[Courageous]
> ...
> I have this implementation at http://www.sourceforge/projects/pythonic.

Better make that

    http://www.sf.net/projects/pythonic

("sf" works the same as "sourceforge", but leaving off the ".net" makes the
link dead)

> In cvs, checkout adt. You want the "dlist" (double ended list) type.
> It's a vector which uses prealloc at the head AND the tail.  This
> implements much of the basic python list's capability, albeit it's
> never been intended as a patch replacement for listobject.c.

And fun, wasn't it?  Extending Python in C is a hoot!  I can tell you
enjoyed yourself <wink>.

To answer a question in the code, memcpy() and memmove() are both std C
functions, and you definitely want memmove() whenever the source and
destination slices overlap; memcpy() explicitly refuses to define what
happens then, to make life easier for optimized implementations using
buffering tricks to speed the copy; memmove() guarantees to do the right
thing.

Here's a dirty trick:  things like reverse() (which you did implement) and
sort() (which you didn't) can't change the size or address of the data
vector.  So you don't have to implement those yourself:  instead you can
create a temporary list object, set its ob_item pointer to *your* data
pointer, fill in its ob_size field with your size, and call the
corresponding Python list operation (PyList_Reverse(), PyList_Sort(), etc).
When those return, your "items" pointer will point to the dlist guts
appropriately shuffled.  Then set the list object's ob_item member to NULL
and decref the list object (setting ob_item to NELL prevents list dealloc
from crawling over the ob_item vector and decref'ing *its* contents too).

That's cheating, of course, but this has been stable for years, and you
already have access to the list object's defn. by virtue of #include'ing
Python.h (note that you didn't have to #include listobject.h too -- Python.h
already does that).  Of course if that breaks some day, tough luck -- but it
probably won't, and the sort code in particular is a major undertaking to
reproduce.

> mylist = []1000
>
> This would be a cool construct.

Yuck.

perhaps-for-sufficiently-uncool-values-of-cool-ly y'rs  - tim