Python for Finance

Object Oriented Programming and Algorithm

Analysis

Juan F. Imbet Ph.D. 1

Python for Finance

Object Oriented Programming

Object Oriented Programming is a programming paradigm that uses objects and
classes. It is useful for creating reusable code, and it can also be used to create complex
programs. Object Oriented Programming is done using the class keyword. Classes are
used to create objects, which are instances of a class. Objects can have attributes and
methods. Attributes are variables that belong to an object, and methods are functions
that belong to an object.

class Asset:
pass

Juan F. Imbet Ph.D. 2

Python for Finance

Constructor
A constructor is a special method that is used to initialize an object. It is useful for
creating objects with default values. Constructors are done using the __init__
method. The __init__ method has two arguments: self and args . The self
argument is used to refer to the object itself, and the args argument is used to pass
arguments to the constructor. The __init__ method is called when an object is
created.

class Asset:
def __init__(self, name, price):
self.name = name
self.price = price

asset = Asset('Bitcoin', 50000)

Juan F. Imbet Ph.D. 3

Python for Finance

Attributes
Attributes are variables that belong to an object. They are useful for storing information
about an object. Attributes can be accessed using the . operator. Attributes can also
be accessed using the getattr function. Attributes can be set using the = operator.
Attributes can also be set using the setattr function. Attributes can be deleted using
the del operator. Attributes can also be deleted using the delattr function.

asset.name # Get attribute

asset.price = 60000 # Set attribute
asset.type = 'Cryptocurrency' # Set attribute not defined in constructor

Juan F. Imbet Ph.D. 4

Python for Finance

Methods
Methods are functions that belong to an object. Methods can be called using the ()
operator. Since they are functions they are defined using the def keyword and always
contain the self argument first.

class Asset:
...

def double_price(self):
return self.price*2

Juan F. Imbet Ph.D. 5

Python for Finance

Dunders (Magic methods)

Dunders are special methods that are used to avoid operator overloading. They are
useful for creating objects that behave like built-in objects. Dunders are done using the
__ keyword. For example, the + operator can be used to add two numbers, but it can
also be used to add two strings.

class Vector2D:
def __init__(self, x, y):
self.x = x
self.y = y

def __add__(self, other):

return Vector2D(self.x + other.x, self.y + other.y)

v1 = Vector2D(1, 2)
v2 = Vector2D(3, 4)
v3 = v1 + v2
Juan F. Imbet Ph.D. 6
Python for Finance

Dunders (Magic methods)

Non-exhaustive list of dunders

__init__ # Constructor
__str__ # String representation
__add__ # Addition +
__sub__ # Subtraction -
__mul__ # Multiplication *
__truediv__ # Division /
__floordiv__ # Floor division //
__mod__ # Modulo %
__pow__ # Exponentiation **
__lt__ # Less than <
__le__ # Less than or equal to <=
__eq__ # Equal to ==
__ne__ # Not equal to !=
__gt__ # Greater than >
__ge__ # Greater than or equal to >=

Juan F. Imbet Ph.D. 7

 Example: Portfolio Class
Python for Finance

A portfolio consists of a list of assets. Each asset has a name (identifier) as well as a
history of prices.

class Asset:

self.mu = np.nan # Expected return

self.sigma = np.nan # Volatility

def __init__(self, name: str, price_history: pd.DataFrame):

self.name = name
self.price_history = price_history
self.compute_mu()
self.compute_sigma()

def compute_mu(self):
self.mu = self.price_history.pct_change().mean()

def compute_sigma(self):
self.sigma = self.price_history.pct_change().std()
Juan F. Imbet Ph.D. 8
Python for Finance

Example: Portfolio Class

class Portfolio:

self.mu = np.nan # Expected return

self.sigma = np.nan # Volatility

def __init__(self, assets: List[Asset], weights: List[float]):

self.assets = assets
self.weights = weights
self.compute_mu()
self.compute_sigma()

def compute_mu(self):
self.mu = np.sum([asset.mu * weight for asset, weight in zip(self.assets, self.weights)])

def compute_sigma(self):
# Covariance matrix
cov = np.cov([asset.price_history.pct_change().dropna() for asset in self.assets])
# Weighted covariance matrix
cov = np.diag(self.weights) @ cov @ np.diag(self.weights)
# Portfolio volatility
self.sigma = np.sqrt(np.diag(cov).sum())

Juan F. Imbet Ph.D. 9

Python for Finance

Algorithm Analysis

Juan F. Imbet Ph.D. 10

Python for Finance

What is an algorithm
An algorithm is a set of instructions that are used to solve a problem.

Example
Find the maximum value in a list of numbers.

1. Set the maximum value to the first value in the list.

2. For each value in the list, if the value is greater than the maximum value, then set
the maximum value to that value.
3. Return the maximum value after looking at all values in the list.

Juan F. Imbet Ph.D. 11

Python for Finance

How can we compare algorithms?

Time complexity - How long does it take to run the algorithm?
Space complexity - How much memory does the algorithm use?
Correctness - Does the algorithm solve the problem, or does it approximate the
solution?

Juan F. Imbet Ph.D. 12

Python for Finance

Big O Notation
One way to compare algorithms is by understanding its behavior as the size of the
problem increases. Big O notation is used to describe the time complexity of an
algorithm.

We say an algorithm has a time complexity if the number of operations is

bounded by for some constant and for all greater than some constant .

They normally considered the amount of steps that the algorithm has to perform in the
worst case scenario. E.g. sorting a list that is in reverse order.

Juan F. Imbet Ph.D. 13

Python for Finance

Examples of Big O Notation

- Constant time, and algorithm that always takes the same amount of time to
run. E.g. accessing an element in an array.

a = range(1000000)
%timeit a[0] # O(1)
%timeit a[500000] # O(1)

Differences are due to CPU caching, practically they are the same.

66.8 ns ± 0.124 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
86.2 ns ± 0.192 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Juan F. Imbet Ph.D. 14

Python for Finance

Examples of Big O Notation

- Linear time, an algorithm that takes steps to run. E.g. find the maximum
value in a list of numbers.

import random
random.seed(0)
a = [random.random() for _ in range(1000)]
%timeit max(a) # O(n)
a = [random.random() for _ in range(1000000)]
%timeit max(a) # O(n)

Second examples takes 1000 times longer.

12.1 µs ± 4.11 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
12 ms ± 10.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Juan F. Imbet Ph.D. 15

 Examples of Big O Notation
Python for Finance

- Quadratic time, an algorithm that takes steps to run. Sort a list of

numbers using bubble sort.

import random
random.seed(0)
a = [random.random() for _ in range(1000)]
%timeit bubble_sort(a) # O(n^2)
a = [random.random() for _ in range(10000)]
%timeit bubble_sort(a) # O(n^2)

Increasing the size ten times increases the time by 100 times.

37 ms ± 107 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

4.09 s ± 24.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Juan F. Imbet Ph.D. 16

Python for Finance

Appendix: Bubble Sort

def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Last i elements are already in place
for j in range(0, n - i - 1):
# Traverse the array from 0 to n-i-1
# Swap if the element found is greater than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

Juan F. Imbet Ph.D. 17

Python for Finance

Polynomial time
When an algorithm has a time complexity of for some constant , we say it has
polynomial time. Polynomial time algorithms are considered efficient.

Example NumPy's matrix inversion is approximately . This means that increasing

the size of the matrix by 10 times increases the time by 1000 times.

DO NOT RUN IN A SLOW COMPUTER

import numpy as np
import random
random.seed(0)
a = np.random.rand(1000, 1000)
%timeit np.linalg.inv(a) # O(n^3)
a = np.random.rand(100000, 100000)
%timeit np.linalg.inv(a) # O(n^3)

Juan F. Imbet Ph.D. 18

Python for Finance

Logarithmic time
When an algorithm has a time complexity of , we say it has logarithmic time.
Logarithmic time algorithms are considered efficient.

Example Binary search is a search algorithm that finds the position of a target value
within a sorted array. Increasing the size by 1000 barely changes the time.

a = range(1000000)
%timeit binary_search(a, 500000) # O(log n)
a = range(1000000000)
%timeit binary_search(a, 500000) # O(log n)

5.18 µs ± 9.36 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
7.79 µs ± 72 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

Juan F. Imbet Ph.D. 19

Python for Finance

Appendix: Binary Search

def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < target:
low = mid + 1
elif arr[mid] > target:
high = mid - 1
else:
return mid
return -1

Juan F. Imbet Ph.D. 20

Python for Finance

Exponential time
When an algorithm has a time complexity of , we say it has exponential time.
Exponential time algorithms are considered inefficient.

Example The Power Set problem involves finding all possible subsets of a given set,
including the empty set and the set itself. For a set with n elements, the number of
subsets is , which grows exponentially with the size of the set. An extra element
almost doubles the time.

s = range(5)
%timeit generate_power_set(s) # O(2^n)
s = range(6)
%timeit generate_power_set(s) # O(2^n)

6.05 µs ± 18.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
10.7 µs ± 20.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
Juan F. Imbet Ph.D. 21
Python for Finance

Appendix: Compute the Power Set

def generate_power_set(s):
if len(s) == 0:
return [[]] # Base case: empty set has one subset, which is the empty set

subsets = []
first_element = s[0]
remaining_elements = s[1:]

# Recursive call to generate subsets without the first element

subsets_without_first = generate_power_set(remaining_elements)

# Combine subsets without the first element with subsets including the first element
for subset in subsets_without_first:
subsets.append(subset) # Add subset without the first element
subsets.append([first_element] + subset) # Add subset including the first element

return subsets

Juan F. Imbet Ph.D. 22

Python for Finance

Factorial time
When an algorithm has a time complexity of , we say it has factorial time.
Factorial time algorithms are considered inefficient.

One example of an algorithm with a time complexity of is the brute-force

solution for the permutation problem. The permutation problem involves finding all
possible permutations of a given set of elements.

s = list(range(5))
%timeit generate_permutations(s) # O(n!)
s = list(range(6))
%timeit generate_permutations(s) # O(n!)

137 µs ± 291 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
822 µs ± 587 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Juan F. Imbet Ph.D. 23

Python for Finance

Appendix: Compute the Permutations

def generate_permutations(elements):
permutations = []
generate_permutations_recursive(elements, [], permutations)
return permutations

def generate_permutations_recursive(elements, current_permutation, permutations):

if len(elements) == 0:
permutations.append(current_permutation)
else:
for i in range(len(elements)):
remaining_elements = elements[:i] + elements[i+1:]
new_permutation = current_permutation + [elements[i]]
generate_permutations_recursive(remaining_elements, new_permutation, permutations)

Juan F. Imbet Ph.D. 24