为什么字典中的查找比Python中的两个iftest快得多？

Question

我需要读取千兆字节的文本，所以我正在尝试优化我的代码。当我这样做的时候，我发现，对于我的问题，使用字典比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]

使用ipythong的%time我发现在字典中查找的速度比使用两个if测试快一倍多：

^{pr2}$

既然测试如此基础，我就没想到会有性能差异。这是众所周知的吗？有人能解释一下为什么会这样吗？在

更新

我检查了上面的两个函数以及下面的check3（）如何影响我实际代码的运行时，并且对总时间没有影响。所以，要么字典带来的提升在一个真实的例子中不是很高，在这个例子中'R'和'F'值需要不断地从文件中读取，要么这段代码不是我瓶颈的一部分。在

无论如何，谢谢你的回答！在

Answer 1

Python对字典进行了大量优化；查找是O(1)-它只是一个哈希表查找，因此只有一个“操作”—是if测试序列（即O(n)）所获得操作数目的一半。在

Answer 2

与许多VM代码一样，主要归结为涉及的VM操作码的数量。在

您可以使用dis检查组合函数：

import dis
dis.dis(func)

在2.6.4中，check1为每个比较和分支获取大约15-20个操作码（取决于代码路径）。check2只需要7个（在添加缺少的chedict字典后，全局声明）。在

Answer 3

实际上，您还没有证明在字典中查找比两个if测试快。你所展示的是，在特定的字典中查找比这两个测试更快。在

通常字典查找需要几个步骤：从密钥生成一个哈希来查找潜在匹配，然后通过比较这些密钥来测试潜在匹配。有时，如果存在哈希表冲突，则可能需要进行多次比较。如果你有用户为键定义的类，那么这两个步骤可能都很慢，对于字符串来说它们通常很快，但在一个特定的情况下，它们确实非常快，而且你已经达到了这种情况。在

字典使用的键是短字符串，与编译时已知标识符的格式相匹配。Python将帮助您“实习”字符串“R”和“F”。因为在测试中使用的字符串在编译时也是已知的，所以它们将是完全相同的实例。对于字典查找来说，所有这些意味着对于只有字符串键的字典使用专门的查找版本，哈希始终是预先计算的，并且密钥比较是通过比较地址来完成的（至少当它成功并且使用两个密钥时，它决不会失败）。在

你的真实代码会，我假设是从输入中读取字符串，所以它不会有“R”的内部副本。这意味着它需要计算每行输入的哈希值。地址不匹配，因此必须为每个测试调用字符串比较函数。对于只有字符串键，您仍然可以得到一些优化，至少它不必对可能不是字符串的对象进行一般用途的比较。在

if语句对对象类型一无所知，因此它们每次都会进行一般用途的比较。在