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

[Terry Reedy]

"Tom Anderson" <twic at urchin.earth.li> wrote in message 
news:Pine.LNX.4.62.0507052310110.13421 at urchin.earth.li...
> I guess setslice is a lot faster than i thought.

Nope, the example is too short to be meaningful.

> How are python lists
> implemented? Presumably not as straightforward arrays, where inserting a
> bunch of items at the head would mean moving everything else in the list
> along?

They *are* extensible arrays, and insertion *does* mean exactly that --  
moving everything else along -- although CPython probably does it with C 
memcopy().  So the littly puny 'test' example with about 20 total elements 
is testing overhead, not large-list behavior.  So you are right, *much* 
longer lists are needed.  You could start, for example, with a list of 1000 
lists of 1000 elements (all 0 would be fine).  Or maybe 100 of 100 of 100. 
For that, I would start with something that appended and extended the 
result list.  Or try writing a generator iflatten that yielded elements in 
order:
   def flatten(iterable): return list(iflatten(iterable))
which pushes appending down into the C code of list().

Terry J. Reedy