我正在查看 sorted_containers 的来源并惊讶地看到 this line:
self._load, self._twice, self._half = load, load * 2, load >> 1
这里 load
是一个整数。为什么在一个地方使用位移,而在另一个地方使用乘法?移位可能比除以 2 更快,这似乎是合理的,但为什么不将乘法也替换为移位呢?我对以下案例进行了基准测试:
(次,除)(移位,移位)(次,移位)(移位,除)
并发现#3 始终比其他替代方案更快:
# 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_swapped():
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_swapped),
}
def get_observations():
return pd.DataFrame([observe(k) for k in range(100)])
https://i.stack.imgur.com/mrSuI.png
问题:
我的测试有效吗?如果是这样,为什么 (multiply, shift) 比 (shift, shift) 快?
我在 Ubuntu 14.04 上运行 Python 3.5。
编辑
以上是问题的原始陈述。 Dan Getz 在他的回答中提供了一个很好的解释。
为完整起见,以下是不适用乘法优化时较大 x
的示例插图。
https://i.stack.imgur.com/2btSH.png
x
?
x
非常大,因为这只是它如何存储在内存中的问题,对吧?
这似乎是因为小数的乘法在 CPython 3.5 中得到了优化,而小数的左移则没有。作为计算的一部分,正左移总是创建一个更大的整数对象来存储结果,而对于您在测试中使用的排序的乘法,特殊的优化可以避免这种情况并创建一个正确大小的整数对象。这可以在 the source code of Python's integer implementation 中看到。
因为 Python 中的整数是任意精度的,所以它们存储为整数“数字”数组,每个整数位的位数有限制。所以在一般情况下,涉及整数的运算不是单个运算,而是需要处理多个“数字”的情况。在 pyport.h 中,此位限制 is defined as 在 64 位平台上为 30 位,否则为 15 位。 (为了简单起见,我从这里开始将其称为 30。但请注意,如果您使用的是为 32 位编译的 Python,那么您的基准测试结果将取决于 x
是否小于 32,768。)
当操作的输入和输出保持在这个 30 位的限制内时,可以以优化的方式而不是一般方式来处理操作。 integer multiplication implementation 的开头如下:
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()
将在相对较少的操作中注意到这一点,并创建一个-digit 整数对象来存储它。
相比之下,左移并未以这种方式进行优化,并且每次左移都将整数作为数组进行移位处理。特别是,如果您查看 long_lshift()
的源代码,在一个小的但为正的左移的情况下,总是会创建一个 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);
/*** ... ***/
}
整数除法
与右移相比,您没有询问整数地板除法的性能更差,因为这符合您(和我)的期望。但是,将一个小的正数除以另一个小的正数也没有像小的乘法那样优化。每个 //
都使用函数 long_divrem()
计算商 和 余数。这个余数是针对具有 a multiplication 和 is stored in a newly-allocated integer object 的小除数计算的,在这种情况下会立即丢弃。
x
的时序图可能会很有趣。