为什么早期回归比其他人慢?

问题:

这是an answer I gave a few days back的后续问题。 编辑:似乎该问题的OP已经使用我向他发布的代码来询问the same question,但是我并不知道。道歉。提供的答案是不同的!
基本上我观察到:

>>> def without_else(param=False):
...     if param:
...         return 1
...     return 0
>>> def with_else(param=False):
...     if param:
...         return 1
...     else:
...         return 0
>>> from timeit import Timer as T
>>> T(lambda : without_else()).repeat()
[0.3011460304260254, 0.2866089344024658, 0.2871549129486084]
>>> T(lambda : with_else()).repeat()
[0.27536892890930176, 0.2693932056427002, 0.27011704444885254]
>>> T(lambda : without_else(True)).repeat()
[0.3383951187133789, 0.32756996154785156, 0.3279120922088623]
>>> T(lambda : with_else(True)).repeat()
[0.3305950164794922, 0.32186388969421387, 0.3209099769592285]

…或换句话说:无论if条件是否触发,拥有else子句都更快。
我假设它与二者生成的不同字节码有关,但是有人能够详细地确认/解释吗?
 编辑:似乎并不是每个人都能够重现我的时间,所以我认为在我的系统上给出一些信息可能是有用的。我正在运行Ubuntu 11.10 64位,并安装了默认的python。 python生成以下版本信息:

Python 2.7.2+ (default, Oct  4 2011, 20:06:09) 
[GCC 4.6.1] on linux2

以下是Python 2.7中的反汇编的结果:

>>> dis.dis(without_else)
  2           0 LOAD_FAST                0 (param)
              3 POP_JUMP_IF_FALSE       10

  3           6 LOAD_CONST               1 (1)
              9 RETURN_VALUE        

  4     >>   10 LOAD_CONST               2 (0)
             13 RETURN_VALUE        
>>> dis.dis(with_else)
  2           0 LOAD_FAST                0 (param)
              3 POP_JUMP_IF_FALSE       10

  3           6 LOAD_CONST               1 (1)
              9 RETURN_VALUE        

  5     >>   10 LOAD_CONST               2 (0)
             13 RETURN_VALUE        
             14 LOAD_CONST               0 (None)
             17 RETURN_VALUE        

回答:

这是一个纯粹的猜测,我没有想出一个简单的方法来检查它是否正确,但我有一个理论为你。
我尝试了你的代码并得到相同的结果,without_else()反复比with_else()稍慢一些

>>> T(lambda : without_else()).repeat()
[0.42015745017874906, 0.3188967452567226, 0.31984281521812363]
>>> T(lambda : with_else()).repeat()
[0.36009842032996175, 0.28962249392031936, 0.2927151355828528]
>>> T(lambda : without_else(True)).repeat()
[0.31709728471076915, 0.3172671387005721, 0.3285821242644147]
>>> T(lambda : with_else(True)).repeat()
[0.30939889008243426, 0.3035132258429485, 0.3046679117038593]

考虑到字节码是相同的,唯一的区别是函数的名称。特别地,时序测试对全局名称进行查找。尝试重命名without_else(),差异消失:

>>> def no_else(param=False):
    if param:
        return 1
    return 0

>>> T(lambda : no_else()).repeat()
[0.3359846013948413, 0.29025818923918223, 0.2921801513879245]
>>> T(lambda : no_else(True)).repeat()
[0.3810395594970828, 0.2969634408842694, 0.2960104566362247]

我的猜测是without_elseglobals()中的其他内容发生哈希冲突,所以全局名称查找稍慢。
 编辑:具有7或8个键的字典可能有32个插槽,所以在此基础上without_else__builtins__发生哈希冲突

>>> [(k, hash(k) % 32) for k in globals().keys() ]
[('__builtins__', 8), ('with_else', 9), ('__package__', 15), ('without_else', 8), ('T', 21), ('__name__', 25), ('no_else', 28), ('__doc__', 29)]

澄清哈希的工作原理:
 __builtins__哈希值为-1196389688,减小表的大小(32)意味着它存储在表的#8时隙中。
 without_else哈希到505688136,减少模32是8,所以有一个碰撞。要解决这个Python计算:
从…开始:

j = hash % 32
perturb = hash

重复此操作,直到找到空闲插槽:

j = (5*j) + 1 + perturb;
perturb >>= 5;
use j % 2**i as the next table index;

200的X- 200 X-幸运的是,这个循环只会重复一次。哈希表大小是2的幂,所以2**i是哈希表的大小,i是从哈希值j使用的比特数,
每个探针进入表格可以找到以下之一:

  • 插槽是空的,在这种情况下,探测停止,我们知道
    价值不在表中。
  • 这个插槽是未使用的,但在过去使用过,在这种情况下我们去尝试
    下一个值计算如上。
  • 插槽已满,但表中存储的完整散列值不是
    与我们正在寻找的键的哈希一样(就是这样
    __builtins__ vs without_else)的情况下发生。
  • 插槽已满,并且具有我们想要的哈希值,然后是Python
    检查我们正在查找的关键字和对象是否是
    相同的对象(在这种情况下,它们将是短字符串)
    这可以是标识符被实际使用相同的标识符
    完全相同的字符串)。
  • 最后当插槽已满时,哈希匹配准确,但键
    不是相同的对象,那么Python才会尝试
    比较他们的平等。这是比较慢的,但在
    名称查找的情况实际上不应该发生。

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: Why is early return slower than else?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

25 − 20 =