Python3的速度更快？len或字典查找？

Question

什么是更快(Python3)？

if len(interval) <= 2:
  return 1

要么:

if interval in intervaldict:
  return intervaldict[interval]

是否取决于字符串的长度或字典的长度？我做了一些简单的测试,它看起来len更贵,这对我来说似乎违反直觉.

Answer 1

该len解决方案是或多或少地更慢,因为有更多的参与.你可以通过以下方式分解代码来看到这一点dis.dis:

>>> import dis
>>> dct = {1:1, 2:2}
>>> dis.dis('1 in dct')
  1           0 LOAD_CONST               0 (1)
              3 LOAD_NAME                0 (dct)
              6 COMPARE_OP               6 (in)
              9 RETURN_VALUE
>>> dis.dis('len(dct) <= 2')
  1           0 LOAD_NAME                0 (len)
              3 LOAD_NAME                1 (dct)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 LOAD_CONST               0 (2)
             12 COMPARE_OP               1 (<=)
             15 RETURN_VALUE
>>>

请注意,该len解决方案具有额外的名称查找len以及函数调用.这些都需要时间.但是,正如您从timeit.timeit下面的测试中看到的那样,性能差异非常微不足道:

>>> import timeit
>>> dct = {1:1, 2:2}
>>> timeit.timeit('1 in dct', 'from __main__ import dct')
0.24376701508152573
>>> timeit.timeit('len(dct) <= 2', 'from __main__ import dct')
0.4435952055358978
>>>

此外,这些统计数据将不依赖于字典的长度,因为这两个改变len,并in有O(1)使用词典(恒定)的复杂性.

Answer 2

请参阅Python的时间复杂性

len在所有情况下,列表上的是O(1),而在字典中查找是最坏情况下的O(n).复杂性和运行时是不同的.对于某些情况,字典查找将花费更长时间,但它可能很少发生,并且仅对于如此大的字典而言,它将不是最适合您的用途.