On Fri, Jun 17, 2011 at 8:45 AM, Franck Ditter <fra...@ditter.org> wrote: > Hi, I'm just wondering about the complexity of some Python operations > to mimic Lisp car and cdr in Python... > > def length(L) : > if not L : return 0 > return 1 + length(L[1:]) > > Should I think of the slice L[1:] as (cdr L) ? I mean, is the slice > a copy of a segment of L, or do I actually get a pointer to something > inside L ?
The slice is a copy of a segment of L. > Is the above function length O(n) or probably O(n^2) ? O(n^2). If you want to implement Lisp-style list processing in Python, Python lists are not the most efficient data type to do it with. I would suggest using 2-element tuples to represent cons cells and building up from there. Also note that Python does not do tail recursion optimization, so recursion in general is inefficient and prone to stack overflow if the data structure is large enough. > Where are such implementation things (well) said ? http://docs.python.org/tutorial/introduction.html#lists -- http://mail.python.org/mailman/listinfo/python-list
