对于Python 3.x整数，比位移位快两倍吗？

我正在查看sorted_containers的源代码，惊讶地看到了这一行：

self._load, self._twice, self._half = load, load * 2, load >> 1

这里load是一个整数。为什么在一个地方使用位移位，而在另一个地方使用乘法？位移位可能比整数除以2更快似乎是合理的，但为什么不也用移位来代替乘法呢？我对以下情况进行了基准测试：
1.（倍，除）
1.（轮班，轮班）
1.（次数、班次）
1.（移位、除法）
并发现#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)])

第一节第一节第一节第一节第一次
问题是：
我的测试有效吗？如果有效，为什么（乘法，移位）比（移位，移位）快？
我在Ubuntu 14.04上运行Python 3.5。

- 编辑**

以上是这个问题的原始陈述。丹·格茨在他的回答中提供了极好的解释。
为了完整起见，下面是不应用乘法优化时较大x的示例说明。
第一节第二节第一节第三节第一节

这似乎是因为在CPython 3.5中对小数乘法进行了优化，而对小数左移则没有进行优化。正左移总是创建一个更大的整数对象来存储结果，作为计算的一部分，而对于测试中使用的乘法，一个特殊的优化避免了这个问题，并且创建了一个正确大小的整数对象。2这可以在the source code of Python's integer implementation中看到。
因为Python中的整数是任意精度的，它们被存储为整数“位数”数组，每个整数位数的位数是有限制的。所以在一般情况下，涉及整数的操作不是单个操作，而是需要处理多个“位数”的情况。在 pyport.h 中，这个位数限制被定义为64位平台上的30位。否则为15位（为了简化说明，我将从这里开始称之为30。但是请注意，如果您使用的是为32位编译的Python，则基准测试的结果将取决于x是否小于32，768）。
当一个操作的输入和输出保持在这个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()将在相对少量的操作中注意到这一点，并创建一个一位整数对象来存储它。
相比之下，左移并不是这样优化的，每一次左移都是将整数作为一个数组来处理的，特别是，如果你看一下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()计算商 * 和余数 *。此余数是通过乘法为小除数计算的，并存储在新分配的整数对象中，在这种情况下，立即丢弃该整数对象。
或者至少，当这个问题最初被问到的时候是这样的，在CPython 3.6中，增加了一个小int //的快速路径，所以//现在也比>>更适合小int。

对于Python 3.x整数，比位移位快两倍吗？

1条答案

整数除法

相关问题

热门标签

最新问答