can multi-core improve single funciton?
sturlamolden
sturlamolden at yahoo.no
Wed Feb 18 19:50:58 EST 2009
On Feb 10, 8:38 am, Paul McGuire <pt... at austin.rr.com> wrote:
> Even worse than linear, the function is recursive, which as I
> understand it, is inherently a no-no when looking for code that is
> parallel-friendly.
There is no way to parallelize Fibonacci numbers computed with linear
time complexity, as we must know fib(n-1) to compute fib(n). But if we
were to use Oyster's recursive version, which has geometric
complexity, one could parallelize with a 'forkjoin' scheme.
Anyhow, this runs in amortized linear time and would be a lot faster:
def fib(n):
while True:
try:
return fib.seq[n]
except AttributeError:
fib.seq = [0, 1, 1]
except IndexError:
fib.seq.append( fib.seq[-2] +
fib.seq[-1] )
S.M.
More information about the Python-list
mailing list