<!DOCTYPE html>
Asymptotic Analysis¶
In the past, we've run into questions about efficiency when choosing what data structures to use (preferring sets or dictionaries instead of lists), as well as in designing our software to precompute and save results in the initializer rather than compute them just-in-time. By the end of this lesson, students will be able to:
- Cache or memoize a function by defining a dictionary or using the
@cachedecorator. - Analyze the runtime efficiency of a function involving loops.
- Describe the runtime efficiency of a function using asymptotic notation.
There are many different ways software efficiency can be quantified and studied.
- Running Time, or how long it takes a function to run (e.g. microseconds).
- Space or Memory, or how much memory is consumed while running a function (e.g. megabytes of memory).
- Programmer Time, or how long it took to implement a function correctly (e.g. hours or days).
- Energy Consumption, or how much electricity or natural resources a function takes to run (e.g. kilo-watts from a certain energy source).
!pip install -q nb_mypy
%reload_ext nb_mypy
%nb_mypy mypy-options --strict
Version 1.0.5
Data classes¶
Earlier, we wrote a University class that needed to loop over all the students enrolled in the university in order to compute the list of students enrolled in a particular class. Let's take this opportunity to review this by also introducing one neat feature of Python that allows you to define simple data types called data classes. We can define a Student data class that takes a str name and dict[str, int] for courses and the credits for each course with the @dataclass decorator. Decorators will turn out to be a useful feature for the remainder of this lesson, and it's helpful to see them in a more familiar context first.
from dataclasses import dataclass, field
@dataclass
class Student:
"""Represents a student with a given name and dictionary mapping course names to credits."""
# Only in a dataclass are these class attributes turned into instance fields!
name: str
courses: dict[str, int] = field(default_factory=dict) # specifies that the default value for courses is an empty dictionary
def get_courses(self) -> list[str]:
"""Return a list of all the enrolled courses."""
from time import sleep
sleep(0.0001) # The time it takes to retrieve a single student's course list from MyUW
return list(self.courses)
The @dataclass decorator "wraps" the Student class in this example by providing many useful dunder methods like __init__, __repr__, and __eq__ (used to compare whether two instances are == to each other), among many others. This allows you to write code that actually describes your class, rather than the "boilerplate" or template code that we always need to write when defining a class.
Default values for each field can be set with = assignment operator, and dataclasses also have a built-in way of handling mutable default parameters like fields that are assigned to lists or dictionaries using the field function as shown above.
Student("Nicole")
Student(name='Nicole', courses={})Let's see how we can use this Student data class to implement our University class again.
class University:
"""
Represents one or more students enrolled in courses at a university.
"""
def __init__(self, name: str, students: list[Student] | None = None) -> None:
"""Takes the name of the university and optionally a list of students enrolled."""
self._name: str = name
if students is None:
students = []
self._students: list[Student] = students
self._courses: dict[str, list[Student]] = {}
for student in self._students:
for course in student.get_courses():
if course not in self._courses:
self._courses[course] = []
self._courses[course].append(student)
def enrollments(self) -> list[Student]:
"""Returns all the enrolled students sorted by their name in alphabetical order."""
return sorted(self._students, key=lambda student: student.name)
def enroll(self, student: Student) -> None:
"""Enrolls the student to the university."""
self._students.append(student)
for course in student.get_courses():
if course not in self._courses:
self._courses[course] = []
self._courses[course].append(student)
def roster(self, course: str) -> list[Student] | None:
"""
Returns the list of students enrolled in the given course. If there are no students
enrolled, return an empty list. If the course does not exist, return None.
"""
if course not in self._courses:
return None
return self._courses[course]
def roster_uncached(self, course: str) -> list[Student] | None:
"""
Returns the list of students enrolled in the given course. If there are no students
enrolled, return an empty list. If the course does not exist, return None.
"""
result = {}
for student in self._students:
for course in student.get_courses():
if course not in result:
result[course] = []
result[course].append(student)
return result
uw = University("Udub", [Student("Student"), Student("Nicole")])
uw.enrollments()
<cell>45: error: Need type annotation for "result" (hint: "result: dict[<type>, <type>] = ...") [var-annotated] <cell>51: error: Incompatible return value type (got "dict[Any, Any]", expected "list[Student] | None") [return-value]
[Student(name='Nicole', courses={}), Student(name='Student', courses={})]Caching¶
The approach of precomputing and saving results in the constructor is one way to make a function more efficient than simply computing the result each time we call the function. But these aren't the only two ways to approach this problem. In fact, there's another approach that we could have taken that sits in between these two approaches. We can cache or memoize the result by computing it once and then saving the result so that we don't have to compute it again when asked for the same result in the future.
Let's go back to the University class to add a cached version of the roster method and name it roster_cached.
%time uw.roster("CSE163")
%time uw.roster_uncached("CSE163")
Okay, so this doesn't seem that much faster since we're only working with 2 students. There were 60,692 enrolled students at UW in 2023. Let's try generating that many students for our courses.
names = ["Thrisha", "Sheamin", "Nicole"]
students = [Student(names[i % len(names)], {"CSE163": 4}) for i in range(60692)]
students[:10]
[Student(name='Thrisha', courses={'CSE163': 4}),
Student(name='Sheamin', courses={'CSE163': 4}),
Student(name='Nicole', courses={'CSE163': 4}),
Student(name='Thrisha', courses={'CSE163': 4}),
Student(name='Sheamin', courses={'CSE163': 4}),
Student(name='Nicole', courses={'CSE163': 4}),
Student(name='Thrisha', courses={'CSE163': 4}),
Student(name='Sheamin', courses={'CSE163': 4}),
Student(name='Nicole', courses={'CSE163': 4}),
Student(name='Thrisha', courses={'CSE163': 4})]uw = University("Udub", students)
Python provides a way to implement this caching feature using the @cache decorator. Like the @dataclass decorator, the @cache decorator helps us focus on expressing just the program logic that we want to communicate.
from functools import cache
class University:
...
# If you cache the University's roster method,
# what might happen? So the issue with caching
# information, is you have to be very careful about
# changes to information in objects.
# So probably not a good idea for this University to cache
# the roster!
@cache
def roster_uncached(...):
...
@dataclass
class Student:
...
# So we could also try to cache the results here on the Student object
# But we would still want to have some way of reporting changes to the
# cache
@cache
def get_courses(self) -> list[str]:
"""Return a list of all the enrolled courses."""
from time import sleep
sleep(0.0001) # The time it takes to retrieve a single student's course list from MyUW
return list(self.courses)
# Q: Where is the cache stored?
# A: The cache is a dictionary created for every decorated @cache function.
# It's not in this code at all: the dictionary is in the @cache code.
# Q: Why caching?
# A: It is definitely to make things faster, particularly when you need the
# the same computation (function call result) in the future.
Counting steps¶
A "simple" line of code takes one step to run. Some common simple lines of code are:
printstatements- Simple arithmetic (e.g.
1 + 2 * 3) - Variable assignment or access (e.g.
x = 4,1 + x) - List or dictionary accesses (e.g.
l[0],l[1] = 4,'key' in d).
The number of steps for a sequence of lines is the sum of the steps for each line.
x = 1
print(x)
1
The number of steps to execute a loop will be the number of times that loop runs multiplied by the number of steps inside its body.
The number of steps in a function is just the sum of all the steps of the code in its body. The number of steps for a function is the number of steps made whenever that function is called (e.g if a function has 100 steps in it and is called twice, that is 200 steps total).
This notion of a "step" intentionally vague. We will see later that it's not important that you get the exact number of steps correct as long as you get an approximation of their relative scale (more on this later). Below we show some example code blocks and annotate their number of steps in the first comment of the code block.
# Total: 4, 5, 6, or 7 steps depending on how you count!
print(1 + 2) # 1 step
print("hello") # 1 step
x = 14 - 2 # 1 step
y = x ** 2 # 1 step
3 hello
# Total: 51 steps
print("Starting loop") # 1 step
# Loop body has a total of 1 step. It runs 30 times for a total of 30
for i in range(30): # Runs 30 times
print(i) # - 1 step
# Loop body has a total of 2 steps. It runs 10 times for a total of 20
for i in range(10): # Runs 10 times
x = i # - 1 step
y = i**2 # - 1 step
Starting loop 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
# Total: 521 steps
print("Starting loop") # 1 step
# Loop body has a total of 26 steps. It runs 20 times for a total of 520
for i in range(20): # Runs 20 times
print(i) # - 1 step
# Loop body has a total of 1 step.
# It runs 25 times for total of 25.
for j in range(25): # - Runs 25 times
result = i * j # - 1 step
Starting loop 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Big-O notation¶
Now that we feel a little bit more confortable counting steps, lets consider two functions sum1 and sum2 to compute the sum of numbers from 1 to some input n.
def sum1(n: int) -> int:
total = 0
for i in range(n + 1):
total += i
return total
def sum2(n: int) -> int:
return n * (n + 1) // 2
The second one uses a clever formula discovered by Gauss that computes the sum of numbers from 1 to n using a formula.
To answer the question of how many steps it takes to run these functions, we now need to talk about the number of steps in terms of the input n (since the number of steps might depend on n).
# Linear time: because it scales directly with the size of the input, n
def sum1(n: int) -> int: # Total: 1 + k * (n + 1) + 1
total = 0 # 1 step
for i in range(n + 1): # n + 1 loops:
total += i # - 1 step (or 2 or 3 steps depending on how you count)
return total # 1 step
# Constant time: no matter how big your input (n) becomes, still takes the same
# relatively small amount of time
def sum2(n: int) -> int: # Total: 3
return n * (n + 1) // 2 # 3 steps (or more depending on how you count)
# Orders of growth runtime analysis
# Computer scientists and data scientists focus on orders of growth
# because really nowadays the hard problems are with big data
Since everything we've done with counting steps is a super loose approximation, we don't really want to promise that the relationship for the runtime is something exactly like n + 3. Instead, we want to report that there is some dependence on n for the runtime so that we get the idea of how the function scales, without spending too much time quibbling over whether it's truly n + 3 or n + 2.
Instead, computer scientists generally drop any constants or low-order terms from the expression n + 3 and just report that it "grows like n." The notation we use is called Big-O notation. Instead of reporting n + 3 as the growth of steps, we instead report O(n). This means that the growth is proportional to n but we aren't saying the exact number of steps. We instead only report the terms that have the biggest impact on a function's runtime.
Poll question: count the number of steps run in the loop for the given method.
pollev.com/kevinl
def method(n: int) -> int:
result = 0
for i in range(9):
for j in range(n):
result += j
return result
# Try plugging in n = 10, method(10)
# How many loops? 9 * 10, 9n answer
# "9n is in O(n)"
# "The [order of growth of the] runtime of method is in O(n)"
# "The runtime of method is linear"
method(10)
# Q: How would you get 9 + n as an answer?
# A:
def method(n: int) -> int:
result = 0
for i in range(9):
print(i)
for j in range(n):
result += j
return result
Big-O notation is helpful because it lets us communicate how the runtime of a function scales with respect to its input size. By scale, we mean quantifying approximately how much longer a function will run if you were to increase its input size. For example, if I told you a function had a runtime in O(n2), you would know that if I were to double the input size n, the function would take about 4 times as long to run.
In addition to O(n) and O(n2), there are many other orders of growth in the Big-O Cheat Sheet.
Data structures¶
Most operations in a set or a dictionary, such as adding values, removing values, containment check, are actually constant time or O(1) operations. No matter how much data is stored in a set or dictionary, we can always answer questions like, "Is this value a key in this dictionary?" in constant time.
In the data-structures.ipynb notebook, we wanted to count the number of unique words in the file, moby-dick.txt. Here are two different implementations that are nearly identical, except one uses a list and the other uses a set.
def count_unique_list(file_name: str) -> int:
words = list()
with open(file_name) as file:
for line in file.readlines():
for word in line.split():
if word not in words: # O(n)
words.append(word) # O(1)
return len(words)
def count_unique_set(file_name: str) -> int:
words = set()
with open(file_name) as file:
for line in file.readlines():
for word in line.split():
if word not in words: # O(1)
words.add(word) # O(1)
return len(words)
The not in operator in the list version was responsible for the difference in runtime because it's an O(n) operation. Whereas, for set, the not in operator is an O(1) operation!
The analysis ends up being a little bit more complex since the size of the list is changing throughout the function (as you add unique words), but with a little work you can show that the list version of this function takes O(n2) time where n is the number of words in the file while the set version only takes O(n) time.