flatten(), [was Re: map/filter/reduce/lambda opinions ...]
twic at urchin.earth.li
Thu Jul 7 18:55:24 CEST 2005
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
> But they're all respectable times so everyone wins. ;-)
Everyone shall have medals!
They travel the world in their ice cream van ...
More information about the Python-list