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
