flatten(), [was Re: map/filter/reduce/lambda opinions and background unscientific mini-survey]

[Ron Adam]

Tom Anderson wrote:

> The trouble with these is that they make a lot of temporary lists - 
> George's version does it with the recursive calls to flatten, and Ron's 
> with the slicing and concatenating. How about a version which never 
> makes new lists, only appends the base list? We can use recursion to 
> root through the lists ...

Ok...  How about a non-recursive flatten in place? ;-)

def flatten(seq):
     i = 0
     while i!=len(seq):
         while isinstance(seq[i],list):
             seq.__setslice__(i,i+1,seq[i])
         i+=1
     return seq

seq = [[1,2],[3],[],[4,[5,6]]]
print flatten(seq)

I think I'll be using the __setslice__ method more often.



And the test:
#--------------------------------

# Georges recursive flatten
init_a = """
def flatten(seq):
     return reduce(_accum, seq, [])

def _accum(seq, x):
     if isinstance(x,list):
         seq.extend(flatten(x))
     else:
         seq.append(x)
     return seq

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Ron's non-recursive
init_b = """
def flatten(seq):
     s = []
     while seq:
         while isinstance(seq[0],list):
             seq = seq[0]+seq[1:]
         s.append(seq.pop(0))
     return s

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Tom's recursive, no list copies made
init_c = """
def isiterable(x):
     return hasattr(x, "__iter__") # close enough for government work

def visit(fn, x): # perhaps better called applytoall
     if (isiterable(x)):
         for y in x: visit(fn, y)
     else:
         fn(x)

def flatten(seq):
     a = []
     def appendtoa(x):
         a.append(x)
     visit(appendtoa, seq)
     return a

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Devan' smallest recursive
init_d = """
def flatten(iterable):
     if not hasattr(iterable, '__iter__'):
         return [iterable]
     return sum([flatten(element) for element in iterable],[])

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Ron's non-recursive flatten in place!  Much faster too!
init_e = """
def flatten(seq):
     i = 0
     while i!=len(seq):
         while isinstance(seq[i],list):
             seq.__setslice__(i,i+1,seq[i])
         i+=1
     return seq

seq = [[1,2],[3],[],[4,[5,6]]]
"""

import timeit
t = timeit.Timer("flatten(seq)",init_a)
print 'recursive flatten:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_b)
print 'flatten in place-non recursive:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_c)
print 'recursive-no copies:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_d)
print 'smallest recursive:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_e)
print 'non-recursive flatten in place without copies:',t.timeit()

#--------------------------------------------


The results on Python 2.3.5: (maybe someone can try it on 2.4)

recursive flatten: 23.6332723852
flatten in place-non recursive: 22.1817641628
recursive-no copies: 30.909762833
smallest recursive: 35.2678756658
non-recursive flatten in place without copies: 7.8551944451


A 300% improvement!!!

This shows the value of avoiding copies, recursion, and extra function 
calls.

Cheers,
Ron Adam