flatten(), [was Re: map/filter/reduce/lambda opinions ...]

[Tom Anderson]

On Thu, 7 Jul 2005, Ron Adam wrote:

> Stian Søiland wrote:
>
> > Or what about a recursive generator?

That's the sort of thing i like to see!

> Ok, lets see...  I found a few problems with the testing (and corrected 
> it) so the scores have changed.  My sort in place routines were cheating 
> because the lists weren't reset between runs so it had the advantage 
> after the first time though of sorting already sorted list.

Aaagh, of course!

> And Tom's recursive no copy had a bug which kept a reference to one of 
> it's arguments so it's output was doubling the list.

Oops. I really should have written tests as well as benchmarks.

> And the hasattr function was slowing everyone down, so I inlined it for 
> everyone who used it. Using a 1000 item list and starting with a flat 
> list and increasing the depth (unflatten) to shallow, medium, and deep. 
> (but not so deep to cause recursion errors.)

I wrote a new and improved test harness myself, but left my laptop at 
work, and haven't been in today due to the bombs :(. I ran tests out to 
100 000 elements, and your implementation was still faster, although not 
by a lot - but then i hadn't found the bugs you had, so it's all moot.

> And the winners are...
>
> Stians flatten generator is nearly tied with Tom's recursive zerocopy. 
> My nonrecursive inplace is faster for very shallow lists, but Tom's 
> quickly over takes it.  I was able to improve my nonrecursive copy 
> flatten a bit, but not enough to matter.

I also came up with an improvement to my version that should cut down on 
recursive calls - a sort of recursion unrolling. I doubt it wouldd make 
much difference, though.

> So Tom's recursive zerocopy is the overall winner with Stian's flatten 
> generator close behind and just barely winning out in the very deep 
> catagory.

\o/

> But they're all respectable times so everyone wins. ;-)

Everyone shall have medals!

tom

-- 
They travel the world in their ice cream van ...