Re: What is the "functional" way of doing this?

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.


.

Relevant Pages

  • Re: Help- Recursion v. Iter Speed comparison
    ... Recursion is usually slower than ... >> Would using a generator be faster than recursion? ... > def f1: ... list comprehension approach ...
    (comp.lang.python)
  • RE: bad generator performance
    ... Aside from the recursion question... ... To make it work I had to build a data tree - I used the files and ... the generator version takes about 1/4 of the time that the ... for iterator in: ...
    (comp.lang.python)
  • Re: bad generator performance
    ... I would assume the recursion is ... good idea to represent the bookmarks as a tree (with folders as internal ... the generator version takes about 1/4 of the time that the ...
    (comp.lang.python)
  • Re: What is the "functional" way of doing this?
    ... They were run in IDLE from their own windows. ... You may find that using the timeit module is better than rolling your own ... If you're going to compare speeds, you should also test this one: ... grand conclusions about the general speed of recursion etc. in Python from ...
    (comp.lang.python)
  • Re: What is the "functional" way of doing this?
    ... grand conclusions about the general speed of recursion etc. in Python from ... As soon as the size of the list increases the generator function ... Not especially surprising. ... naturally more expensive than a single function call. ...
    (comp.lang.python)