为什么有些浮点数<整数比较慢四倍？-Java 学习之路

281

将浮点数与整数进行比较时，某些值对的评估时间比其他类似值的值要长得多 .

例如：

>>> 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似乎更多地使用一些值而不是其他值 .

2 回答

350

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

回复于 2024-04-29T17:49:24+08:00

4
float对象的Python源代码中的注释确认：

比较几乎是一场噩梦

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

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

将float v 与整数/长 w 进行比较时，最糟糕的情况是：
- v 和 w 具有相同的符号（均为正数或均为负数），
- 整数 w 具有足够的位，可以保存在size_t类型中（通常为32或64位），
- 整数 w 至少有49位，
- float v 的指数与 w 中的位数相同 .
这正是我们对问题中的 Value 观的看法：
```
>>> 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 中的位数 . 如果它有太多位，那么它不可能被保持为浮点数，因此必须比float 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的指数 . 回想一下，浮点数可以写成（忽略符号）作为有效数字* 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;
    }
```
如果此检查未成功，我们知道float v 的指数与整数 w 中的位数相同 .

现在可以比较这两个值的唯一方法是从 v 和 w 构造两个新的Python整数 . 想法是丢弃 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 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 . 比较这两个新的整数来获得结果 .
回复于 2024-04-29T17:49:24+08:00

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

2 回答

更详细的比较

相关问题