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

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.

.

Relevant Pages

  • Re: What is the "functional" way of doing this?
    ... They were run in IDLE from their own windows. ... 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 ... As soon as the size of the list increases the generator function ...
    (comp.lang.python)
  • Re: C Application running on single processor only
    ... one completely remain idle. ... application vendor to make it multithreaded as they may charge company ... In order to understand recursion you must first understand recursion. ...
    (comp.unix.aix)