Complexity of splits

[Duncan Booth]

Jean-Guillaume Pyraksos <jeapy at free.fr> wrote in news:jeapy-
98A462.15570212052003 at malibu.unice.fr:

> As I am digging into my Python studies, I started translating some 
> elementary Lisp recursive algorithms...
> 
> def length(L):
>    if not(L): 
>       return 0
>    return 1 + length(L[1:len(L)])
> 
> is (?) the Pythonization of the Lisp function:
> 
> (defun length (L)
>   (if (not L)
>       0
>       (+ 1 (length (cdr L)))))
> 
> If n is the length of L, then the Lisp algorithm is O(n) but the Python 
> algorithm is O(n^2) as L([1:len(L)]) builds a n-1 elements list. Am i 
> wrong ? I chose a split as it seems that taking the cdr of a list is not 
> a primitive operation in Python, did I miss it ? Probably. What's the 
> name of that operation  so that the recursive algorithm stays O(n) ? I 
> don't want (for now) to translate it into a loop.
> Thanks,
> 
Python lists are stored like arrays in other languages, not as linked 
lists, so no, you didn't miss anything, cdr of a Python list requires 
making a copy of all but one element. On the other hand, getting the length 
of a Python list or accessing an arbitrary element are both O(1) 
operations.

If you are trying to mimic Lisp algorithms to understand the data 
structures, then you could implement a Python list as a list of tuples.

e.g.
L = (1, (2, (3, (4, None))))

Then car becomes L[0] and cdr becomes L[1] and both are O(1) operations. 
However you will almost certainly find that any practical list operations 
are much slower using this form of list than the equivalent would be using 
builtin lists.

However, if you are interested in mimicking Lisp simply to be able to use 
similar operations, stick with Python lists, accept that cdr is slower, and 
define length like this:

>>> length = len
>>> print length([1, 2, 3, 4])
4

-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?