实现最佳性能的一个简单方法是构建一个包含所有可能的[a,b]对结果的大表。 但是,这可能会消耗大量的存储器,对较大的n来说是不现实的
以下是用常见方法优化代码的方法。 在
1。 在逻辑表达式中使用显式and
正如评论中提出的那样,由于and的short circuiting动作,这更具可读性和效率。 在我的测试中,仅这个更改就会减少60%的运行时间。 在
2。 消除冗馀的条件
因为a和b的范围是从1到{},所以如果a==n**2,则{}永远无法实现。 因此,条件a%n==0 and a!=n**2 and b==a 1的a!=n**2检查是多余的。 第三种情况也是如此。 通过排除这些条件,以下内容将变得简单。
elif a % n==0 and b==a 1:
elif(a-1 ) % n==0 and b==a - 1:
.
3。 避免在条件下重复计算
另外,上述条件得到改善
a % n==0 and b==a 1和{}是ABS(a-b )==1的特例。 {cd16因此可以在这些条件下改写。 在
^{pr2}$
另请注意,值ABS(a-b )与所有条件相关。 因此,可以在检查所有条件之前进行计算。 随着这一变化,代码将变为d=ABS(a-b )
if d==0: return 6
elif d==1:
if a % n==0 and b a: return 0
elif b % n==0 and a b: return 0
else return 1
elif d==n - 1:
if a % n==0 and a b: return 1
elif b % n==0 and b a: return 1
else return 0
elif d==n :返回1
else :返回0
4。 简化逻辑
例如,上面第一个嵌套的if-else可以简化为ifmin(a,b ) % n==0: return 0
else return 1
更精简的语法是return1ifmin(a,b ) % n==0 else 0
五。 应用特定于Python的优化
Python认为数字0具有错误的值。 所以对于数量,if d!=0:和{}分别等效于if d:和{}。 后者有点快。 应用此更改将生成以下优化代码: 这里使用更紧凑的语法来缩短回答。 在d=ABS(B-a )
if not d: return 6
elifd==1:return1ifmin(a,b ) % n else 0
elifd==n-1:return0ifmax(a,b ) % n else 1
else: return 1 if d==n else 0
应用上述步骤2至5,正常运行时间将进一步缩短50%。
6。 根据输入分布调整条件顺序
这种变化取决于对APP应用程序中实际输入分布的理解。 目标是更快地恢复更常见的输入。 本示例假设输入a和{}均匀分布在[1,n**2]和{}中。 在这种情况下,最常见的情况是值d与任何if条件都不匹配,0将在检查所有条件后返回。 要加速,首先检查D是否可能为非零返回值,以便更快地失败。 在d=ABS(a-b )
if1dn-1 ordn : return0# return0ifdisnotin [ 0,1,n-1,n]
elifd==1:return1ifmin(a,b ) % n else 0
elifd==n-1:return0ifmax(a,b ) % n else 1
else 3360 return1ifd==n else6# d==0caseismovedtothelast ' else ' sinceitisleastfrequentlyseen
7。 使用查找表
进一步的加速可以通过使用查找表来实现。 在此,可以存储第一个条件检查的值[ 0,1,n - 1,n]以加快检查。 在这种情况下,有两个主要选项。 一个组或一个长度-n 1布尔值列表。 前者占用的内存较少,后者性能较好。 请注意,应该在函数外部构建一次查找表,然后将其传递给它。 使用布尔列表进行搜索的代码是deffunc(n,a,b,lookup ) :
是d=ABS(a-b )
ifnot(d=nandlookup[d] ) : return 0
.
应用步骤6和7 (通过布尔列表搜索)后,执行时间将进一步缩短15%。
在该示例中,还可以使用[min(a,b ) % n,d ]作为索引来使用实现为嵌套列表或词典的2D查找表。 但是,在步骤6中相同输入分布假设下,这比1D查找慢一些。 这是因为额外级别的索引开销。 在
上面的运行时是将函数应用于[1,n**2]中所有可能的[a,b]值的总时间。 在