flatten() time trial mystery. (or, 101 ways to flatten a nested list using generators)

[Francis Avila]

A few days ago (see the 'itertools.flatten()?' thread from October 28) I
became obsessed with refactoring a recursive generator that yielded the
leaves of nested iterables. When the dust settled, I had many flatten
functions at hand.

So I had to time them. Results below.

History of the functions (from flattrial.py):

# There are three basic features:
# 1. Can specify a function that determines iterability.
# 2. Can specify class-iterability.
# 3. Can modify sequence before iterating.

##Function: Features Supported : Author
##
##flatten_fa: 1 : Francis Avila
##flatten_po: 1,2,3 : Peter Otten
##flatten_po2: None : Alex Martelli channeling Peter Otten
##flatten_am: None : Alex Martelli
##flatten_dict: 2 : Peter Otten
##flatten_fastcond: 1,2 : Francis Avila
##flatten_itercond: 1,2,3 : Francis Avila
##flatten_dictcond: 1,2,3 : Francis Avila
##flatten_dictdef: 1,2,3 : Francis Avila
##flatten_trydictdef: 1,2,3 : Francis Avila
##flatten_fastdictdef: 1,2,3 : Francis Avila

Tree test flattens tree:
subtree = ['foo']*18 + [1,2,3]*6
tree = [ subtree*10, [ subtree * 8 ] ]

Node test flattens nodetree:
class Node(object):
def __init__(self, label=None, data=None, children=()):
self.children = children
self.label = label
self.data = data
def __iter__(self):
return iter(self.children)

leaves = [Node(chr(i+65),i) for i in range(10)]
branches = [Node(chr(i+65), i, leaves) for i in range(10,30)]
nodetree = [Node(chr(i+65), i, branches) for i in range(30,50)]

Results (Python 2.2):

.....>python flattrial.py
C:\Docs>python flattrial.py
Tree Tests (100 reps):
02.113544 fa
03.129147 po
02.845054 po2
02.587387 am
00.643718 dict
00.648371 fastcond
00.724689 itercond
00.791277 dictcond
01.006224 dictdef
00.833452 trydictdef
00.776937 fastdictdef
Node Tests (10 reps):
02.877818 po
02.633231 itercond
00.878554 dictcond
01.040838 dictdef
00.897504 trydictdef
00.864411 fastdictdef

I'd post flattrial.py, but it's about 500 lines and I don't have any web
space to put it up. Besides, I'm not sure anyone is interested. :)

A mystery, though. I did not expect dictdef (my magnum opus) to be as slow
as it was, so I investigated. I went to the obvious first: using dict.get
is quite a bit slower than using try: x = dict[key]; except KeyError: x =
default. This is rather inexplicable....

It was still noticeably slower than dictcond. So, I made fastdict, which
emulated dictcond more closely by not allowing the default handler to modify
the sequence passed to it:

def defaulthandler(seq):
try:
it = iter(seq)
except TypeError:
return False, seq
else:
return True, it

def flatten_fastdictdef(iterable, get_iterbility=None):
#Note defaulthandler is no longer an argument.
if get_iterbility is None:
get_iterbility = {''.__class__:False, u''.__class__:False}

# In dictdef, the following try-except is:

# iterbility = get_iterbility.get(iterable.__class__, defaulthandler)

try:
iterbility = get_iterbility[iterable.__class__]
except KeyError:
#Following added to avoid a function call
#Was:

# iterbility = defaulthandler
#
# if iterbility is defaulthandler:
# iterbility, iterable = defaulthandler(iterable)
# get_iterbility[iterable.__class__] = iterbility

#Now:
t = iterable.__class__
try:
iterable = iter(iterable)
except TypeError:
iterbility = get_iterbility[t] = False
else:
iterbility = get_iterbility[t] = True

if callable(iterbility):
iterbility, iterable = iterbility(iterable)

if not iterbility:
yield iterable
else:
for elem in iterable:
for subelem in flatten_fastdictdef(elem, get_iterbility):
yield subelem
This gave the results you see above: even faster than dictcond. The thing
is, I don't have any idea why. The function call overhead doesn't seem to
be enough to explain the difference between the try version of dictdef and
fastdictdef. Nor the name rebinding (which is very fast). Anyone have any
ideas?

Second, is the speed gain of fastdictdef over trydictdef worth the loss of
specifying a defaulthandler that can dictate what goes into the cache
dictionary and modify sequences? (I know, "it depends", but in the general
case, is that a feature anyone would ever *need*? I can't see how.)

--
Francis Avila