PERFORMANCE: list versus a "dlist"

[Courageous]

> so how about also doing some random tests (or assuming I'm perverse) the
> worst case for your dlist ie insert and remove in the middle.

I didn't do this, because the cost will be identical to the
python list implementation, with the exception of a little
bit of extra constant time which won't be measurable. The
only anticipated data points of interest were at the head,
hence I confined my measurements to that.

If you want insert/remove in the middle, you should use my
deque implementation, which supports safe (I think) write-
on-iterate. In order to acquire safety with write-on-iterate,
I only allow one outstanding iterator at a time and lock
the deque as long as an iterator is outstanding. This
prevents (I think, heh, heh) a few situations which could
cause python to crash if mutiple threads were accessing
the deque.

In any case, assuming any normal iteration over the deque,
at any location I, insertion at I offers a complexity guarantee
of constant time. Iterators support arbitrary forward or
backward iteration, and don't have any trouble with this
because of the dual-sentinel approach ala Sedgewick's
algorithm.

The deque also implements merge in constant time, with the
caveat that it breaks a sort of implicit covenant of python
and is destructive to the argument deque (it doesn't destroy
the deque per se, but rather removes all of its elements
wholesale).

I'll probably be putting a website up for all these sources
sometime soon, but in the meantime mail me and I can send
you the whole VC98 project zipped up if interested.

I'm implementing all of the sequence and invariant sequence
methods on the dlist object at the moment, and will probably
get back to completing the deque as soon as this is done.

Do keep in mind that my deque implements random access as
O(n), which is a major drawback if you have any desire to
access your data structure that way. I hesitate to even
implement the d[i] sequence operator for this reason; it's
almost better to have an error pop up than to allow a naive
program to index the array like that.


C/