Memoization, Code Optimization and Time Complexity¶
- based on the Latin word memorandum, meaning "to be remembered"
- 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))
fib at 30th position = 1346269 fib function count = 2692537
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(2n-1) + O(2n-2) + O(1)
- T(n) = O(2n)
- 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)
Help on module timeit:
NAME
timeit - Tool for measuring execution time of small code snippets.
MODULE REFERENCE
https://docs.python.org/3.6/library/timeit
The following documentation is automatically generated from the Python
source files. It may be incomplete, incorrect or include features that
are considered implementation detail and may vary between Python
implementations. When in doubt, consult the module reference at the
location listed above.
DESCRIPTION
This module avoids a number of common traps for measuring execution
times. See also Tim Peters' introduction to the Algorithms chapter in
the Python Cookbook, published by O'Reilly.
Library usage: see the Timer class.
Command line usage:
python timeit.py [-n N] [-r N] [-s S] [-t] [-c] [-p] [-h] [--] [statement]
Options:
-n/--number N: how many times to execute 'statement' (default: see below)
-r/--repeat N: how many times to repeat the timer (default 3)
-s/--setup S: statement to be executed once initially (default 'pass').
Execution time of this setup statement is NOT timed.
-p/--process: use time.process_time() (default is time.perf_counter())
-t/--time: use time.time() (deprecated)
-c/--clock: use time.clock() (deprecated)
-v/--verbose: print raw timing results; repeat for more digits precision
-u/--unit: set the output time unit (usec, msec, or sec)
-h/--help: print this usage message and exit
--: separate options from statement, use when statement starts with -
statement: statement to be timed (default 'pass')
A multi-line statement may be given by specifying each line as a
separate argument; indented lines are possible by enclosing an
argument in quotes and using leading spaces. Multiple -s options are
treated similarly.
If -n is not given, a suitable number of loops is calculated by trying
successive powers of 10 until the total time is at least 0.2 seconds.
Note: there is a certain baseline overhead associated with executing a
pass statement. It differs between versions. The code here doesn't try
to hide it, but you should be aware of it. The baseline overhead can be
measured by invoking the program without arguments.
Classes:
Timer
Functions:
timeit(string, string) -> float
repeat(string, string) -> list
default_timer() -> float
CLASSES
builtins.object
Timer
class Timer(builtins.object)
| Class for timing execution speed of small code snippets.
|
| The constructor takes a statement to be timed, an additional
| statement used for setup, and a timer function. Both statements
| default to 'pass'; the timer function is platform-dependent (see
| module doc string). If 'globals' is specified, the code will be
| executed within that namespace (as opposed to inside timeit's
| namespace).
|
| To measure the execution time of the first statement, use the
| timeit() method. The repeat() method is a convenience to call
| timeit() multiple times and return a list of results.
|
| The statements may contain newlines, as long as they don't contain
| multi-line string literals.
|
| Methods defined here:
|
| __init__(self, stmt='pass', setup='pass', timer=<built-in function perf_counter>, globals=None)
| Constructor. See class doc string.
|
| autorange(self, callback=None)
| Return the number of loops and time taken so that total time >= 0.2.
|
| Calls the timeit method with *number* set to successive powers of
| ten (10, 100, 1000, ...) up to a maximum of one billion, until
| the time taken is at least 0.2 second, or the maximum is reached.
| Returns ``(number, time_taken)``.
|
| If *callback* is given and is not None, it will be called after
| each trial with two arguments: ``callback(number, time_taken)``.
|
| print_exc(self, file=None)
| Helper to print a traceback from the timed code.
|
| Typical use:
|
| t = Timer(...) # outside the try/except
| try:
| t.timeit(...) # or t.repeat(...)
| except:
| t.print_exc()
|
| The advantage over the standard traceback is that source lines
| in the compiled template will be displayed.
|
| The optional file argument directs where the traceback is
| sent; it defaults to sys.stderr.
|
| repeat(self, repeat=3, number=1000000)
| Call timeit() a few times.
|
| This is a convenience function that calls the timeit()
| repeatedly, returning a list of results. The first argument
| specifies how many times to call timeit(), defaulting to 3;
| the second argument specifies the timer argument, defaulting
| to one million.
|
| Note: it's tempting to calculate mean and standard deviation
| from the result vector and report these. However, this is not
| very useful. In a typical case, the lowest value gives a
| lower bound for how fast your machine can run the given code
| snippet; higher values in the result vector are typically not
| caused by variability in Python's speed, but by other
| processes interfering with your timing accuracy. So the min()
| of the result is probably the only number you should be
| interested in. After that, you should look at the entire
| vector and apply common sense rather than statistics.
|
| timeit(self, number=1000000)
| Time 'number' executions of the main statement.
|
| To be precise, this executes the setup statement once, and
| then returns the time it takes to execute the main statement
| a number of times, as a float measured in seconds. The
| argument is the number of times through the loop, defaulting
| to one million. The main statement, the setup statement and
| the timer function to be used are passed to the constructor.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
FUNCTIONS
default_timer = perf_counter(...)
perf_counter() -> float
Performance counter for benchmarking.
repeat(stmt='pass', setup='pass', timer=<built-in function perf_counter>, repeat=3, number=1000000, globals=None)
Convenience function to create Timer object and call repeat method.
timeit(stmt='pass', setup='pass', timer=<built-in function perf_counter>, number=1000000, globals=None)
Convenience function to create Timer object and call timeit method.
DATA
__all__ = ['Timer', 'timeit', 'repeat', 'default_timer']
FILE
/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/timeit.py
In [43]:
#print(globals())
import timeit
print(timeit.timeit('fib(30)', number=1, globals=globals()))
0.7455664590088418
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))
fib at 60th position = 2504730781961 fib function count = 119
In [45]:
import timeit
print(timeit.timeit('MemoizedFib(1000)', number=1, globals=globals()))
0.002014205005252734
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)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Python code optimization¶
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()
Out[47]:
0.005
In [48]:
sys.maxsize
Out[48]:
9223372036854775807
In [49]:
import timeit
In [50]:
code = '''
x = 47
x = x * 2
'''
timeit.timeit(stmt=code)
Out[50]:
0.046036384999752045
In [51]:
code = '''
x = 47
x = x << 1
'''
timeit.timeit(stmt=code)
Out[51]:
0.07047916000010446
In [38]:
code = '''
x = 47
x = x + x
'''
timeit.timeit(stmt=code)
Out[38]:
0.04736856800445821
Time complexity¶
- Time complexity of various Python built-in data sturctures and functions
- https://wiki.python.org/moin/TimeComplexity
In [ ]: