python list handling and Lisp list handling

Daniel Stutzbach daniel at stutzbachenterprises.com
Mon Apr 27 21:18:58 CEST 2009


On Fri, Apr 24, 2009 at 10:19 AM, Mark Tarver <dr.mtarver at ukonline.co.uk>wrote:

> but also says that their representation is implementation dependent.
> As far as I see this should mean that element access in Python should
> run in constant time.  Now if so this is a boon, because generally
>

When I first learned Python, I too was confused by the fact that Python
lists are actually arrays (or vectors) under-the-hood, and it was some time
before I learned that element access is fast (O(1)) but inserts, deletes,
and taking a sublist are slow (O(n)).

Much later, I went on to write a drop-in replacement type called the "blist"
that has the same methods as a Python list, but has better asymptotic
performance for many operations.  That way I can write use the list in the
most natural way without having to worry about accidentally hitting a O(n)
method.

http://pypi.python.org/pypi/blist/

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090427/38252e0f/attachment.html>


More information about the Python-list mailing list