What is the "functional" way of doing this?

[Steven D'Aprano]

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]


-- 
Steven.