时间比位移快两倍？
我正在查看sorted_containers的来源，很惊讶地看到这一行 ：
self._load, self._twice, self._half = load, load * 2, load >> 1 这里的load是一个整数。 为什么在一个地方使用位移，在另一个位置乘法？ 移位可能比积分除以2快，但为什么不用一个移位来代替乘法呢？ 我以下列情况为基准：
- （倍，分）
- （换class，换class）
- （时代，class次）
- （移位，除）
并发现＃3始终比其他select更快：
# self._load, self._twice, self._half = load, load * 2, load >> 1 import random import timeit import pandas as pd x = random.randint(10 ** 3, 10 ** 6) def test_naive(): a, b, c = x, 2 * x, x // 2 def test_shift(): a, b, c = x, x << 1, x >> 1 def test_mixed(): a, b, c = x, x * 2, x >> 1 def test_mixed_swaped(): a, b, c = x, x << 1, x // 2 def observe(k): print(k) return { 'naive': timeit.timeit(test_naive), 'shift': timeit.timeit(test_shift), 'mixed': timeit.timeit(test_mixed), 'mixed_swapped': timeit.timeit(test_mixed_swaped), } def get_observations(): return pd.DataFrame([observe(k) for k in range(100)])
问题是：
我的testing是否有效？ 如果是这样，为什么（乘，移）比（移位，移位）更快？
我在Ubuntu 14.04上运行Python 3.5。
编辑
以上是该问题的原始陈述。 Dan Getz在他的回答中提供了一个很好的解释。
为了完整起见，当乘法优化不适用时，这里是大x示例说明。
这似乎是因为在CPython 3.5中对小数的乘法进行了优化，小数左移不是这样。 积极的左移总是创build一个更大的整数对象来存储结果，作为计算的一部分，而对于在testing中使用的sorting的乘法，一个特殊的优化避免了这一点，并创build了一个正确大小的整数对象。 这可以在Python的整数实现的源代码中看到。
因为Python中的整数是任意精度的，所以它们被存储为整数“数字”的数组，每个整数数字的位数是有限制的。 因此，在一般情况下，涉及整数的操作不是单个操作，而是需要处理多个“数字”的情况。 在pyport.h中 ，该位限制在64位平台上定义为 30位，否则定义为 15位。 （我将从这里调用这个30来简化说明，但是请注意，如果你使用Python编译为32位，那么你的基准testing结果将取决于x是否小于32,768。）
当一个操作的input和输出保持在这个30位的限制内时，操作可以以一种优化的方式来处理，而不是一般的方式。 整数乘法实现的开始如下：
static PyObject * long_mul(PyLongObject *a, PyLongObject *b) { PyLongObject *z; CHECK_BINOP(a, b); /* fast path for single-digit multiplication */ if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) { stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b); #ifdef HAVE_LONG_LONG return PyLong_FromLongLong((PY_LONG_LONG)v); #else /* if we don't have long long then we're almost certainly using 15-bit digits, so v will fit in a long. In the unlikely event that we're using 30-bit digits on a platform without long long, a large v will just cause us to fall through to the general multiplication code below. */ if (v >= LONG_MIN && v <= LONG_MAX) return PyLong_FromLong((long)v); #endif }
所以，当乘以两个整数，每个都适合30位数字时，这是由CPython解释器直接乘法完成的，而不是将整数作为数组使用。 （在正整数对象上调用MEDIUM_VALUE()只需获取其第一个30位数字）。如果结果适合单个30位数字， PyLong_FromLongLong()会在相对较less的操作中注意到这一点，并创build一个数字整数对象来存储它。
相比之下，左移并不是以这种方式优化的，每一个左移处理整数被移位为一个数组。 特别是，如果您查看long_lshift()的源代码， long_lshift()在左移小但正向的情况下，总是会创build一个2位整数对象，如果仅将其长度截断为1 （我的注释在/*** ***/ ）
static PyObject * long_lshift(PyObject *v, PyObject *w) { /*** ... ***/ wordshift = shiftby / PyLong_SHIFT; /*** zero for small w ***/ remshift = shiftby - wordshift * PyLong_SHIFT; /*** w for small w ***/ oldsize = Py_ABS(Py_SIZE(a)); /*** 1 for small v > 0 ***/ newsize = oldsize + wordshift; if (remshift) ++newsize; /*** here newsize becomes at least 2 for w > 0, v > 0 ***/ z = _PyLong_New(newsize); /*** ... ***/ }
整数划分
你没有询问整体楼层划分与右移相比的糟糕performance，因为这符合你的（和我的）期望。 但是将一个小的正数除以另一个小的正数也不如小乘法那样优化。 每个//使用函数long_divrem()计算商和余数。 这个余数是乘以一个小的除数，并存储在一个新分配的整数对象 ，在这种情况下立即被丢弃。
