为什么在字典中查找要比Python中的两个if-tests快得多？

Question

我需要阅读千兆字节的文本,所以我正在尝试优化我的代码.这样做时,我发现,对于我的问题,使用字典比if-tests更快.

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的%timeit我发现在字典中查找的速度比使用两个if-tests快两倍:

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-tests是如此基本,我没想到性能差异.这是众所周知的吗？任何人都可以解释为什么会这样吗？

UPDATE

我检查了上面的两个函数以及下面的check3()如何影响我的实际代码的运行时间,并且对总时间没有影响.因此,在现实世界的例子中,要么字典中的提升不是很高,其中"R"和"F"值需要不断地从文件中重新读取,或者这段代码不是我的瓶颈的一部分.

无论如何,谢谢你的答案!

Answer 1

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

通常,字典查找需要几个步骤:从密钥生成哈希以找到潜在匹配,然后通过比较密钥来测试潜在匹配.如果存在哈希表冲突,有时可能需要进行多次比较.如果你有用户定义的键类,那么这两个步骤都可能很慢,它们通常对字符串很快,但在一个特殊情况下它们真的非常快,你已经遇到了这种情况.

您的字典使用的短字符串与编译时已知的标识符格式相匹配.Python将有助于"实践"你的字符串'R'和'F'.由于您在测试中使用的字符串在编译时也是已知的,因此它们将是完全相同的实例.对字典查找的所有这些意味着,查找的专用版本用于仅具有字符串键的字典,哈希始终是预先计算的,并且通过比较地址来进行密钥比较(至少在成功时和您的它永远不会失败的两把钥匙).

你的真实代码,我假设是从输入读取字符串,所以它不会有'R'的实习副本.这意味着它需要计算每行输入的哈希值.地址不匹配,因此必须为每个测试调用字符串比较函数.你仍然只对字符串键进行一些优化,至少它不必对可能不是字符串的对象进行通用比较.

这些if语句对于对象类型一无所知,因此它们每次都会进行通用比较.