python list handling and Lisp list handling
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)
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-list