18: 效率

编程任务往往有多种解决方案,然而一种方案可能运行速度比另一种快。编写运行速度快的程序不仅需要编程者拥有艺术眼光,还要拥有坚实的编程基础。在下列习题中会有一些示例。

第1部分:避免进行重复计算

斐波那契数列是一个既简单又吸引人的数列。前两项是1,1,接下来每一个数字是前两个数字的和。比如,下一个数字是1+1=2。这样前三项就确定了,

1, 1, 2

第四项是1+2=3,然后是2+3=5,以此类推:

1, 1, 2, 3, 5, 8, 13, ...

斐波那契数列原本是用来解决兔子数量的问题,但是还和植物建筑相关。下面是一个有关斐波那契数列视频:

斐波那契数列的定义会令人很自然地想到递推方程。下一个练习题定义了一个方程Fibonacci(n),返还上述序列中第n项(从n=1开始)。

综合练习: Nibofacci
整理这个程序,返还一个斐波那契数列递推定义。判分系统会打印出它们的前十项。
  • def Fibonacci(n):
  • return Fibonacci(n-1) + Fibonacci(n-2)
  • else:
  • return 1
  • if (n==1 or n==2):
在下方输入测试语句,例如 print(myfunction("test argument"))

然而,这个递推方程运行起来很慢。点击输入测试语句,输入print(Fibonacci(80))。测试它时会得到"超出时限"提示。

为什么运行地这么慢?因为这个方程没有复杂的指示或循环,只有加法,总共调用方程的次数太多。如果我们调用Fibonacci(3),递推方程总共会被调用三次:最开始的调用,然后是两个递推调用。如果我们调用Fibonacci(4),递推方程被调用了五次:最开始的调用,刚刚讲过的三次n=3,还有一个递推调用n=2Fibonacci(5)总共会有九次调用,Fibonacci(6)会有9+5+1=15次调用。调用的次数会随着n增长而迅速增长!

粗略估计,Fibonacci(n+2)的调用次数至少是Fibonacci(n)调用次数的两倍。因为Fibonacci(n+2)直接调用一次Fibonacci(n),还有通过递推非直接调用Fibonacci(n+1)。所以计算时间与指数函数成正比,至少有(√2)n这么大。比如,Fibonacci(80)需要多于240 = 1099511627776次递推调用。

这个论据还略述了概念性的问题:调用Fibonacci(n)两次,从零开始重新计算结果太浪费时间了。如何用相同的方法,但是不重复计算?

答案

让我们试试类似于介绍中所写的东西。我们从1, 1开始。此后,我们把最后两项相加来扩充序列。下面是这个想法的代码形式,在这个基础上是否进行整理取决于你。

综合练习: Fast Fibonacci
计算斐波那契值的最快版本。
  • sequence = [0, 1, 1] # Fibonacci(0) is 0, Fibonacci(1) and Fibonacci(2) are 1
  • sequence.append(sequence[i-1] + sequence[i-2])
  • return sequence[n]
  • def Fibonacci(n):
  • for i in range(3, n+1):
在下方输入测试语句,例如 print(myfunction("test argument"))

因为不需要每次调用的时候重新计算整个数组,所以在这个基础上还有提升的空间。但是这个版本就能够满足我们的要求,n值很大的时候运行也很快!

第2部分:避免计算不重要的事情,一次也不要

第二个例子是关于检查数字是否是质数,这在加密和计算机安全方面非常重要。如果一个数只有两个因子:1和它本身,那么这个数字是质数。从1开始的几个质数是2,3,5,7,11,13,17,19,23(21不是质数因为除了是1和21外,21还有因子3和7)。

Python中如何测试一个数字是否是质数?我们之前讲过如何测试整除性:

N % D == 0  # will be True if D is a divisor of N, False otherwise

下列程序测试所有可能的因子。

示例
测试数字是否是质数
在下方输入测试语句,例如 print(myfunction("test argument"))

这个程序可以满足我们的要求!但是如果数字很大,这个程序也会很慢。选输入,输入isItPrime(324635459)。你会得到超出时间限制的提示。尝试更多的值……对于大于10000000的质数,这个代码总是超出时间限制,打分器只能以每秒一千万次的速度进行整除性检查循环。如果想检查比较大的数字,我们需要其他更有效率的想法。让我们把代码变得更有效,可以处理十亿以上的数字!

是否有必要检查所有的数字,2N-1之间,以查看N是否是质数?提示

主意和参数

如果你阅读了提示或者进行了多次尝试,你可能会注意到当N不是质数,这个程序通常能找到一个与N相比相当小的因数。比如,isItPrime(34827948723948723984729834)运行地非常快:尽管数字很大,但找到的因子却是D=2

或许我们不需要检查所有的因子。但是是否有一些因子我们一定要检查,然后才可以确定N是质数?没错!实际上,我们可以认为如果N不是质数,它的质数最大不超过sqrt(N)。为什么?因为如果N不是质数,那么它就有一个因子A。作为一个因子就意味着还有另一个数字B,使得

A*B == N

让我们继续论证。如果A <= sqrt(N)B <= sqrt(N),那么皆大欢喜:我们找到了N的一个比较小的因子。实际上这里只有这些可能:否则,我们就会得到矛盾

N = A*B > sqrt(N)*sqrt(N) > N

那么现在,让我们在Python中施行这个新的主意。改变旧方法的最简单的方法是在for循环中加入一个测试:一旦D > sqrt(N)(或者D*D > N),可以(break)跳出循环,停止测试。

示例
运行速度更快的质数测试

这个程序可以处理很大的质数!

最后的练习题

在这个练习中,我们将这节课后半部分的质数与序列为核心的前半部分结合。你的代码应该能够填写一个长为1000001表格,使得如果N是质数isPrime[N]等于True;如果N是合数,就是False。在这里N小于等于一百万(比如,isPrime[0]isPrime[1]应为False)。

点击这里查看提示。很重要!

编程练习: Primed for Takeoff
编写我们上述描述的程序isPrime(注意isPrime是一个序列,不是方程)。提示
判断器时间限制是7秒,以确保你的程序运行成功。然而,单独使用isItPrime方程还不够快。

这是CS Circles网站最后的练习题。恭喜完成所有课程的同学!查看resources page,里面有些建议告诉你接下来可以学什么。希望你可以从中找到乐趣,编写出好程序!祝你好运!