为什么在Python中字典查找比两个if测试快得多？

Question

我需要读取几GB的文本，所以我在尝试优化我的代码。在这个过程中，我发现对于我的问题来说，使用字典比用if语句要快。

check = {'R':'-', 'F':'+'}
seqs = ['R', 'F']*100

def check1():
    for entry in seqs:
        if entry == 'R':
            strand = '-'
        if entry == 'F':
            strand = '+'

def check2():
    for entry in seqs:
        strand = check[entry]

通过使用ipython的%timeit，我发现查找字典的速度大约是用两个if语句的两倍还要快一点：

In [63]: %timeit check1()
10000 loops, best of 3: 38.8 us per loop

In [64]: %timeit check2()
100000 loops, best of 3: 16.2 us per loop

因为if语句是非常基础的东西，我本来没想到会有性能差异。这是大家都知道的吗？有人能解释一下为什么会这样吗？

更新

我检查了上面两个函数以及下面的check3()对我实际代码运行时间的影响，发现对总时间没有影响。所以，要么在实际情况下，使用字典的性能提升并没有那么明显，因为'R'和'F'的值需要不断从文件中重新读取，要么这段代码根本不是我性能瓶颈的一部分。

无论如何，谢谢大家的回答！

Answer 1

在Python中，字典的性能非常好；查找一个值的时间复杂度是O(1)，这意味着它只需要一次简单的操作，就像在一个哈希表中查找一样。相比之下，如果你用一系列的if判断来查找，那就需要O(n)的时间，也就是说操作的次数会翻倍。

Answer 2

你并没有真正证明查字典比两个if测试要快。你展示的只是查这个特定字典比那两个测试快。

通常，查字典需要几个步骤：首先从键生成一个哈希值来找可能的匹配项，然后通过比较键来测试这个匹配项。如果有哈希表冲突，可能还需要进行多次比较。如果你用的是用户自定义的类作为键，这两个步骤可能会比较慢；对于字符串来说，通常是很快的，但在某些特定情况下会特别快，而你正好遇到了这种情况。

你的字典使用的是短字符串作为键，这些字符串的格式在编译时就已经确定。Python会很贴心地把你的字符串'R'和'F'进行“内部化”。因为你在测试中使用的字符串在编译时也是已知的，所以它们会是完全相同的实例。这意味着在查字典时，对于只有字符串键的字典，会使用一种特殊的查找方式，哈希值总是预先计算好的，键的比较是通过比较地址来完成的（至少在成功的情况下，对于你的两个键来说，它永远不会失败）。

我假设你的真实代码会从输入中读取字符串，所以它不会有'R'的内部化副本。这意味着它需要为每一行输入计算哈希值。地址不会匹配，因此每次测试时都需要调用字符串比较函数。不过，使用字符串键仍然能获得一些优化，至少它不需要进行可能不是字符串的对象的通用比较。

而if语句对对象类型一无所知，所以每次都要进行通用比较。

Answer 3

很多虚拟机（VM）的代码，主要是看里面有多少个操作码（opcodes）。

你可以用 dis 命令来查看这些组装好的函数：

import dis
dis.dis(func)

在版本2.6.4中，check1这个函数每次比较和分支大约需要15到20个操作码（具体数量取决于代码的执行路径）。而check2只需要7个操作码（这是在添加了缺失的全局字典 chedict 之后）。