Complexity of splits

[Alex Martelli]

<posted & mailed>

Jean-Guillaume Pyraksos wrote:

> 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)))))

Well, sort of -- there's some redundancy and a strange choice in having
to use the built-in len to compute its equivalent, so I think a closer
version might be instead:

def length(L):
    if not L:
        return 0
    return 1 + length(L[1:])


> 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

Right.  Python's so-called 'list' is actually what just about every
other language calls a vector or array -- a contiguous area of memory,
NOT a linked structure -- so the O() behavior of various operations is
drastically different from what you might expect from a linked-list --
len(L) is O(1), so is L[x], but L[1:] is O(N), and so forth.

> 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.

There is no 'cdr of a list' in Python (since the 'list' is actually a
vector) nor any way to take such a cdr without modifying the original
list except by making a copy, so O(N) is unavoidable.  If you CAN
modify the original list, then L.pop() does modify it (by removing
the LAST item rather than the FIRST one) in time O(1).  So, if you
were intensely keen on coding a slow recursive O(N) replacement for
the fast built-in O(1) len function, one possibility might be to make
the copy JUST ONCE, as follows:

def length(L):
    def aux_length(L1):
        if not L1: return 0
        L1.pop()
        return 1 + aux_length(L1)
    return aux_length(list(L))

using list(L) to get a separate (shallow) copy of L, which is also
an O(N) operation.  Such decomposition of a recursive function into
a nonrecursive outer function which calls a recursive inner one is
of course quite a familiar technique in Lisp too, although in that
case one might typically use it for other purposes, such as ensuring
tail recursion (Python's implementations don't currently optimize
tail recursion -- and are unlikely to do so in the foreseeable future,
since recursion is most definitely NOT Python's main focus -- so such
an effort would be futile for Python anyway).

Of course, this function will probably hit Python's recursion limit
as soon as you try to use it on any _substantial_ list -- see
function setrecursionlimit in module sys.  One more hint that, when
programming in Python, you're FAR better off using it in the ways
it was intended to be used rather than in widely different ways, of
course.  But, if you insist, you CAN surely [ab]use it like this;-).


Alex