[Python-3000] Two proposals for a new list-like type: one modest, one radical

[Daniel Stutzbach]

On 4/25/07, Raymond Hettinger <python at rcn.com> wrote:
> > There are only a few use-cases (that I can think of) where Python's
> > list() regularly outperforms the BList.  These are:
> >
> > 1. A large LIFO stack, where there are many .append() and .pop(-1)
> > operations.  These are O(1) for a Python list, but O(log n) for the
> > BList().
>
> This is a somewhat important use-case (we devote two methods to it).

I've been thinking about this a bit more.  For the LIFO use case, I
can cache a pointer within the root node to the right-most leaf node,
which will make a sequence of n append and pop operations take O(n)
amortized time (same as a regular list).

The latest version, 0.9.4, on PyPi fixes most of the issues raised by others:

- C++ style comments have been converted to C comments.
- Variable declarations are now always at the beginning of a block.
- Use Py_ssize_t instead of int in all (I think) the appropriate places.
- Cleaned up the debugging code to rely on fewer macros
- Removed all (I think) gcc-isms

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC