import time
import numpy as np
import gc

def fib_stack1(n):
    """ Original function """
    assert type(n) is int, 'Expected an integer as input.'
    if n < 2:
        return n
    else:
        stack = [0, 1]
        for i in range(n-1):
            stack.append(stack[-1] + stack[-2])
        return stack[-1]

def fib_stack2(n):
    """ Modified function """
    assert type(n) is int, 'Expected an integer as input.'
    if n < 2:
        return n
    else:
        stack = [0, 1]
        for i in range(n-1):
            stack.append(stack[-1] + stack[-2])
            ### CHANGE ###
            stack.pop(-3)
            ##############
        return stack[-1] 


rec1 = []
rec2 = []
rec3 = []
rec4 = []
for _ in range(5):
    t1 = time.time()
    fib_stack1(99999)  
    t2 = time.time()
    rec1.append(t2-t1)
    
    t1 = time.time()
    fib_stack2(99999)  
    t2 = time.time()
    rec2.append(t2-t1)
    
    gc.disable()
    
    t1 = time.time()
    fib_stack1(99999)  
    t2 = time.time()
    rec3.append(t2-t1)
    
    t1 = time.time()
    fib_stack2(99999)  
    t2 = time.time()
    rec4.append(t2-t1)
    
    gc.enable()
print(np.array(rec1).mean())
print(np.array(rec2).mean())
print(np.array(rec3).mean())
print(np.array(rec4).mean())