Memoization in Python

memoizer.py

import time

import numpy as np


class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}

    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fn(*args)
        return self.memo[args]


@Memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


@Memoize
def factorial(n):
    fact = 1
    for i in range(1, n + 1):
        fact = fact * i
    return fact


@Memoize
def bin_search(arr, l, r, x):
    if r >= l:
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return bin_search(arr, l, mid - 1, x)
        else:
            return bin_search(arr, mid + 1, r, x)
    else:
        return -1


arr = tuple(np.random.randint(-100, 100, 1000000))
x = 10

tick1 = time.time()

""" First Pass """
# _ = factorial(1000)
# _ = fib(80)
_ = bin_search(arr, 0, len(arr) - 1, x)
tick2 = time.time()
print(tick2 - tick1)

""" Second Pass """
# _ = factorial(1000)
# _ = fib(80)
_ = bin_search(arr, 0, len(arr) - 1, x)
tick3 = time.time()
print(tick3 - tick2)

# Fibonacci
# 1st pass: 0.007365226745605469
# 2nd pass: 3.218650817871094e-05

# Factorial
# 1st pass: 0.00025081634521484375
# 2nd pass: 3.0517578125e-05

# Binary Search
# 1st pass: 0.9389126300811768
# 2nd pass: 0.029410600662231445