Complexity of splits

[Erik Max Francis]

Jean-Guillaume Pyraksos wrote:

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

This line would probably make more sense as

	return 1 + length(L[1:])

It is a little peculiar using len (which computes the length of a
sequence) in conjunction with writing a recursive function which
computes the length of a list ... :-).  In Python you can leave one end
of the slice limits open and it means "from the beginning" (L[:x}) or
"to the end" (L[x:]).

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

You are correct.

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

You are correct again, although what you call a "split" is normally
referred to as a slice.  (Split is an unrelated operation you can
perform on strings.)

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

The fundamental issue here is that Python lists and Lisp lists are not
the same beasts, and you don't iterate over them in the same way.  Lisp
lists are really degenerate tree structures composed of cons cells, and
you can walk along the structure's cons cells and add them up, like this
algorithm does here.

Python's lists (and indeed tuples and strings as well) are computer
science vectors, like Lisp arrays.  (Python has no builtin "linked list"
data structure, though you can easily make your own with attribute
references.)  And since there's no way to talk about a chunk of a list
without making a new one, that means that the Python version of your
algorithm is going to be O(n^2).

The closest Python analog would be to actually build a linked list data
structure and then manipulate that, or instead of passing lists around,
pass indices into the list.  In that case, though, the slicing is still
going to make the algorithm O(n^2), unless you use the len builtin
(which you were actually using in your sample code anyway).

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ There is _never_ no hope left.  Remember.
\__/ Louis Wu
    Max Pandaemonium / http://www.maxpandaemonium.com/
 A sampling of Max Pandameonium's music.