[Python-3000] Two proposals for a new list-like type: one modest, one radical (original) (raw)
Daniel Stutzbach daniel at stutzbachenterprises.com
Tue May 1 02:21:49 CEST 2007
- Previous message: [Python-3000] Breakthrough in thinking about ABCs (PEPs 3119 and 3141)
- Next message: [Python-3000] Addition to PEP 3101
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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
- Previous message: [Python-3000] Breakthrough in thinking about ABCs (PEPs 3119 and 3141)
- Next message: [Python-3000] Addition to PEP 3101
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]