为什么有些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的位太少，无法保存在^{}类型中（通常为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实现的。

---

更详细的比较

^{}函数处理两个值v和w之间的比较。

下面是对函数执行的检查的逐步描述。Python源代码中的注释实际上对于理解函数的功能非常有帮助，所以我将它们放在相关的地方。我也在答案下面的列表中总结了这些检查。

其主要思想是将Python对象v和w映射到两个适当的C双精度数i和j，然后可以很容易地进行比较以给出正确的结果。Python 2和Python 3都使用相同的思想（前者只分别处理int和long类型）。

首先要做的是检查v绝对是Python浮点，并将其映射到C doublei。接下来，该函数将查看w是否也是浮点值，并将其映射到C doublej。这是函数的最佳情况，因为可以跳过所有其他检查。函数还检查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，如果为正）。如果符号不同，这是返回比较结果所需的所有信息：

    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位或更多位。会是修道院ent将w视为正整数，因此根据需要更改符号和比较运算符：

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

现在该函数查看浮点的指数。回想一下，浮点数可以写为有效位*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;
    }

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

现在可以比较这两个值的唯一方法是从v和w构造两个新的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 double。现在，如果w也是浮点数：

• 检查w是nan还是inf。如果是，请根据w的类型单独处理此特殊情况。

• 如果不是，则直接将v和w表示为C doubles进行比较。

如果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加倍。比较这两个新的整数得到结果。

Answer 2

对任意精度的浮点和整数使用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