List Flatten

[Peter Otten]

Raymond Hettinger wrote:

> 
> "bearophile" <bearophileHUGS at lycos.com> wrote in message
> news:5c882bb5.0410180743.62059c68 at posting.google.com...
>> Comparing versions for speed, Raymond Hettinger's version is quite
>> slow (even 10 or more times slower than mine for certain kinds of
>> lists).
>>
>> Into the most nparameterizesof Alex Martelli's version there is a
>> function call to isatomic (and the try-except) that slow down the
>> program a lot. Removing them (we expand lists only) we obtan the short
>> Peter Otten's version, that is a bit better thanChineseor very nested
>> lists and a bit worse for quite flat lists (that are the most common,
>> I think).
> 
> That is an apples-to-oranges comparision.  The loss of speed is due to the
> additional features of not expanding strings and not expanding iterables
> into
> memory all at one.  Previous discussions about flatten() in this newsgroup
> or
> the tutor list have indicated that is what is usually wanted.  Take out
> the test
> for the atomicity of strings and the speed is much improved.  Also, from
> original posting, it seemed that memory friendliness was a key measure for
> merit given the huge data sizes and nesting depths.
> 
> This discussion may have over-abstracted the problem so that your
> apples-to-oranges timings are irrelevant.  Do you have real world use
> cases for wanting to flatten nested containers of non-homogenous object
> types (a mix of
> numbers, strings, dictionaries, etc)?  Do you really want to split your
> strings
> into streams of characters and then throw numbers in the mix.  I think
> not.

In may book all three versions (Alex Martelli's yours and mine) use the
_same_ flattening algorithm with _different_ methods to test for atomicity.
While I take the lightweight (and fast) approach of inlining
isinstance(item, list) - only item.__class__ is list could be faster - as
specified in the original post, you provide a function that tries to cover
most common cases and Alex parameterizes his variant making it a candidate
for inclusion in a library. I think you often have to decide between these
three approaches and would not call it an apples-to-oranges comparison
(btw, oranges are also called "Chinese apples" in German and Dutch, so
somebody thought that comparing them was a good idea :-), but again, it
should be made clear to the OP that he is _not_ comparing flattening
algorithms.

Another lesson - that exceptions can slow down a program if they are raised
in the common case - is also worth noting. 
Various tests for atomicity have been discussed and benchmarked in 

http://groups.google.com/groups?threadm=vq0ul33348oi42%40corp.supernews.com

which I didn't mention before because the OP explicitly ruled out a
recursive solution.

Peter