can multi-core improve single funciton?

[Chris Rebert]

On Tue, Feb 10, 2009 at 12:45 AM, Steven D'Aprano
<steven at remove.this.cybersource.com.au> wrote:
> On Tue, 10 Feb 2009 18:18:23 +1000, Gerhard Weis wrote:
>
>> Once I have seen Haskell code, that ran fibonacci on a 4 core system.
>>
>> The algorithm itself basically used an extra granularity paramet until
>> which new threads will be sparked. e.g. fib(40, 36) means, calculate
>> fib(40) and spark threads until n=36. 1. divide: fib(n-1), fib(n-2)
>> 2. divide: fib(n-2), fib(n-3)
>> 3. divide: fib(n-3), fib(n-4)
>>
>> We tried this code on a 4 core machine using only 1 core and all 4
>> cores. 1 core wallclock: ~10s
>> 4 core wallclock: ~3s
>
> Three seconds to calculate fib(40) is terrible. Well, it's a great saving
> over ten seconds, but it's still horribly, horribly slow.
>
> Check this out, on a two-core 2.2 GHz system:
>
>
>>>> import timeit
>>>> timeit.Timer('fib(40)', 'from __main__ import fib').timeit(1)
> 7.2956085205078125e-05
>
> That's five orders of magnitude faster. How did I do it? I used a better
> algorithm.
>
>
> def fib(n, a=1, b=1):
>    if n==0:
>        return a
>    elif n==1:
>        return b
>    return fib(n-1, b, a+b)
>
>
> And for the record:
>
>>>> fib(500)
> 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626L
>>>> timeit.Timer('fib(500)', 'from __main__ import fib').timeit(1)
> 0.00083398818969726562
>
> Less than a millisecond, versus millions of years for the OP's algorithm.
> I know which I would choose. Faster hardware can only go so far in hiding
> the effect of poor algorithms.

Indeed. And apparently memoization can hide it also:

$ #memoization added to OP's code
$ python -m timeit -s 'from memoized_naive_recursive_version import
fib' 'fib(40)'
1000000 loops, best of 3: 0.639 usec per loop
$ #your code
$ python -m timeit -s 'from your_version import fib' 'fib(40)'
100000 loops, best of 3: 15.4 usec per loop
$ cat memoized_naive_recursive_version.py
def memoize(func):
    cache = {}
    def memoized(*args):
        if args in cache:
            return cache[args]
        else:
            result = func(*args)
            cache[args] = result
            return result
    return memoized

@memoize
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

However, the naive recursive version fails by exceeding the maximum
recursion depth if N is too large, whereas your version continues to
succeed for a much higher limit of N.

Cheers,
Chris

-- 
Follow the path of the Iguana...
http://rebertia.com