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 -- http://mail.python.org/mailman/listinfo/python-list