#!/usr/bin/env python
# coding: utf-8

# # Memoization, Code Optimization and Time Complexity
# - based on the Latin word memorandum, meaning "to be remembered" <img src="./resources/brain.jpg" width="25%" style="float:right">
# - similar to word memorization, its a technique used in coding to improve program runtime by memorizing intermediate solutions
# - if an intermediate results (from some computations) are used over and again, the results can be remembered/stored to avoid unnecessary repeating calculations
# - using dict type datastructure, one can memoize intermediate results from functions esp. in recurisive solutions

# ## naive recursive fib function

# In[41]:


count = 0
def fib(n):
    global count
    count += 1
    if n <= 1:
        return 1
    f = fib(n-1) + fib(n-2)
    return f

n=30 #40, 50? takes a while
print("fib at {}th position = {}".format(n, fib(n)))
print("fib function count = {}".format(count))


# ## theoritical computational complexity
# - Worst case Big-Oh Time Complexity: O(n) = time to calculate Fib(n-1) + Fib(n-2) + time to add them: O(1)
#     - T(n) = T(n-1) + T(n-2) + O(1)
#     - T(n) = O(2<sup>n-1</sup>) + O(2<sup>n-2</sup>) + O(1)
#     - T(n) = O(2<sup>n</sup>)
# - Space Complexity = O(n) due to call stack

# ## finding actual time - timeit
# - timeit - measures execution time of small code snippets
# - timeit.timeit(stmt='pass', setup='pass', timer=[default timer], number=1000000, globals=None)
# - returns time in seconds

# In[42]:


import timeit
help(timeit)


# In[43]:


#print(globals())
import timeit
print(timeit.timeit('fib(30)', number=1, globals=globals()))


# ## memoized recursive fib function

# In[44]:


memo = {}
count = 0
def MemoizedFib(n):
    global memo, count
    count += 1
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = MemoizedFib(n-1) + MemoizedFib(n-2)
    return memo[n]

n=60 #try 40, 50, 60
print("fib at {}th position = {}".format(n, MemoizedFib(n)))
print("fib function count = {}".format(count))   


# In[45]:


import timeit
print(timeit.timeit('MemoizedFib(1000)', number=1, globals=globals()))


# ## computational complexity of memoized fib
# - Time Complexity - O(n)
# - Space Complexity - O(n)

# ## exercise
# - Write a program that finds factorials of a bunch of positive integer numbers. Would memoization improve time complexity of the program? 

# In[46]:


# find the factorials of the first 20 positive numbers
# optimize the program so it finds the factorials in the 
# shortest time possible
nums = list(range(1, 21))
print(nums)


# # Python code optimization
# - https://wiki.python.org/moin/PythonSpeed/PerformanceTips

# ## Summary
# 
# - use functions and local variables instead of globals, eventhough function calls are relatively high
# - avoid dot . member access specifier
# - user built-in list.sort and sorted with key using itemgetter function if required
# - avoid string concatenation; use "".join(somelist) instead
# - use list comprehension and map() instead of loops
# - while working with dict (esp. initializing), use try catch instead of key test
# - use defaultdict class from collections
# - doing stuff less often - change sys.setswitchinterval(sys.maxsize) to as high as possible if not running threads and catching signals (default is 100?)
# - use addition and subtraction instead of multiplicaiton and divisions

# In[47]:


import sys
sys.getswitchinterval()


# In[48]:


sys.maxsize


# In[49]:


import timeit


# In[50]:


code = '''
x = 47
x = x * 2
'''
timeit.timeit(stmt=code)


# In[51]:


code = '''
x = 47
x = x << 1
'''
timeit.timeit(stmt=code)


# In[38]:


code = '''
x = 47
x = x  + x
'''
timeit.timeit(stmt=code)


# ## Time complexity
# - Time complexity of various Python built-in data sturctures and functions 
# - https://wiki.python.org/moin/TimeComplexity

# In[ ]: