Potential Drawbacks of Results
As highlighted by @Mitchel Paulin LeetCode's performance test aren't reliable. I wrote my own answer and got a range of timings from 44ms in >96.53% bracket, but the same code got 56ms in the >46.94% bracket. This means it's also testing the performance of other things whilst testing my code.
This can happen on your machine too. If you're executing a high performance operation whilst trying to time your code your results are going to be useless. But this doesn't mean that you have to have a 'performance testing machine' with nothing running on it to get fairly accurate results. Currently with two web browsers with ~950 tabs open, an IDE, two different notepad software, Spotify and an email client on Windows. I normally get accurate results.
There are times when you see abnormal results in the graphs. I've noticed that sometimes when Spotify changes song you can see additional error bars. But these can just be ignored. The occasional time the entire graph is just useless; but these are rare, easily identifiable and just requires running the timers again.
How to time performance
The simplest way is to just use timeit, however it's hard to see trends with this. Instead I created and use graphtimer to create graphs. The benefit to graphs is they're visual and easier to understand then a bunch of numbers.
Normally programming challenges give you a couple of integers to test against. So setting up timers for, say, a prime sieve is easier than what we have here. And so before we start checking the performance of your code we need to create a function that converts a single number to the arguments we want. I'll provide the function I used to do this. As for this it's fairly complex. I set the entire size of the dungeon to the passed size, and then randomly created the dungeon from this.
After this when testing you need to test each change one at a time. This is because you may make two changes where one of the changes improves performance, but the other reduces performance. This can lead to you not getting maximum performance as you've thrown away an idea that improves performance.
I don't like the way you're building range. And so have some ideas to change it:
- Change to use
reversed(range(row -1)).
- Near the beginning of the function create a variable that holds the rages.
- Same as (2) but cast the
range to a list.
This shows:
- Precomputing the range and not casting is the fastest.
- Using
reverse is slower than your code.
- Precomputing the range and casting is slower for less than three items, but then becomes faster.
Code Review
- Change mutations to be in-place. Don't make
dp.
- Remove the guard statement.
- In my solution I used
min rather than max causing my final line to be slower. So don't swap these.
- Change formatting of your
min, and your list indexing so it's easier to read them.
All this gets:
def solution_justin_no_guard(dungeon):
dungeon[-1][-1] = max(1, 1 - dungeon[-1][-1])
row, col = len(dungeon), len(dungeon[0])
rows = range(row - 2, -1, -1)
cols = range(col - 2, -1, -1)
for i in rows:
dungeon[i][-1] = max(1, dungeon[i + 1][-1] - dungeon[i][-1])
for j in cols:
dungeon[-1][j] = max(1, dungeon[-1][j + 1] - dungeon[-1][j])
for i in rows:
for j in cols:
dungeon[i][j] = min(
max(1, dungeon[i][j + 1] - dungeon[i][j]),
max(1, dungeon[i + 1][j] - dungeon[i][j])
)
return dungeon[0][0]
Graphs
You need to install numpy, matplotlib and graphtimer from pypi to be able to run the following. Produces the above three graphs.
import random
import copy
import numpy as np
import matplotlib.pyplot as plt
from graphtimer import Plotter, MultiTimer
def solution_justin(dungeon):
if not dungeon or not dungeon[0]:
return 0
row, col = len(dungeon), len(dungeon[0])
dp = [[0] * col for _ in range(row)]
dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
for i in range(row - 2, -1, -1):
dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])
for j in range(col - 2, -1, -1):
dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])
for i in range(row - 2, -1, -1):
for j in range(col - 2, -1, -1):
dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))
return dp[0][0]
def solution_justin_reverse(dungeon):
if not dungeon or not dungeon[0]:
return 0
row, col = len(dungeon), len(dungeon[0])
dp = [[0] * col for _ in range(row)]
dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
for i in reversed(range(row - 1)):
dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])
for j in reversed(range(col - 1)):
dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])
for i in reversed(range(row - 1)):
for j in reversed(range(col - 1)):
dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))
return dp[0][0]
def solution_justin_pre_computed(dungeon):
if not dungeon or not dungeon[0]:
return 0
row, col = len(dungeon), len(dungeon[0])
dp = [[0] * col for _ in range(row)]
dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
rows = range(row - 2, -1, -1)
cols = range(col - 2, -1, -1)
for i in rows:
dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])
for j in cols:
dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])
for i in rows:
for j in cols:
dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))
return dp[0][0]
def solution_justin_pre_computed_list(dungeon):
if not dungeon or not dungeon[0]:
return 0
row, col = len(dungeon), len(dungeon[0])
dp = [[0] * col for _ in range(row)]
dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
rows = list(range(row - 2, -1, -1))
cols = list(range(col - 2, -1, -1))
for i in rows:
dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])
for j in cols:
dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])
for i in rows:
for j in cols:
dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))
return dp[0][0]
def solution_justin_inplace(dungeon):
if not dungeon or not dungeon[0]:
return 0
row, col = len(dungeon), len(dungeon[0])
dungeon[-1][-1] = max(1, 1 - dungeon[-1][-1])
rows = range(row - 2, -1, -1)
cols = range(col - 2, -1, -1)
for i in rows:
dungeon[i][-1] = max(1, dungeon[i + 1][-1] - dungeon[i][-1])
for j in cols:
dungeon[-1][j] = max(1, dungeon[-1][j + 1] - dungeon[-1][j])
for i in rows:
for j in cols:
dungeon[i][j] = min(
max(1, dungeon[i][j + 1] - dungeon[i][j]),
max(1, dungeon[i + 1][j] - dungeon[i][j])
)
return dungeon[0][0]
def solution_justin_no_guard(dungeon):
dungeon[-1][-1] = max(1, 1 - dungeon[-1][-1])
row, col = len(dungeon), len(dungeon[0])
rows = range(row - 2, -1, -1)
cols = range(col - 2, -1, -1)
for i in rows:
dungeon[i][-1] = max(1, dungeon[i + 1][-1] - dungeon[i][-1])
for j in cols:
dungeon[-1][j] = max(1, dungeon[-1][j + 1] - dungeon[-1][j])
for i in rows:
for j in cols:
dungeon[i][j] = min(
max(1, dungeon[i][j + 1] - dungeon[i][j]),
max(1, dungeon[i + 1][j] - dungeon[i][j])
)
return dungeon[0][0]
def solution_peilonrayz(dungeon):
dungeon[-1][-1] = min(dungeon[-1][-1], 0)
row = len(dungeon)
col = len(dungeon[0])
rows = range(row - 2, -1, -1)
cols = range(col - 2, -1, -1)
for i in rows:
dungeon[i][-1] = min(dungeon[i][-1] + dungeon[i + 1][-1], 0)
for i in cols:
dungeon[-1][i] = min(dungeon[-1][i] + dungeon[-1][i + 1], 0)
for y in rows:
for x in cols:
dungeon[y][x] = max(
min(dungeon[y][x] + dungeon[y + 1][x], 0),
min(dungeon[y][x] + dungeon[y][x + 1], 0)
)
return abs(min(dungeon[0][0], 0)) + 1
memoize = {}
def create_arg(size, *, _i):
size = int(size)
key = size, _i
if key in memoize:
return copy.deepcopy(memoize[key])
divisors = [
(i, size // i)
for i in range(1, int(size ** 0.5) + 1)
if size % i == 0
]
if len(divisors) > 1:
divisors = divisors[1:]
y_size, x_size = random.choice(divisors)
output = [[None] * x_size for _ in range(y_size)]
for i in range(size):
y, x = divmod(i, x_size)
output[y][x] = random.randint(-100, 100)
memoize[key] = output
return output
def main():
fig, axs = plt.subplots()
axs.set_yscale('log')
axs.set_xscale('log')
(
Plotter(MultiTimer([
solution_justin,
solution_justin_reverse,
solution_justin_pre_computed,
solution_justin_pre_computed_list,
]))
.repeat(10, 1, np.logspace(0, 2), args_conv=create_arg)
.min()
.plot(axs, title='Comparison of Loop Changes', x_label='dungeon size')
)
fig.show()
fig, axs = plt.subplots()
axs.set_yscale('log')
axs.set_xscale('log')
(
Plotter(MultiTimer([
solution_justin_pre_computed,
solution_justin_inplace,
solution_justin_no_guard,
solution_peilonrayz,
]))
.repeat(10, 1, np.logspace(0, 2), args_conv=create_arg)
.min()
.plot(axs, title='Code Review Changes', x_label='dungeon size')
)
fig.show()
fig, axs = plt.subplots()
axs.set_yscale('log')
axs.set_xscale('log')
(
Plotter(MultiTimer([
solution_justin,
solution_justin_no_guard,
]))
.repeat(10, 1, np.logspace(0, 2), args_conv=create_arg)
.min()
.plot(axs, title='Comparison of Original and Final', x_label='dungeon size')
)
fig.show()
if __name__ == '__main__':
main()
Final notes
The graph is a zig-zaged line. This is because the program is faster when there's only one row or column. And it currently only allows this case when the number is prime. It looks like if a list has at least two dimensions then the performance decreases dramatically to the upper line, but doesn't change much between a 20x2 and a 5x8. I can't prove this, as the graph is only 2D not 3D, but the lack of error bars suggest it. If create_arg is changed to always create a 1xn list once then you get the following graph.
timeitfunction? \$\endgroup\$