What is the "functional" way of doing this?

[Chris Mellon]

On 7/31/07, Ricardo Aráoz <ricaraoz at gmail.com> wrote:
> Steven D'Aprano wrote:
> > On Tue, 31 Jul 2007 09:01:42 -0300, Ricardo Aráoz wrote:
> >
> >> Considering I am a beginner I did a little test. Funny results too. The
> >> function I proposed (lists1.py) took 11.4529998302 seconds, while the
> >> other one (lists2.py) took 16.1410000324 seconds, thats about 40% more.
> >> They were run in IDLE from their own windows (F5).
> >
> > [snip code]
> >
> > You may find that using the timeit module is better than rolling your own
> > timer.
> >
> >>>> def recursive_func(n):
> > ...     if n > 0:
> > ...             return [n % 26] + recursive_func(n/26)
> > ...     else:
> > ...             return []
> > ...
> >>>> def generator_func(n):
> > ...     def mseq(n):
> > ...             while n > 0:
> > ...                     n, a = divmod(n, 26)
> > ...                     yield a
> > ...     return list(mseq(n))
> > ...
> >>>> import timeit
> >>>> N = 10**6+1
> >>>> timeit.Timer("recursive_func(N)",
> > ... "from __main__ import N, recursive_func").repeat()
> > [16.48972487449646, 17.000514984130859, 16.520529985427856]
> >>>> timeit.Timer("generator_func(N)",
> > ... "from __main__ import N, generator_func").repeat()
> > [27.938560009002686, 28.970781087875366, 23.977837085723877]
> >
> >
> > If you're going to compare speeds, you should also test this one:
> >
> >>>> def procedural_func(n):
> > ...     results = []
> > ...     while n > 0:
> > ...         n, a = divmod(n, 26)
> > ...         results.append(a)
> > ...     return results
> > ...
> >>>> timeit.Timer("procedural_func(N)",
> > ... "from __main__ import N, procedural_func").repeat()
> > [15.577107906341553, 15.60145378112793, 15.345284938812256]
> >
> >
> > I must admit that I'm surprised at how well the recursive version did, and
> > how slow the generator-based version was. But I'd be careful about drawing
> > grand conclusions about the general speed of recursion etc. in Python from
> > this one single example. I think this is simply because the examples tried
> > make so few recursive calls. Consider instead an example that makes a few
> > more calls:
> >
> >>>> N = 26**100 + 1
> >>>>
> >>>> timeit.Timer("recursive_func(N)",
> > ... "from __main__ import N, recursive_func").repeat(3, 10000)
> > [7.0015969276428223, 7.6065640449523926, 6.8495190143585205]
> >>>> timeit.Timer("generator_func(N)",
> > ... "from __main__ import N, generator_func").repeat(3, 10000)
> > [3.56563401222229, 3.1132731437683105, 3.8274538516998291]
> >>>> timeit.Timer("procedural_func(N)",
> > ... "from __main__ import N, procedural_func").repeat(3, 10000)
> > [3.3509068489074707, 4.0872640609741211, 3.3742849826812744]
> >
> >
>
> Yup! As soon as the size of the list increases the generator function
> gets better (50% in my tests). But it's interesting to note that if the
> list is within certain limits (I've tested integers (i.e. 2,100,000,000
> => 7 member list)) and you only vary the times the funct. is called then
> the recursive one does better.
>
>

Not especially surprising. Suspending and resuming a generator is
naturally more expensive than a single function call. The advantages
of generators are time/space tradeoffs, greater expressiveness, and
state preservation (not used here).