[Python-3000] Two proposals for a new list-like type: one modest, one radical
daniel at stutzbachenterprises.com
Tue May 1 02:21:49 CEST 2007
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
More information about the Python-3000