Mark Tarver wrote:
This page says that Python lists are often flexible arrays
http://www.brpreiss.com/books/opus7/html/page82.html
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
'A list is a sequence of elements, but it is not a single primitive
object; it is made of cons cells, one cell per element. Finding the
nth element requires looking through n cons cells, so elements farther
from the beginning of the list take longer to access. But it is
possible to add elements to the list, or remove elements.'
(from http://www.chemie.fu-berlin.de/chemnet/use/info/elisp/elisp_7.html)
But are Python lists also indistinguishable from conventional
Lisplists for list processing. For example, can I modify a Python
list non-destructively? Are they equivalent to Lisp lists. Can CAR
and CDR in Lisp be thought of as
def car (x):
return x[0]
def cdr (x):
return x[1:]
The idea of a list in which elements can be accessed in constant time
is novel to me.
They are usually implemented as resizable arrays. In CPython great care
has been taken to make appending average to constant time; however,
inserting requires the later elements to be shifted up.
In the way they are normally used they are fast.
There are also queues and deques for when you want efficient queue or
deque behaviour.
--
http://mail.python.org/mailman/listinfo/python-list
