[prev in list] [next in list] [prev in thread] [next in thread]
List: python-list
Subject: Re: flatten(), [was Re: map/filter/reduce/lambda opinions ...]
From: Tom Anderson <twic () urchin ! earth ! li>
Date: 2005-07-07 16:55:24
Message-ID: Pine.LNX.4.62.0507071742120.13945 () urchin ! earth ! li
[Download RAW message or body]
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 ...
--
http://mail.python.org/mailman/listinfo/python-list
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic