<s> fibo_seq = [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:5> , <NUM_LIT:8> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <EOL> <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <EOL> <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <EOL> <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] <EOL> from functools import lru_cache <EOL> def fibonacci ( n ) : <EOL> if n < <NUM_LIT:2> : <EOL> return n <EOL> return fibonacci ( n - <NUM_LIT:2> ) + fibonacci ( n - <NUM_LIT:1> ) <EOL> @ lru_cache ( ) <EOL> def fibonacci2 ( n ) : <EOL> if n < <NUM_LIT:2> : <EOL> return n <EOL> return fibonacci2 ( n - <NUM_LIT:2> ) + fibonacci2 ( n - <NUM_LIT:1> ) <EOL> def memoize ( func ) : <EOL> '''<STR_LIT>''' <EOL> cache = { } <EOL> def memoized ( * args ) : <EOL> if args not in cache : <EOL> cache [ args ] = func ( * args ) <EOL> return cache [ args ] <EOL> return memoized <EOL> def test ( ) : <EOL> for i , expected in enumerate ( fibo_seq [ : <NUM_LIT> ] ) : <EOL> print ( i , expected ) <EOL> assert fibonacci ( i ) == expected <EOL> def chronograph ( ) : <EOL> global fibonacci <EOL> from time import time <EOL> t0 = time ( ) <EOL> n = <NUM_LIT:32> <EOL> res = fibonacci ( n ) <EOL> t1 = time ( ) <EOL> print ( n , res , format ( t1 - t0 , '<STR_LIT>' ) ) <EOL> t0 = time ( ) <EOL> res = fibonacci2 ( n ) <EOL> t1 = time ( ) <EOL> print ( n , res , format ( t1 - t0 , '<STR_LIT>' ) ) <EOL> t0 = time ( ) <EOL> fibonacci = memoize ( fibonacci ) <EOL> res = fibonacci ( n ) <EOL> t1 = time ( ) <EOL> print ( n , res , format ( t1 - t0 , '<STR_LIT>' ) ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> chronograph ( ) </s>
