Flatten..with less recursion

[Mike C. Fletcher]

Oh, let's pull out this hoary old nugget anyway...

def collapse(inlist, type=type, ltype=types.ListType, maxint= sys.maxint):
	'''
	Destructively flatten a list hierarchy to a single level. 
	Non-recursive, and (as far as I can see, doesn't have any
	glaring loopholes).
	Further speedups and obfuscations by Tim Peters :)
	'''
	try:
		# for every possible index
		for ind in xrange( maxint):
			# while that index currently holds a list
			while type(inlist[ind]) is ltype:
				# expand that list into the index (and subsequent indicies)
				inlist[ind:ind+1] = inlist[ind]
			#ind = ind+1
	except IndexError:
		pass
	return inlist

Who knows, maybe there's even ways to make it faster these days.  Enjoy,
Mike

-----Original Message-----
From: python-list-admin at python.org
[mailto:python-list-admin at python.org]On Behalf Of Nick Perkins
Sent: May 25, 2001 14:14
To: python-list at python.org
Subject: Re: Flatten..with less recursion


>
> def flatten(L):
>     if type(L) != type([]): return [L]
>     if L == []: return L
>     return flatten(L[0]) + flatten(L[1:])


...hmm
this might make a good Scheme program,
but I would consider this excessive and
unnecessary recursion in any language that
does not do proper tail recursion.
Python performance on any long list would
probably be very bad.
(hmm...Stackless?...i wonder...)

..what about:

def flatten(L):
    if type(L) != type([]): return [L]
    if L == []: return L
    return reduce(lambda L1,L2:L1+L2,map(flatten,L))



...maybe someone knows how to avoid the lambda,
but I think this should be much faster.








-- 
http://mail.python.org/mailman/listinfo/python-list