Solving problems
First: some comments
- CLI example: my dotfiles installer
- Homework: my version (made last night)
I could probably have shaved more off the problem but this is quite short and general
Solving problems
Solving problems
The animation was made using pyorb - one of my
packages
(code is in the handout)
"Solving the problem" took about 10 minutes to make because
- I knew the tools
- I knew Python
- I knew the correct pattern
- I knew which trade-offs were important
Solving problems
- The steps involved in problem solving
- The trade-offs and choices you will need to do
- Some common patterns you might find useful
- Some problem solving practice
Lets this lecture go trough
Solving problems
Two levels for the solution
- The idea/pattern of the solution (language agnostic)
- Implementing the idea/pattern (language dependant)
An example problem: implement vector dot product
-
Multiplication map and sum reduce
[map-reduce pattern]
(Higher memory overhead / allows for parallelisation) -
Common iterator loop and mutable result
variable
[online-algorithm pattern]
(Lower memory overhead / single thread sequential execution) -
Just start writing and discover the correct pattern as I go
Solving problems
Two levels for the solution
An example problem: implement vector dot product
-
Common iterator loop and mutable result
variable
[online-algorithm pattern]
(Lower memory overhead / single thread sequential execution)
def dot(vec1, vec2):
result = 0
for ind in range(len(vec1)):
result = result + vec1[ind] * vec2[ind]
return result
Solving problems
def dot(vec1, vec2):
result = 0
for ind in range(len(vec1)):
result = result + vec1[ind] * vec2[ind]
return result
def dot(vec1, vec2):
result = 0
for x1, x2 in zip(vec1, vec2):
result += x1 * x2
return result
Not dependant on [], shortest iter goes, readable
Solving problems
def dot(vec1, vec2):
result = 0
for x1, x2 in zip(vec1, vec2):
result += x1 * x2
return result
def dot(vec1, vec2):
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
Not dependant on first type, less readable, robust?
Solving problems
def dot(vec1, vec2):
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
Solving problems
def dot(vec1, vec2):
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
Solving problems
def dot(vec1, vec2):
assert len(vec1) == len(vec2), "Input vectors must be same length"
if len(vec1) == 0:
return
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
Solving problems
def dot(vec1, vec2):
assert len(vec1) == len(vec2), "Input vectors must be same length"
if len(vec1) == 0:
return
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
Solving problems
def dot(vec1, vec2):
assert len(vec1) == len(vec2), "Input vectors must be same length"
if len(vec1) == 0:
return
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
This is either a really cool or a really bad feature - depending on what you want
Solving problems
def dot(vec1, vec2):
assert len(vec1) == len(vec2), "Input vectors must be same length"
if len(vec1) == 0:
return
common_iter = zip(vec1, vec2)
x1, x2 = next(common_iter)
result = x1 * x2
for x1, x2 in common_iter:
result += x1 * x2
return result
Balance of abstraction and specification, safety and brevity, efficiency and ease
Lets move to numpy arrays
Solving problems
import numpy as np
def dot(vec1, vec2):
if np.can_cast(vec1.dtype, vec2.dtype, casting="safe"):
result = vec2.dtype.type(0)
elif np.can_cast(vec2.dtype, vec1.dtype, casting="safe"):
result = vec1.dtype.type(0)
else:
raise TypeError("Types cannot be cast safely")
assert vec1.size == vec2.size
for x1, x2 in zip(vec1, vec2):
result += x1 * x2
return result
Now we have MORE code that just checks input than actual working lines
"Meh! No one is gonna input something stupid to this"
Solving problems
import numpy as np
def dot(vec1: np.ndarray, vec2: np.ndarray):
result = vec1.dtype.type(0)
for x1, x2 in zip(vec1, vec2):
result += x1 * x2
return result
Solving problems
from numpy import dot
We could also just know the correct tools for the job
+it is written already / tested (hopefully) / robust (hopefully) / fast (hopefully)
(you can never assume with dependencies)
-added a dependency (and its own tree) / no control over behaviour / no option to optimize
Solving problems
from numpy import dot
- Be aware of the trade-offs and make a concious decision
-
It is also a matter of "time-to-implement" - pick your
battles
E.g. coordinate transforms (used everywhere):
religiously tested and validated and designedE.g. my CLI interface:
Thrown together and when it crashes I fix itE.g. I trust numpy to be fast and scipy to be correct
I don't trust the 1 star, 0 issues, last commit 7 years ago, github repo - How do you learn these things?
Solving problems
- How do you learn these things?
- Write code, write a lot of code
- Read other peoples code
- Have other read your code
- Throw away code, and write it again
- Talk to others about code and writing code
- Get coached on writing code
So that is what we are doing!
Solving problems
First: some common patterns I think are useful to know
- Dependency injection
- Composition over inheritance
- Strategy pattern
- Adapter
- Interface
- Vectorisation
- Online-algorithm
- Map-Reduce
- Visitor
All of these are described in the handout!
Solving problems
Time to code!
If you don't want to log in: use This input file - the result should be 1660292
Let's compare solutions
Solving problems
Further study and homework
Let's check out the handout above!