如何提高"Is this a straight line?"算法的性能？

Question

我最近开始使用LeetCode来提高我的算法性能，大多数时候我的算法是<运行时和内存使用率比其他用户高80%。

我能做些什么来改进下面的代码，它在运行时和内存使用率方面都只提高了5%？是什么让你找到了一个有效的解决方案？LeetCode问题：https://leetcode.com/problems/check-if-it-is-a-straight-line/

def checkStraightLine(self, coordinates):
"""
:type coordinates: List[List[int]] exm1: [[1,2],[2,3],[3,4],[4,5] exm2: [[0,0],[0,5],[5,5],[5,0]]
:rtype: bool
"""
import numpy as np
slope = []
for i in range(len(coordinates)-1):
x = coordinates[i+1][0]
X = coordinates[i][0]
y = coordinates[i+1][1] 
Y = coordinates[i][1] 
if x - X !=0:
slope.append((y - Y) / (x - X))  #for non-zero devision cases cal. the slope
else:
slope.append(x) # for zero devision cases check if parlell to y axis
print(slope)

return len(np.unique(slope)) == 1 #whether slope is 0 or >0 it should be constant when comparing all given points

Answer 1

一些注意事项：

当第一个斜率不同时，

• 不需要继续循环
• 不是计算唯一值所必需的numpy：

import functools
from itertools import tee
def check_slope(coords):
slope = None

def pairwise(iterable):
a, b = tee(iterable)
next(b, None)
return zip(a, b)
for [x,y],[X,Y] in pairwise(coords):
if x != X:
v = (y - Y) / (x - X)
else:
v = x

if slope is None:
slope=v
else:
if v!=slope:
return False

return True

case1 = [[1,2],[2,3],[3,4],[4,5]]
case2 = [[0,0],[0,5],[5,5],[5,0]]
%timeit a = checkStraightLine(case1)
#6.78 µs ± 119 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit b = checkStraightLine(case2)
# 6.67 µs ± 47.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit c = check_slope(case1)
# 845 ns ± 50.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit d = check_slope(case2)
# 774 ns ± 12.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
assert a==c
assert b==d