# return the first n fibonacci numbers #version 1: for loop, list, nonrecursive from pylab import * def fib(N): #req: N>=0 , no error checking if N==0: ret =[0] return ret if N==1: ret = [0, 1] return ret ret = [0,1] for n in range(2,N+1): ret+=[ret[n-1]+ret[n-2]] return ret #version 2: for loop, numpy, nonrecursive def fib2(N): #req: N>=0, no error checking x=empty(N+1) if N==0: #careful! x[0]=0 return x if N==1: x[1]= 1 return x x[:2]= [0,1] for n in arange(2, N+1): x[n] = x[n-1] + x[n-2] return x #version 3: generator, list, nonrecursive def fib3(N): a,b = 0,1 i=0 while i<=N: yield a a,b = b, a+b i= i+1 from timeit import timeit; if __name__=='__main__': # print fib(5) # print fib2(5) # print fromiter(fib3(5), np.float) #print list(fib3(5)) X = zeros((3,1000)) # import cProfile # cProfile.run('from ex301 import fib2; fib2(1000)') # for i in range(size(X,1)): X[0,i] = timeit("fib(%d)"%i, setup='from w5_3 import fib' ,number=1)/1; X[1,i] = timeit("fib2(%d)"%i,setup='from w5_3 import fib2' , number=1)/1; X[2,i] = timeit("list(fib3(%d))"%i, setup='from w5_3 import fib3' , number=1)/1; figure(0) plot(arange(size(X,1)), X[0,:],'r', arange(size(X,1)), X[1,:],'g', arange(size(X,1)), X[2,:], 'b' ) # explorer several issues. # number = 1 versus 1000 # why numpy is so slow? # explore when N is too big