为什么一些浮点数小于整数的比较速度比其他的慢四倍?

290

比较浮点数和整数时,一些值的比较需要比其他同样数量级的值更长的时间来评估。

例如:

>>> 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似乎在处理某些值对时比处理其他值对更具挑战性。


上面的时间是来自Python 3.4 - 在我的Linux电脑上运行2.7时,时间也有类似的差异(在3和4倍多慢之间)。 - Alex Riley
2
谢谢你的有趣文章。我很好奇是什么启发了这个问题 - 你是随机比较时间还是背后有一个故事? - Veedrac
4
@Veedrac:谢谢。这并没有什么故事:我不经意地想知道浮点数和整数比较的速度有多快,计时了一些值,注意到一些小差异。然后我意识到我完全不知道Python如何精确比较浮点数和大整数。我花了一些时间试图理解源代码,并了解了最坏情况是什么。 - Alex Riley
我简直不敢相信你“心不在焉地”找到那些接近2的49次方的值。 - user1196549
3
@YvesDaoust:不是那些特定的值,没有(那将是难以置信的运气!)。我尝试了各种值对,并注意到时间上的较小差异(例如,将小幅度的浮点数与类似的整数进行比较,而不是非常大的整数)。我只有在查看源代码以了解比较方式后才了解到2^49的情况。我选择了问题中的这些值,因为它们以最引人注目的方式呈现了这个主题。 - Alex Riley
显示剩余3条评论
2个回答

363

Python中的float对象源码中有一条注释承认:

比较几乎是一场噩梦

尤其是在将float与整数进行比较时,这一点尤为明显。因为与浮点数不同,Python中的整数可以任意大且始终精确。将整数强制转换为浮点数可能会导致精度丢失并使比较不准确。试图将浮点数转换为整数也行不通,因为任何小数部分都将被丢失。

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

当将浮点数v与整数/长整数w进行比较时,最坏的情况是:

  • vw具有相同的符号(都是正数或负数),
  • 整数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函数处理两个值vw之间的比较。

下面是函数执行的逐步说明。Python源代码中的注释在理解函数操作时非常有用,因此我已将相关注释保留在其中。我还在答案底部总结了这些检查的列表。

主要思想是将Python对象vw映射到两个适当的C双精度浮点数ij,然后可以轻松地进行比较以得出正确的结果。 Python 2和Python 3都使用相同的思想来实现此目的(前者只是单独处理intlong类型)。

首先要做的是检查v是否确实是Python浮点数,并将其映射到C双精度i。接下来,函数会检查w是否也是浮点数,并将其映射到C双精度j。这是函数的最佳情况,因为所有其他检查都可以跳过。函数还会检查v是否为infnan
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整数。如果是这种情况,则最简单的测试是提取vw的符号(如果为零,则返回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;
        }
    }   

如果这个检查失败了,那么vw的符号是相同的。
接下来的检查计算整数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双精度“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];
    }

现在该函数查看浮点数的指数。回想一下,一个浮点数可以写成(忽略符号)significand * 2exponent,significand代表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|,因为significand * 2exponent小于2nbits
如果这两个检查失败,函数会查看指数是否大于w的位数。这表明significand * 2exponent大于2nbits,因此v > |w|
    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

如果这个检查没有成功,我们知道浮点数 v 的指数与整数 w 中的位数相同。现在唯一比较这两个值的方法是从 vw 构建两个新的 Python 整数。思路是丢弃 v 的小数部分,将整数部分加倍,然后再加一。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 双精度。现在,如果 w 也是浮点数:
  • 检查 w 是否为 naninf。如果是,则根据 w 的类型分别处理此特殊情况。
  • 如果不是,则直接通过它们作为 C 双精度的表示来比较 vw
如果 w 是整数:
  • 提取 vw 的符号。如果它们不同,则我们知道 vw 不同,并且哪个值更大。

  • (符号相同。) 检查 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 加倍。比较这两个新整数以获取结果。


6
Python开发者干得好 - 大多数语言实现都会简单地通过说浮点数/整数比较不精确来掩盖这个问题。 - user253751
1
@user253751 我会用不同的措辞来表达:大多数语言根本不支持直接比较浮点数和整数。相反,其中一个值必须进行转换,以执行浮点数/浮点数或整数/整数的转换。特定的语言可能在未指定转换时进行隐式转换,所以看起来像是浮点数/整数的比较,但实际上在这些语言中并非如此。 - undefined

4
使用带有任意精度浮点数和整数的gmpy2,可以实现更加均衡的比较性能。
~ $ ptipython
Python 3.5.1 |Anaconda 4.0.0 (64-bit)| (default, Dec  7 2015, 11:16:01) 
Type "copyright", "credits" or "license" for more information.

IPython 4.1.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: import gmpy2

In [2]: from gmpy2 import mpfr

In [3]: from gmpy2 import mpz

In [4]: gmpy2.get_context().precision=200

In [5]: i1=562949953421000

In [6]: i2=562949953422000

In [7]: f=562949953420000.7

In [8]: i11=mpz('562949953421000')

In [9]: i12=mpz('562949953422000')

In [10]: f1=mpfr('562949953420000.7')

In [11]: f<i1
Out[11]: True

In [12]: f<i2
Out[12]: True

In [13]: f1<i11
Out[13]: True

In [14]: f1<i12
Out[14]: True

In [15]: %timeit f<i1
The slowest run took 10.15 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 441 ns per loop

In [16]: %timeit f<i2
The slowest run took 12.55 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop

In [17]: %timeit f1<i11
The slowest run took 32.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 269 ns per loop

In [18]: %timeit f1<i12
The slowest run took 36.81 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 231 ns per loop

In [19]: %timeit f<i11
The slowest run took 78.26 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 156 ns per loop

In [20]: %timeit f<i12
The slowest run took 21.24 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 194 ns per loop

In [21]: %timeit f1<i1
The slowest run took 37.61 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 275 ns per loop

In [22]: %timeit f1<i2
The slowest run took 39.03 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 259 ns per loop

1
我还没有使用过这个库,但它看起来可能非常有用。谢谢! - Alex Riley
它被sympy和mpmath使用。 - denfromufa
CPython在标准库中也有“decimal”。 - denfromufa

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接