2.8 效率

如何表示和处理数据的决定常常受到备选方案的效率的影响。效率指的是表示或进程所使用的计算资源，例如计算函数或表示对象的结果所需的时间和内存。根据实现的细节，这些金额可能会有很大的差异。

2.8.1 测量效率

准确测量一个程序需要运行多长时间或它消耗多少内存是一项挑战，因为结果取决于计算机如何配置的许多细节。描述程序效率的一种更可靠的方法是测量某些事件发生的次数，比如函数调用。

让我们回到第一个树递归函数，用来计算斐波那契数列中的数字的fib函数。

>>> def fib(n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        return fib(n-2) + fib(n-1)

>>> fib(5)
5

考虑从计算fib(6)中得到的计算模式，如下所示。为了计算fib(5)，我们计算fib(3)和fib(4)。为了计算fib(3)，我们计算fib(1)和fib(2)。总的来说，进化过程看起来像一棵树。每个蓝点表示在遍历这棵树时完成了斐波那契数列的计算。

这个函数作为一个典型的树递归具有指导意义，但它是一种非常低效的计算斐波那契数的方法，因为它需要进行大量的冗余计算。

fib(3)的整个计算过程是重复的。 我们可以衡量这种低效率。高阶count函数返回一个等价的函数给它的参数，该参数也维护一个call_count属性。通过这种方式，我们可以检查fib被调用了多少次。

>>> def count(f):
        def counted(*args):
            counted.call_count += 1
            return f(*args)
        counted.call_count = 0
        return counted

通过计算对fib的调用次数，我们可以看到所需的调用比斐波那契数本身增长得更快。这种调用的快速扩展是树递归函数的特征。

>>> fib = count(fib)
>>> fib(19)
4181
>>> fib.call_count
13529

空间。为了理解函数的空间需求，我们必须指定在我们的计算环境模型中如何使用、保存和回收内存。在计算表达式时，解释器保留所有活动的环境以及这些环境引用的所有值和框架。 如果环境为正在求值的某个表达式提供求值上下文，那么它就是活动的。 当创建环境的第一个框架的函数调用最终返回时，环境就变成不活动的。

例如，当计算fib时，解释器按照前面显示的顺序继续计算每个值，遍历树的结构。 要做到这一点，它只需要在计算的任何一点跟踪树中当前节点之上的那些节点。 用于计算其余分支的内存可以被回收，因为它不会影响未来的计算。 一般来说，树递归函数所需的空间与树的最大深度成正比。

下图描述了通过计算fib(3)创建的环境。 在对fib初始应用的返回表达式求值的过程中，对表达式fib(n-2)求值，结果为0。一旦计算了这个值，就不再需要相应的环境框架(灰色显示)：它不是活动环境的一部分。因此，一个设计良好的解释器可以回收用来存储框架的内存。另一方面，如果解释器当前正在计算fib(n-1)，那么由fib(其中n为2)的应用程序创建的环境是活动的。反过来，最初创建用于将fib应用到3的环境是活动的，因为它的返回值还没有计算出来。

高阶count_frames函数跟踪open_count，即尚未返回的函数f的调用数。max_count属性是open_count所获得的最大值，它对应于计算过程中同时活动的最大框架数。

>>> def count_frames(f):
        def counted(*args):
            counted.open_count += 1
            counted.max_count = max(counted.max_count, counted.open_count)
            result = f(*args)
            counted.open_count -= 1
            return result
        counted.open_count = 0
        counted.max_count = 0
        return counted

>>> fib = count_frames(fib)
>>> fib(19)
4181
>>> fib.open_count
0
>>> fib.max_count
19
>>> fib(24)
46368
>>> fib.max_count
24

综上所述，在活动框架中测量的fib函数的空间要求比输入的空间要求小1，而输入的空间要求往往很小。用总递归调用来衡量的时间需求比输出要大，输出往往很大。

2.8.2 记忆化

树递归计算过程通常可以通过记忆化来提高效率，记忆化是一种强大的技术，可以提高重复计算的递归函数的效率。 记忆化函数将存储它之前收到的任何参数的返回值。 第二次调用fib(25)不会递归地重新计算返回值，而是返回已经构造好的现有值。

Memoization可以自然地表示为高阶函数，也可以用作装饰器。 下面的定义创建了一个先前计算结果的缓存，该缓存由计算结果的参数索引。 字典的使用要求已记忆函数的实参是不可变的。

>>> def memo(f):
        cache = {}
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memoized

如果我们把memo应用到斐波那契数的递归计算中，就会出现一种新的计算模式，如下图所示。

在对fib(5)的计算中，fib(2)和fib(3)的结果在树的右分支计算fib(4)时重复使用。因此，大部分的树递归计算根本就不需要。 使用count，我们可以看到fib函数实际上对fib的每个惟一输入只调用一次。

>>> counted_fib = count(fib)
>>> fib  = memo(counted_fib)
>>> fib(19)
4181
>>> counted_fib.call_count
20
>>> fib(34)
5702887
>>> counted_fib.call_count
35

2.8.3 增长顺序

正如前面的例子所说明的，进程在消耗空间和时间计算资源的速度上可能存在巨大差异。 然而，精确地确定调用函数时将使用多少空间或时间是一项非常困难的任务，这取决于许多因素。 分析流程的一种有用方法是将其与一组具有相似需求的流程一起分类。一个有用的分类是流程的增长顺序，它用简单的术语表示流程的资源需求如何作为输入的函数增长。

作为对增长顺序的介绍，我们将分析下面的函数count_factors，它计算能均匀地除以输入n的整数的数目。该函数试图将n除以每一个小于或等于其平方根的整数。 这个实现利用了这样一个事实：如果k/n和k<根号n，那么还有一个因子j=n/k，使j>根号n。

执行count_factors需要多少时间? 在不同的机器上，确切的答案会有所不同，但是我们可以对所涉及的计算量做一些有用的一般性观察。 这个进程执行while语句体的总次数是小于$\sqrt n$的最大整数。 while语句前后的语句只执行一次。 因此，执行的语句总数是$w \times \sqrt n + v$，其中w是while语句体中的语句数，v是while语句之外的语句数。 尽管这个公式并不精确，但它通常描述了作为输入n的函数计算count_factors需要多少时间。

很难获得更精确的描述。常数w和v根本不是常数，因为对因子的赋值语句有时执行，有时不执行。 增长顺序分析可以让我们忽略这些细节，而将重点放在增长的一般形状上。 特别地，count_factors(n)的增长顺序精确地表示了计算计数因子count_factors(n)所需的时间以$\sqrt n$的速率扩展，在一些常数因子的范围内。

θ符号。 设n为参数，测量一些过程的输入大小，让R (n)成为一些资源的过程需要一个输入的大小n。在我们之前的例子中我们把n的数量给定函数计算,但也有其他的可能性。例如，如果我们的目标是计算一个数字平方根的近似值，我们可以将n作为所需精度的位数。

R(n)可以测量使用的内存数量、执行的基本机器步骤的数量，等等。 在一次只执行固定步骤的计算机中，计算表达式所需的时间与计算过程中执行的基本步骤的数量成比例。

我们说R(n)具有θ (f(n))的生长阶，写成R(n)= θ (f(n))(发音为“f(n)的theta”)，如果存在与n无关的正常数k1和k2，则R(n)具有θ的生长阶 \begin{equation} k_1 \cdot f(n) \leq R(n) \leq k_2 \cdot f(n) \end{equation}

换句话说，对于较大的n, R(n)总是被夹在两个随f(n)缩放的值之间：

• A的下界$k_1 \cdot f(n)$

• 一个上界$k_2 \cdot f(n)$

我们可以用这个定义来证明计算count_factors(n)所需的步骤数与θ (n)一样增长。

首先，我们选择k1=1和m=0，使下界状态为对于任意n>0 count_factors(n)需要至少$\sqrt n$步。 在while语句之外至少执行了4行，每一行至少需要执行1步。在while正文中至少有两行执行，以及while头本身。 所有这些至少需要一个步骤。 while主体至少要计算$\sqrt n -1$次。组合这些下界，我们看到这个过程至少需要$4 + 3 \cdot ( \sqrt n-1)$步，总是大于$k_1 \cdot \sqrt n$。

第二，我们可以验证上界。 我们假设count_factors正文中的任何一行最多需要p步。 这个假设并不是对每一行Python都成立，但是在这个例子中是成立的。 然后，计算count_factors(n)最多需要$p \cdot(5+4\sqrt n)$，因为在while语句之外有5行，而在语句内部有4行(包括头文件)。 即使每个if头值都为true，这个上界也保持不变。 最后，如果我们选择$k_2=5p$，那么所需的步骤总是小于$k \cdot \sqrt n$ 。我们的论证结束了。

2.8.4 例子:求幂

考虑计算给定数的指数的问题。我们想要一个以b为底和正整数指数n为参数的函数，并计算$b^n$。一种方法是通过递归定义

$$\begin{align*} b^n &= b \cdot b^{n-1} \\ b^0 &= 1 \end{align*}$$

这很容易转化为递归函数

>>> def exp(b, n):
        if n == 0:
            return 1
        return b * exp(b, n-1)

这是一个线性递归过程，需要θ (n)步和θ (n)空间。就像阶乘一样，我们可以很容易地建立一个等价的线性迭代，它需要相同的步数，但空间不变。

>>> def exp_iter(b, n):
        result = 1
        for _ in range(n):
            result = result * b
        return result

通过使用连续的平方，我们可以在更少的步骤中计算指数。例如，与其计算$b^8$不如

$$\begin{equation*} b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot b)))))) \end{equation*}$$

我们可以用三次乘法来计算：

$$\begin{align*} b^2 &= b \cdot b \\ b^4 &= b^2 \cdot b^2 \\ b^8 &= b^4 \cdot b^4 \end{align*}$$

这种方法适用于指数为2的幂的情况。如果我们使用递归规则，我们也可以在计算指数时利用逐次平方的优势

$$\begin{equation*} b^n = \begin{cases} (b^{\frac{1}{2} n})^2 & \text{if $n$ is even} \\ b \cdot b^{n-1} & \text{if $n$ is odd} \end{cases} \end{equation*}$$

我们也可以将此方法表示为递归函数：

>>> def square(x):
        return x*x

>>> def fast_exp(b, n):
        if n == 0:
            return 1
        if n % 2 == 0:
            return square(fast_exp(b, n//2))
        else:
            return b * fast_exp(b, n-1)

>>> fast_exp(2, 100)
1267650600228229401496703205376

fast_exp演进的进程在空间和步骤数上以n为对数增长。 要看到这一点，请注意使用fast_exp计算$b^{2n}$只需要比计算$b^n$多一次乘法运算。 因此，我们可以计算的指数大小在允许的每一次新的乘法运算中都翻倍(大约)。 因此，n的指数所需的乘法次数的增长速度与n以2为底的对数的增长速度一样快。 该过程具有θ (logn)生长。 θ (logn)生长与θ (n)生长之间的差异随着n的增大而显著。 例如，当n为1000时，fast_exp只需要14次乘法，而不是1000。

2.8.5 增长类别

设计增长阶数是为了简化计算过程的分析和比较。 许多不同的过程都有相同的增长数量级，这表明它们以类似的方式扩展。 这是一个计算机科学家的基本技能，知道和识别共同的增长顺序，并识别相同的顺序的过程。

常量。 常数项不影响过程的增长顺序。 所以，例如，θ (n)和θ ($500 \cdot n$)是同一生长阶。 这个性质来自于符号的定义，它允许我们选择任意常数$k_1$和$k_2$(比如$\frac{1}{500}$ )作为上界和下界。 为了简单起见，常量总是在增长顺序中被忽略。

对数。 对数的底数不影响过程的增长顺序。 例如，$log_2 n$和$log_{10} n$的增长顺序是相同的。 改变对数的底数等于乘以一个常数因子。

嵌套。 当一个内部计算过程对外部过程中的每一步重复时，则整个过程的增长顺序是外部过程和内部过程中步骤数量的乘积。

例如，下面的函数overlap计算列表a中同时出现在列表b中的元素的数量。

>>> def overlap(a, b):
        count = 0
        for item in a:
            if item in b:
                count += 1
        return count

>>> overlap([1, 3, 2, 2, 5, 1], [5, 4, 2])
3

在操作符列表需要Θ(n)，其中n是列表b的长度。用于Θ(m),其中m的列表a的长度。列表b中的表达式是内在的过程，for项目在一个循环中是外面的过程。 该函数的总生长阶为θ ($m \cdot n$)。

低阶项。当一个进程的输入增长时，计算中增长最快的部分支配着所使用的总资源。符号抓住了这种直觉。总的来说，除增长最快的项外，所有项都可以去掉，而不改变增长顺序。

例如，考虑one_more函数，它返回列表a的元素比a的其他元素大一的个数。也就是说，在列表[3,14,15,9]中，元素15比14多一个，因此one_more将返回1。

>>> def one_more(a):
        return overlap([x-1 for x in a], a)

>>> one_more([3, 14, 15, 9])
1

这个计算分为两个部分：列表推导和overlap调用。 对于长度为n的列表a，列表综合需要θ (n)步，而调用overlap需要θ ($n^2$)步。 台阶的和是θ ($n+n^2$)，但这不是表达增长顺序的最简单的方式。 θ ($n^2 + k \cdot n$)和θ ($n^2$)对任何常数k都是等价的，因为对任何k来说，$n^2$项最终将支配k的总数。事实上，只有当n大于某个最小m时，边界才成立这个等价性。 为了简单起见，低阶项总是在增长顺序中被忽略，所以我们永远不会在表达式中看到一个和。

常见类别。 有了这些等价性，就会出现一小部分共同的范畴来描述大多数的计算过程。 下面列出了最常见的从最慢到最快的增长，以及随着投入增加的增长的描述。 下面是每个类别的示例。

类别	θ符号	增长描述	示例
常数	$\Theta(1)$	增长与输入无关	abs
对数	$\Theta(log n)$	乘以输入的增量资源	fast_exp
线性	$\Theta(n)$	增加输入会增加资源	exp
二次	$\Theta(n^2)$	增加输入会增加n个资源	one_more
指数	$\Theta(b^n)$	增加输入会使资源倍增	fib

其它类别也存在，如$\Theta(\sqrt n)$计数因子的增长。 然而，这些类别特别常见。

指数增长描述了许多不同的增长顺序，因为改变基数b确实会影响增长顺序。 例如，我们的树递归斐波那契计算fib的步骤数在输入n时呈指数增长。特别地，我们可以证明第n个斐波那契数是最接近的整数

$$\begin{equation*} \frac{\phi^{n-2}}{\sqrt{5}} \end{equation*}$$

其中，ϕ为黄金比例：

$$\begin{equation*} \phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180 \end{equation*}$$

此外，树递归过程需要$\Theta(\phi^n)$步，这是一个随n指数增长的函数。