can multi-core improve single funciton?
gerhard at proclos.com
Tue Feb 10 13:41:25 CET 2009
> 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:
>>>> 'from __main__ import fib').timeit(1)
> 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.
I agree to 100% to this.
btw. the timeings are not that different for the naive recursion in
OP's version and yours.
fib(500) on my machine:
OP's: 0.00116 (far away from millions of years)
This here: 0.000583
Gabriel's while loop: 0.000246
The fastest algorithm I've found does fib(1000000) in .25seconds on my machine.
However, I have not found a way to parallelize this algorithm and I
think it is not possible.
To come back to the original question. Yes it is possible; however
there are quite some restrictions about it. In case of the naive
recursion it was possible to get a speedup of more than 3 times on a 4
core machine. With the highly optimised version mentioned above, I had
no success in utilizing more than one core.
As conclusion I would say, Yes, a single function can profit from
multiple cores, but sometimes a better algorithm delivers better
results than using more cores. However, it is possible that a slower
but parallelizable algorithm might outperform the best serial
algorithm, with enough cores :).
More information about the Python-list