can multi-core improve single funciton?
lie.1296 at gmail.com
Tue Feb 10 07:43:20 EST 2009
On Tue, 10 Feb 2009 14:28:15 +0800, oyster wrote:
> I mean this
> def fib(n):
> if n<=1:
> return 1
> return fib(n-1)+fib(n-2)
> timeit(fib(500)) #this show 20 seconds
> timeit(fib(500)) #this show 10 seconds [/code]
> Is it possible?
> and more, can threads/multi-processors/clusters be used to improve fib?
Of course multi-core processor can improve single function using
multiprocessing, as long as the function is parallelizable. The Fibonacci
function is not a parallelizable function though.
However, there are ways to improve your fibonacci function. Either put
off the recursion or implement a memoization. An imperative fibonacci is
much faster than a naive recursion one because a naive recursive
fibonacci function is O(2**n) while the imperative one O(n). Memoization
must be used to help recursive fibonacci to become O(n).
More information about the Python-list