python - 为什么一些 float < integer 比较比其他的慢四倍？

Question

将浮点数与整数进行比较时，某些值对的计算时间比其他类似量级的值要长得多。

例如:

>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742

但是如果浮点数或整数变小或变大一定数量，则比较运行得更快:

>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956

更改比较运算符(例如使用 == 或 > 代替)不会以任何明显的方式影响时间。

这不仅仅与幅度有关，因为选择更大或更小的值可以导致更快的比较，所以我怀疑这归结为某些不幸的位排列方式。

显然，对于大多数用例来说，比较这些值已经足够快了。我只是很好奇为什么 Python 似乎在处理某些值对时比在其他值对上更挣扎。

Answer 1

float 对象的 Python 源代码中的注释承认:

Comparison is pretty much a nightmare

将浮点数与整数进行比较时尤其如此，因为与浮点数不同，Python 中的整数可以任意大并且总是精确的。尝试将整数转换为浮点数可能会失去精度并使比较不准确。尝试将浮点数转换为整数也不会起作用，因为任何小数部分都将丢失。

为了解决这个问题，Python 执行了一系列检查，如果其中一个检查成功则返回结果。它比较两个值的符号，然后整数是否“太大”而不能成为浮点数，然后将浮点数的指数与整数的长度进行比较。如果所有这些检查都失败了，则需要构造两个新的 Python 对象进行比较才能获得结果。

比较浮点数时 v到整数/长 w ，最坏的情况是:

v和 w具有相同的符号(均为正或均为负)，

整数 w几乎没有足够的位可以保存在 size_t 中类型(通常为 32 或 64 位)，

整数 w至少有 49 位，

浮点数的指数 v与w中的位数相同.

这正是我们对问题中的值所拥有的:

>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49

我们看到 49 既是浮点数的指数也是整数中的位数。这两个数字都是正数，因此满足上述四个标准。

选择一个更大(或更小)的值可以改变整数的位数或指数的值，因此 Python 能够确定比较的结果，而无需执行昂贵的最终检查。

这是特定于该语言的 CPython 实现的。

比较详细

float_richcompare 函数处理两个值之间的比较 v和 w .

以下是该函数执行的检查的分步说明。 Python 源代码中的注释在尝试理解该函数的作用时实际上非常有用，因此我将它们留在了相关的地方。我还在答案底部的列表中总结了这些检查。

主要思想是映射 Python 对象 v和 w到两个合适的 C double ， i和 j ，然后可以很容易地进行比较以给出正确的结果。 Python 2 和 Python 3 都使用相同的想法来做到这一点(前者只是分别处理 int 和 long 类型)。

首先要做的是检查 v绝对是一个 Python 浮点数并将其映射到 C double i .接下来函数查看是否 w也是一个浮点数并将其映射到 C double j .这是该函数的最佳情况，因为可以跳过所有其他检查。该函数还检查是否 v是 inf或 nan :

static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
    double i, j;
    int r = 0;
    assert(PyFloat_Check(v));       
    i = PyFloat_AS_DOUBLE(v);       

    if (PyFloat_Check(w))           
        j = PyFloat_AS_DOUBLE(w);   

    else if (!Py_IS_FINITE(i)) {
        if (PyLong_Check(w))
            j = 0.0;
        else
            goto Unimplemented;
    }

现在我们知道如果 w这些检查失败，它不是 Python 浮点数。现在该函数检查它是否是一个 Python 整数。如果是这种情况，最简单的测试是提取 v 的符号。和 w的标志(返回 0 如果为零， -1 如果为负， 1 如果为正)。如果符号不同，这就是返回比较结果所需的全部信息:

    else if (PyLong_Check(w)) {
        int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
        int wsign = _PyLong_Sign(w);
        size_t nbits;
        int exponent;

        if (vsign != wsign) {
            /* Magnitudes are irrelevant -- the signs alone
             * determine the outcome.
             */
            i = (double)vsign;
            j = (double)wsign;
            goto Compare;
        }
    }   

如果此检查失败，则 v和 w有相同的标志。

下一次检查计算整数 w 中的位数.如果它有太多位，那么它不可能被保存为浮点数，因此必须大于浮点数 v :

    nbits = _PyLong_NumBits(w);
    if (nbits == (size_t)-1 && PyErr_Occurred()) {
        /* This long is so large that size_t isn't big enough
         * to hold the # of bits.  Replace with little doubles
         * that give the same outcome -- w is so large that
         * its magnitude must exceed the magnitude of any
         * finite float.
         */
        PyErr_Clear();
        i = (double)vsign;
        assert(wsign != 0);
        j = wsign * 2.0;
        goto Compare;
    }

另一方面，如果整数 w具有 48 位或更少位，它可以安全地转换为 C double j并比较:

    if (nbits <= 48) {
        j = PyLong_AsDouble(w);
        /* It's impossible that <= 48 bits overflowed. */
        assert(j != -1.0 || ! PyErr_Occurred());
        goto Compare;
    }

从这点开始，我们知道 w有 49 位或更多位。治疗会很方便 w作为正整数，因此根据需要更改符号和比较运算符:

    if (nbits <= 48) {
        /* "Multiply both sides" by -1; this also swaps the
         * comparator.
         */
        i = -i;
        op = _Py_SwappedOp[op];
    }

现在该函数查看浮点数的指数。回想一下，浮点数可以写成(忽略符号)为有效数 * 2exponent 并且有效数表示 0.5 和 1 之间的数字:

    (void) frexp(i, &exponent);
    if (exponent < 0 || (size_t)exponent < nbits) {
        i = 1.0;
        j = 2.0;
        goto Compare;
    }

这会检查两件事。如果指数小于 0，则浮点数小于 1(因此幅度小于任何整数)。或者，如果指数小于 w 中的位数那么我们就有了 v < |w|因为有效数 * 2exponent 小于 2nbits。

如果这两项检查失败，该函数将查看指数是否大于 w 中的位数。 .这表明有效数 * 2exponent 大于 2nbits 等 v > |w| :

    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

如果这个检查没有成功，我们就知道浮点数的指数 v与整数 w中的位数相同.

现在可以比较这两个值的唯一方法是从 v 构造两个新的 Python 整数。和 w .这个想法是丢弃 v 的小数部分，将整数部分加倍，然后加一。 w也加倍了，可以比较这两个新的 Python 对象以给出正确的返回值。使用较小值的示例， 4.65 < 4将由比较决定 (2*4)+1 == 9 < 8 == (2*4) (返回假)。

    {
        double fracpart;
        double intpart;
        PyObject *result = NULL;
        PyObject *one = NULL;
        PyObject *vv = NULL;
        PyObject *ww = w;

        // snip

        fracpart = modf(i, &intpart); // split i (the double that v mapped to)
        vv = PyLong_FromDouble(intpart);

        // snip

        if (fracpart != 0.0) {
            /* Shift left, and or a 1 bit into vv
             * to represent the lost fraction.
             */
            PyObject *temp;

            one = PyLong_FromLong(1);

            temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
            ww = temp;

            temp = PyNumber_Lshift(vv, one);
            vv = temp;

            temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
            vv = temp;
        }
        // snip
    }
}

为简洁起见，我省略了 Python 在创建这些新对象时必须执行的额外错误检查和垃圾跟踪。不用说，这会增加额外的开销并解释了为什么问题中突出显示的值比其他值要慢得多。

以下是比较函数执行的检查的摘要。

让 v是一个浮点数并将其转换为 C double。现在，如果 w也是一个浮点数:

检查是否w是 nan或 inf .如果是这样，请根据 w 的类型单独处理此特殊情况.

如果不是，比较v和 w直接通过它们的表示作为 C 加倍。

如 w是一个整数:

提取v的符号和 w .如果它们不同，那么我们知道 v和 w是不同的，哪个是更大的值。

(标志相同。)检查是否w有太多位不能作为浮点数(超过 size_t )。如果是这样，w具有比 v 更大的震级.

检查是否 w有 48 位或更少位。如果是这样，它可以安全地转换为 C double 而不会损失其精度并与 v 进行比较。 .

( w 有超过 48 位。我们现在将 w 视为一个正整数，并适当更改了比较操作。)

考虑浮点数的指数 v .如果指数为负，则 v小于 1因此小于任何正整数。否则，如果指数小于 w 中的位数那么它必须小于 w .

如果指数v大于 w 中的位数然后 v大于 w .

(指数与 w 中的位数相同。)

最后检查。拆分 v分为整数部分和小数部分。将整数部分加倍并加 1 以补偿小数部分。现在将整数加倍 w .比较这两个新整数以获得结果。