[Python-Dev] deque alternative

[Christian Tismer]

Martin Blais wrote:
> On 12/25/05, Christian Tismer <tismer at stackless.com> wrote:

[is auto-dequeue too much magic?]

> IMO it's a little bit too much magic.  Plus, if you pass these
> instances around e.g. between libraries, how could you determine with
> certainty the usage patterns without analysing the entire codebase?  I
> think the user has to be involved.

Well, I would treat a list as a special case of dequeue.
Dequeues are made of a chain of list pieces. ATM they are
all equally sized. But turning a list into a dequeue like
structure at some point in the future can be done in many
ways. One way would be to embrace the list into the dequeue
structure without any copying involved, if a smooth transition
is crucial.
Passing the object between libraries gives me no problem.
We just track usage a little and even convert back to a list
if it seems appropriate. I think this can be cheap and elegant.
The question is less about implementation, but if we want this
to be explicitly more versatile, documenting it like
"""lists can be efficiently extended at both ends. Dependent on
the usage pattern, the implementation is free to choose a more
compact representation""".

> A problem I see now is that there is no way for me to
> indicate--whether there currently exists or not an appropriate data
> type with the desired characteristic-- whether I want an array (Python
> list) or a real list, both of which are really, really basic
> fundamental kinds of data structures with very different complexity
> characteristics.  The source code I write does not carry this
> information and therefore if in the future it would become available
> there won't be an easy way to convert code to take advantage of this. 
> This choice, is being made in the programmer's head, but the
> distinction blurred in the source code because lists are just not
> there.

I don't think your code has to decide about this. The power lies
in the fact that you don't specify that, but just use the list
in a different way. We do this in the PyPy implementation;
right now it is true that we have a static analysis, but a JIT
is to come, and I'm pretty sure it will try to use an array
until something gets used like a list.
No concrete layout available, yet.

...

> Also, there is something incredibly elegant and simple and compact
> about the cons cell, maybe all we need is a good simple cons cell type
> and a nice interface on it, so you get both single-linked lists and
> trees at the same time...

Tuples are fine for cons cells, and if your usage pattern
indicates that we can optimize, why should you use an extra
data type? You already said what you want, by the way you use
it. Extra-specification would be redundant, wouldn't it? :-)

ciao - chris
-- 
Christian Tismer             :^)   <mailto:tismer at stackless.com>
tismerysoft GmbH             :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9A     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 802 86 56  mobile +49 173 24 18 776  fax +49 30 80 90 57 05
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/