为什么有些浮点数<整数比较慢四倍？

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源代码中的注释确认:

比较几乎是一场噩梦

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

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

将float v与integer/long 进行比较时w,最糟糕的情况是:

• v并且w具有相同的符号(正面或两面都是负面的),
• 整数的w位数足够少,可以保存在size_t类型中(通常为32位或64位),
• 整数w至少有49位,
• float的指数与vin中的位数相同w.

这正是我们对问题中的价值观的看法:

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

我们看到49既是float的指数又是整数中的位数.这两个数字都是正数,因此符合上述四个标准.

选择其中一个值更大(或更小)可以更改整数的位数或指数的值,因此Python可以在不执行昂贵的最终检查的情况下确定比较结果.

这特定于CPython语言的实现.

比较更详细

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

以下是该功能执行的检查的逐步说明.在尝试理解函数的功能时,Python源代码中的注释实际上非常有用,因此我将它们放在相关的位置.我还在答案的最后列表中总结了这些检查.

其主要思想是映射Python对象v和w两个相应的C双打,i并且j,然后可以很容易地比较以得到正确的结果.Python 2和Python 3都使用相同的想法来做到这一点(前者只是单独处理int和long类型).

要做的第一件事是检查它v是一个Python浮点数并将其映射到C double i.接下来,该函数查看是否w也是一个float并将其映射到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];
    }

现在该函数查看float的指数.回想一下,浮点数可以写成(忽略符号)作为有效数字*2 ^指数,而有效数字表示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|因为有效数*2 ^指数小于2 ^nbits.

如果未通过这两项检查,该函数将查看指数是否大于位数w.这表明有效数*2 ^指数大于2 ^nbits,因此v > |w|:

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

如果此检查未成功,我们知道float的指数v与整数中的位数相同w.

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

    {
        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双重投射.现在,if 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.比较这两个新的整数来获得结果.