时间相关的技巧

计时代码

程序员中有一句流行的说法：“先确保正确，再追求高效。” 假设我们的程序已经正确，且有多种解决方案，我们应选择最快的一种。这在 Python 中尤为常见，尽管《Python 之禅》中提到：“应该有一种——而且最好只有一种——显而易见的实现方式。”

一种错误的计时方法是使用 time 模块中的 time() 函数，在代码片段前后分别调用一次。该函数精度较低，通常远低于代码片段的实际执行时间。正确的工具是 timeit 模块中的 timeit() 函数。该函数接受若干参数，其中前两个最为重要。

• 第一个参数是要计时的代码片段，必须以字符串形式传入。否则，Python 会在调用计时函数之前就执行这段代码。代码中必须包含所有涉及变量的定义，因为函数会在一个干净的环境中评估参数，不包含任何已定义的函数、变量或已导入的模块。函数会执行代码指定次数（number 是可选参数），并返回总执行时间。
• 第二个参数是另一个字符串，用于初始化代码。timeit() 函数会在开始收集统计数据前执行一次该代码。我们可以用它来导入模块或定义全局变量。

我们可能会好奇：平方一个数的最佳方式是什么？是直接相乘，还是使用幂运算符（**），或是调用 math.pow()？在这种情况下，我们应该遵循《Python 之禅》中的建议：“面对模糊性，拒绝猜测的诱惑。” 使用 timeit()！

注意：如果对整数应用前两种代码片段，结果会有显著差异。更多细节请参见本课末尾的“警惕大整数和慢整数”部分。函数返回的是总执行时间（单位：秒）。

timeit() 函数执行语句 1,000,000 次。将返回的时间除以 number 即可得到每次语句的平均执行时间。

让我们运行以下代码：

1print(timeit.timeit('a ** 2', 'a = 10.0'))
2print(timeit.timeit('a * a', 'a = 10.0'))
3print(timeit.timeit('math.pow(a, 2)', 'import math; a = 10.0'))

尽管保留了小数点后十七位数字，但乘法仍然明显更快，紧随其后的是幂运算符。math.pow() 的性能最差。

将一个数乘以自身比调用 math.pow() 更快。

检查点节省时间

最令人沮丧的事情莫过于在撰写博士论文过程中意外删除未完成的文件，或者程序经过数小时甚至数天的高强度计算后崩溃。频繁备份有助于应对前者，而检查点机制则能有效应对后者。

检查点是一种实时备份形式，可通过 Python 的序列化（pickling）轻松实现。

创建检查点的方法是将那些难以重新计算的变量值保存到文件中，一旦程序崩溃，就可以从文件中恢复这些值，而无需重新计算。

例如，我们的程序可能调用了虚构的、耗时极长的函数 foo() 和 bar()：

1result1 = foo(original_data)
2result2 = bar(result1)

如果我们希望将最终结果与中间结果同等对待，可以添加一个或多个检查点。应为检查点数据创建一个目录。在重新计算前，先检查结果是否已存在。若涉及多个结果，可将它们作为元组存储在同一文件中，或依次存储。pickle 支持单个文件中保存多个对象。

1try:
2   with open('checkpoints/result1.p', 'rb') as infile:
3       result1 = pickle.load(infile) 
4except FileNotFoundError:
5    result1 = foo(original_data)
6    with open('checkpoints/result1.p', 'wb') as outfile:
7        pickle.dump(result1, outfile)
8try:
9    with open('checkpoints/result2.p', 'rb') as infile:
10        result2 = pickle.load(infile) 
11except FileNotFoundError:
12    result2 = bar(result1)
13    with open('checkpoints/result2.p', 'wb') as outfile:
14        pickle.dump(result2, outfile)

该方案可扩展至任意数量的中间阶段，能显著节省时间和精力。

此技巧与 CacheIt 类似。如前所述，检查点本质上是一种缓存机制。

“经典”的缓存方法是按对象标识符组织目录来存储先前获取的对象。这些标识符可以是对象的 URL、推文 ID 或数据库行号等，只要是与对象来源相关的信息即可。

优化查找操作

有人认为（许多计算机科学入门书籍也认同）：在计算中，搜索数据是最常见的操作——甚至可能是最频繁的操作。如果我们需要某种引擎，那说明这个操作非常重要。

使用 in 操作符

Python 中查找集合中某项的标准方法是使用 in 操作符。该操作符会查找某个项目，并判断其是否存在于集合中（无论是作为值还是对象）。对于小型集合的一次查找，我们无需担心性能问题。但随着集合规模和查找次数的增长，性能问题可能变得突出。

列表查找速度最慢。列表是顺序结构，要查找一个值为 1001 的“针”，Python 必须遍历整个列表，逐个比较每个元素。最坏情况下需要扫描全部列表。列表越长，所需时间越久。在普通计算机上，检查一个不存在的值是否在包含 1,000 个整数的列表中，大约需要 9.1 微秒：

让我们在此尝试一下。

1print(timeit('1001 in haystack', 'haystack=list(range(1000))'))

元组的情况也类似。虽然不可变，但仍是顺序结构，因此性能与列表相当：

1print(timeit('1001 in haystack', 'haystack=tuple(range(1000))'))

字典和集合则提供了显著提升。对于包含 1,000 个不同数字的集合，其性能比列表高出 450 到 500 倍，且随着集合规模增大，加速效果更加明显：

1print(timeit('1001 in haystack', 'haystack=dict(enumerate(range(1000)))', number=100000000))
2print(timeit('1001 in haystack', 'haystack=set(range(1000))', number=100_000_000))

哈希表原理

这是如何实现的？Python 的字典和集合是通过 哈希表 实现的。哈希表具有近乎常数的查找时间。它们由数组中的桶（槽）组成。桶的位置通过哈希函数根据目标值计算得出。函数调用和数组查找都只需常数时间。如果目标值存在于集合中，则必然存储在特定桶中；若不在该桶中，则肯定不在集合中。简单而高效。

选择合适的集合类型，有时甚至决定了程序能否正常运行。实际应用中，如果给定一个值列表（例如自然语言处理任务中的停用词列表），并且计划在循环中多次搜索，应优先将列表转换为集合，然后在集合中进行搜索：

1import nltk
2nltk.download("stopwords")
3stops = set(nltk.corpus.stopwords.words('english')) 
4text='Stopwords are the English words which does not add much meaning to a sentence. They can safely be ignored without sacrificing the meaning of the sentence. For example, the\
5 words like the, he, have etc. Such words are already captured this\
6  in corpus named corpus.'
7print([ word for word in text.split() if word not in stops])

not in 操作符同样适用。

避免函数调用，它们代价高昂

即使没有参数，调用函数也需要时间。在普通计算机上，无参函数调用大约需要 55 纳秒。例如，一个不带参数但计算两个数之和的函数：

1def sumOfTwo():
2   a = 4
3   b = 5
4   sum = a + b
5   return sum

让我们计算上述函数调用的执行时间。

1import timeit
2mycode= '''
3def sumOfTwo():
4   a = 4
5   b = 5
6   sum = a + b
7   return sum
8
9#print(sumOfTwo())
10'''
11print(timeit.timeit(stmt=mycode))

此外，每传递一个参数还会额外增加约 3 纳秒的开销。虽然微小，但在循环中反复调用时累积效应明显。

现在，让我们向上述函数传入参数，并计算执行时间差异。

1import timeit
2mycode= '''
3def sumOfTwo(a, b):
4   sum = a + b
5   return sum
6
7#print(sumOfTwo(5, 4))
8'''
9print(timeit.timeit(stmt=mycode))

这种延迟递增意味着：不应在无必要的情况下创建和调用函数。

• 直接使用算术表达式加法，比调用 add(a,b) 函数更快速、更优。
• 包含十个参数的函数，略慢于接收一个包含十项的元组的函数。
• 将一个数乘以自身，比调用 math.pow() 更快。

我们该如何判断何时应避免函数调用？

• 是否有办法不依赖该调用解决问题？
• 无函数的解决方案是否易于维护和阅读？若是，应避免调用。
• 若无函数方案明显更快，应避免调用。

否则，仍应调用函数。因为我们的首要目标是先确保正确，再追求高效。

先构建，再打印

函数调用在执行时间上代价较高，但几乎没有比 print() 及其他输入输出函数调用更昂贵的了。显示输出涉及与操作系统交互（本身较慢），以及滚动控制台窗口（同样缓慢）。对比以下两个实现相同目标的代码片段：在一行中显示 1,000 个字母 a。

1# 分段打印
2for _ in range(1000): 
3  print('a', end='')
4
5print()

先构建字符，再一次性打印。

1# 先构建，再打印
2a = 1000 * 'a' 
3print(a)

第一个片段是字面意义上的实现：逐个显示字母 1,000 次，不换行，最后才换行。第二个片段先构造一个包含 1,000 个 a 的字符串，然后一次性输出。

在普通计算机上，第二个片段执行时间更短。

1import timeit
2code1 = '''
3for _ in range(1000): 
4  print('a', end='')
5
6print()
7'''
8code2 = '''
9a = 1000 * 'a' 
10print(a)
11'''
12print(timeit.timeit(stmt = code1, number=100))
13print(timeit.timeit(stmt = code2, number=100))

Python 的字符串函数和操作符非常高效。若性能至关重要，应尽可能将输出合并为一个字符串，并尽量减少 print() 的调用次数。

用空间换时间

Python 提供了丰富的内置数据类型和数据结构，标准库中还有更多。似乎总有合适的容器适用于各种场景。

Python 拥有强大的数据类型和数据结构集合。但该集合中并不包括树结构，无论是二叉树还是其他类型的树。

Python 字典的平均查找时间复杂度为 $O(1)$，我们无法超越这一性能。

有时，两个容器协同工作，比单独使用一个更高效。

考虑这样一个场景：需要从列表中去除重复项，同时保持原有顺序（仅保留每个元素的首次出现）。将列表转为集合再转回列表的朴素方法失败，因为集合是无序的。

1data = [7, 2, 3, 4, 7, 7, 7]
2print(list(set(data)))

在 CPython 3.6 及以上版本中，字典的顺序被保证为插入顺序。我们可以使用原始列表元素作为键，常量（如 1）作为值来构造字典。若存在重复键，仅保留第一个：

1data = [7, 2, 3, 4, 7, 7, 7]
2print(list({d:1 for d in data}.keys()))

如果使用较早版本的 Python 呢？检查下一个元素是否已在列表中，效率很低，因为列表的查找速度很慢。此时可结合使用集合追踪重复项，同时用列表收集唯一值：

1dups = set()
2result = []
3for d in data:
4  if d not in dups:
5    result.append(d)
6    dups.add(d)
7
8print(result)

两个并行的数据结构需要更多内存空间，但性能更优。最好的做法是直接升级到更新版本的 Python。

警惕大整数和慢整数

与 C、C++、Java 等主流编程语言不同，Python 支持任意大小的整数（极大或极小）。小于等于 sys.maxsize（64 位 CPU 上为 9,223,372,036,854,775,807）的整数以 CPU 字长原生表示。更大的整数则采用更复杂的实现方式。

让我们查看 sys.maxsize：

1# 导入 sys 模块
2import sys
3       
4# 获取最大值
5maxVal = sys.maxsize
6print(maxVal)

在 Python 中，我们还能处理超过 sys.maxsize 的更大整数。由于这一特性，可以进行任意精度的整数运算。例如，可以表示一个“古戈尔”（googol），即 1 后面跟着 100 个零：

让我们运行以下代码：

1print(10**100)

再加 1 并检查：

1print(10**100+1)

无界整数并非免费的，因为所有整数运算都产生精确结果，而浮点运算只是近似值。整数表达式的求值可能耗时更长，但精度更高。

让我们比较两项操作：

1print(10 ** 100 * 10 ** 100) # 整数，精确
2print(10. ** 100 * 10. ** 100) # 浮点数，近似
3print(timeit.timeit('10**100 * 10**100'))
4print(timeit.timeit('10.**100 * 10.**100'))

通常我们不需要如此精确的大数结果。应使用浮点数，享受更快的执行速度。

测验