Performance Counter
When you use time.time()
, you are getting the number of seconds since January 1, 1970, 00:00:00 UTC. This value is (as I'm writing this) around 1565401846.889736 ... so has about microsecond resolution.
When you use time.perf_counter()
, you are getting "a clock with the highest available resolution to measure a short duration". As I was writing this, I retrieved the value 53.149949335 ... so it has approximately nanosecond resolution.
For profiling code, you want the highest resolution timer at your disposal ... so eschew time.time()
in favour of time.perf_counter()
.
Timed Decorator
Since you are doing a lot of performance measurements in your exploration of Project Euler, you should package up the performance measurement code in a neat little package that can be easily reused. You were given a decorator for this in an answer to your "Time & Space of Python Containers" question. But here it is again, slightly modified for just doing timing:
from time import perf_counter
from functools import wraps
def timed(func):
@wraps(func)
def wrapper(*args, **kwargs):
start = perf_counter()
result = func(*args, **kwargs)
end = perf_counter()
print(f"{func.__name__}: {end-start:.6f} seconds")
return result
return wrapper
You can decorate a function with @timed
, and it will report how long that function takes. You can even decorate multiple functions!
And it moves the timing code out of your if __name__ == '__main__':
block.
Use Test Cases
Project Euler 15 gives you the answer to a 2x2 lattice grid. You should run that test case in your code, to give yourself confidence you are getting the correct answer. Eg)
@timed
def count_lattice_paths(rows, cols):
# ...
def pe15(rows, cols):
paths = count_lattice_paths(rows, cols)
print(f"{rows} x {cols} = {paths} paths")
if __name__ == '__main__':
pe15(2, 2)
pe15(20, 20)
A few import points.
- The
if __name__ == '__main__':
block clearly runs two cases
- a 2x2 lattice, and
- a 20x20 lattice.
- The
pe15(rows, cols)
calls count_lattice_paths(rows, cols)
to get the result, and then prints out the result with a description of the case.
- The
count_lattice_paths(rows, cols)
is the @timed
function, so the time spent printing the result report in not counted in the timing.
- The
count_lattice_paths()
method can be generalized to work with an NxM lattice; it doesn't need to be square, even though the problem asked for the result for a square lattice and gives a square lattice test case.
Count Lattice Paths (without a cache)
As you noticed, a 2x2 lattice is better represented by a 3x3 grid of nodes.
- It should be obvious there is only 1 way to reach every node along the top edge.
- It should be obvious there is only 1 way to reach every node along the left edge.
So, our initial array of counts would look like:
1 1 1
1 . .
1 . .
At each node (other than the top edge and left edge), the number of paths is equal to the sum of the paths to the node above it and the paths to the node to the left of it. So, there are 1+1 = 2
paths to the node at 1,1:
1 1 1
1 2 .
1 . .
Since the value at each point is defined entirely by the values above and left of it, we can directly loop over each node, and compute the required values, and finally return the value at the lower right corner of the grid. We don't even need to store the entire grid; we can compute the next row from the current row.
@timed
def count_lattice_paths(rows, cols):
steps = [1] * (cols + 1)
for _ in range(rows):
for i in range(cols):
steps[i+1] += steps[i]
return steps[-1]