deque vs list: performance notes

[Christian Tismer]

Courageous wrote:
> 
> > I'm against a linked list deque implementation for Python.
> > But I'm plus 1 on doing it as an extension of lists.
> 
> For what it's worth, I'm implementing a dynarray which
> leaves buffer room on both the head and tail as we speak.

Whow :-))

> Note that this slows down random access ever-so-slightly,
> as you have to have a "virtual index" to account for the
> actual and current positions of the "beginning" of the list.

Sure. There is no free lunch at all.
For that reason, I also wouldn't propose to change
lists for this feature, but offer this as an addition.
If you want it, you get it, at a slight cost for every
operation of course.
How about deque(list) as initializer?

> However, the cost is very small: an extra add on every
> access.

I think it is a bit more; well it depends on the
implementation. I thought of a list, with a size
controlled by the deque, padded with Py_None.

> My current algorithm is as follows:
> 
> 1. Store a "virtual index" into the list, allowing buffer
>    room at the head.

Yup.

> 2. On an insert at the head, simply decrement the virtual
>    index and insert.

Yup.

> 3. On an insert operation at the head, if the virtual index
>    would go negative on the insert, double the allocation
>    space of the array and place the actual used space of
>    the array 1/3 of the way into the array.

Great. I'd also love to get the 1/3 rule into standard lists.

> 4. On removal at the head, simply increment the virtual
>    index.

Yeah.

> 5. If the virtual index becomes larger than 2/3 of the
>    allocated space, move the actual used space of the
>    array 1/3 of the way into the array (this last is to
>    avoid an array which would grow infinitely on append
>    to tail and removal from head).

We have something in common...

> 6. The growth rate of the array will always be 100%
>    increase (as compared to python's 50/500 heuristic,
>    IIRC).

Blah. No more comments, just do it. It is the right
track; I love it.

> 7. You'll be able to specify an initial size for the list.
> 
> This technique should have the same complexity as python
> lists with the additional benefit of O(1) removal/insert
> at the head without sacrificing O(1) random access. I'll
> do a complete performance test as before, of course.
> 
> As per usual, the source will be entered into the public
> domain.

As per unusual, I will incorporate this into Stackless
Python immediately if it is written as clear as you described
it.

still-waiting-for-your-job-offer-ly y'rs - chris :-)

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     where do you want to jump today?   http://www.stackless.com