为什么有些float

内容 隐藏
问题:为什么有些float 将浮点数与整数进行比较时,某些值对的评估时间要比其他类似幅度的值花费更长的时间。 例如: >>> import timeit >>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times 0.5387085462592742 但是,如果将float或整数变小或变大一定数量,则比较会更快地运行: >>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000 0.1481498428446173 >>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1 0.1459577925548956 更改比较运算符(例如使用==或>代替)不会以任何明显的方式影响时间。 这不只是涉及到大小,因为采摘较大或较小的值会导致比较快,所以我怀疑它已经降到了一些不幸的方式位排队。 显然,对于大多数用例而言,比较这些值已足够快。我只是对为什么Python似乎在某些价值观上比在其他价值观上挣扎更多感到好奇。 点击查看英文原文 When comparing floats to integers, some pairs of values take much longer to be evaluated than other values of a similar magnitude. For example: >>> import timeit >>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times 0.5387085462592742 But if the float or integer is made smaller or larger by a certain amount, the comparison runs much more quickly: >>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000 0.1481498428446173 >>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1 0.1459577925548956 Changing the comparison operator (e.g. using == or > instead) does not affect the times in any noticeable way. This is not solely related to magnitude because picking larger or smaller values can result in faster comparisons, so I suspect it is down to some unfortunate way the bits line up. Clearly, comparing these values is more than fast enough for most use cases. I am simply curious as to why Python seems to struggle more with some pairs of values than with others. 回答 0 浮点对象的Python源代码中的注释确认: 比较几乎是一场噩梦 在将浮点数与整数进行比较时尤其如此,因为与浮点数不同,Python中的整数可以任意大,并且总是精确的。尝试将整数强制转换为浮点数可能会失去精度,并使比较不准确。尝试将浮点数转换为整数也不会起作用,因为任何小数部分都会丢失。 为了解决这个问题,Python执行了一系列检查,如果其中一项检查成功,则返回结果。它比较两个值的符号,然后比较整数是否“太大”而不能成为浮点数,然后将浮点的指数与整数长度进行比较。如果所有这些检查均失败,则有必要构造两个新的Python对象进行比较以获得结果。 将浮点数v与整数/长整数进行比较时w,最坏的情况是: v并且w具有相同的符号(正号或负号), 该整数的w位数很少,可以保存为该size_t类型(通常为32或64位), 整数w至少有49位, float的指数与中的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双打,i并且j,然后可以很容易地比较以得到正确的结果。Python 2和Python 3都使用相同的想法进行操作(前者只是分别处理int和long键入)。 首先要做的是检查v是否绝对是Python float并将其映射到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翻倍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]; } 现在,该函数查看浮点数的指数。回想一下,可以将浮点数写为有效位数* 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(因此,其大小小于任何整数)。或者,如果指数小于in的位数,w则v < |w|由于有效* 2 指数小于2 nbits,我们可以得到。 如果这两项检查均未通过,该函数将查看该指数是否大于中的位数w。这表明有效数* 2 指数大于2 nbit,因此v > |w|: if ((size_t)exponent > nbits) { i = 2.0; j = 1.0; goto Compare; } 如果此检查未成功,我们将知道float的指数v与整数中的位数相同w。 现在可以比较两个值的唯一方法是从v和构造两个新的Python整数w。这个想法是丢弃的小数部分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值翻倍。 如果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。比较这两个新的整数以获得结果。 点击查看英文原文 A comment in the Python source code for float objects acknowledges that: Comparison is pretty much a nightmare This is especially true when comparing a float to an integer, because, unlike floats, integers in Python can be arbitrarily large and are always exact. Trying to cast the integer to a float might lose precision and make the comparison inaccurate. Trying to cast the float to an integer is not going to work either because any fractional part will be lost. To get around this problem, Python performs a series of checks, returning the result if one of the checks succeeds. It compares the signs of the two values, then whether the integer is “too big” to be a float, then compares the exponent of the float to the length of the integer. If all of these checks fail, it is necessary to construct two new Python objects to compare in order to obtain the result. When comparing a float v to an integer/long w, the worst case is that: v and w have the same sign (both positive or both negative), the integer w has few enough bits that it can be held in the size_t type (typically 32 or 64 bits), the integer w has at least 49 bits, the exponent of the float v is the same as the number of bits in w. And this is exactly what we have for the values in the question: >>> import math >>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair (0.9999999999976706, 49) >>> (562949953421000).bit_length() 49 We see that 49 is both the exponent of the float and the number of bits in the integer. Both numbers are positive and so the four criteria above are met. Choosing one of the values to be larger (or smaller) can change the number of bits of the integer, or the value of the exponent, and so Python is able to determine the result of the comparison without performing the expensive final check. This is specific to the CPython implementation of the language. The comparison in more detail The float_richcompare function handles the comparison between two values v and w. Below is a step-by-step description of the checks that the function performs. The comments in the Python source are actually very helpful when trying to understand what the function does, so I’ve left them in where relevant. I’ve also summarised these checks in a list at the foot of the answer. The main idea is to map the Python objects v and w to two appropriate C doubles, i and j, which can then be easily compared to give the correct result. Both Python 2 and Python 3 use the same ideas to do this (the former just handles int and long types separately). The first thing to do is check that v is definitely a Python float and map it to a C double i. Next the function looks at whether w is also a float and maps it to a C double j. This is the best case scenario for the function as all the other checks can be skipped. The function also checks to see whether v is inf or 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; } Now we know that if w failed these checks, it is not a Python float. Now the function checks if it’s a Python integer. If this is the case, the easiest test is to extract the sign of v and the sign of w (return 0 if zero, -1 if negative, 1 if positive). If the signs are different, this is all the information needed to return the result of the comparison: 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; } } If this check failed, then v and w have the same sign. The next check counts the number of bits in the integer w. If it has too many bits then it can’t possibly be held as a float and so must be larger in magnitude than the 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; } On the other hand, if the integer w has 48 or fewer bits, it can safely turned in a C double j and compared: if (nbits <= 48) { j = PyLong_AsDouble(w); /* It's impossible that <= 48 bits overflowed. */ assert(j != -1.0 || ! PyErr_Occurred()); goto Compare; } From this point onwards, we know that w has 49 or more bits. It will be convenient to treat w as a positive integer, so change the sign and the comparison operator as necessary: if (nbits <= 48) { /* "Multiply both sides" by -1; this also swaps the * comparator. */ i = -i; op = _Py_SwappedOp[op]; } Now the function looks at the exponent of the float. Recall that a float can be written (ignoring sign) as significand * 2exponent and that the significand represents a number between 0.5 and 1: (void) frexp(i, &exponent); if (exponent < 0 || (size_t)exponent < nbits) { i = 1.0; j = 2.0; goto Compare; } This checks two things. If the exponent is less than 0 then the float is smaller than 1 (and so smaller in magnitude than any integer). Or, if the exponent is less than the number of bits in w then we have that v < |w| since significand * 2exponent is less than 2nbits. Failing these two checks, the function looks to see whether the exponent is greater than the number of bit in w. This shows that significand * 2exponent is greater than 2nbits and so v > |w|: if ((size_t)exponent > nbits) { i = 2.0; j = 1.0; goto Compare; } If this check did not succeed we know that the exponent of the float v is the same as the number of bits in the integer w. The only way that the two values can be compared now is to construct two new Python integers from v and w. The idea is to discard the fractional part of v, double the integer part, and then add one. w is also doubled and these two new Python objects can be compared to give the correct return value. Using an example with small values, 4.65 < 4 would be determined by the comparison (2*4)+1 == 9 < 8 == (2*4) (returning 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 } } For brevity I’ve left out the additional error-checking and garbage-tracking Python has to do when it creates these new objects. Needless to say, this adds additional overhead and explains why the values highlighted in the question are significantly slower to compare than others. Here is a summary of the checks that are performed by the comparison function. Let v be a float and cast it as a C double. Now, if w is also a float: Check whether w is nan or inf. If so, handle this special case separately depending on the type of w. If not, compare v and w directly by their representations as C doubles. If w is an integer: Extract the signs of v and w. If they are different then we know v and w are different and which is the greater value. (The signs are the same.) Check whether w has too many bits to be a float (more than size_t). If so, w has greater magnitude than v. Check if w has 48 or fewer bits. If so, it can be safely cast to a C double without losing its precision and compared with v. (w has more than 48 bits. We will now treat w as a positive integer having changed the compare op as appropriate.) Consider the exponent of the float v. If the exponent is negative, then v is less than 1 and therefore less than any positive integer. Else, if the exponent is less than the number of bits in w then it must be less than w. If the exponent of v is greater than the number of bits in w then v is greater than w. (The exponent is the same as the number of bits in w.) The final check. Split v into its integer and fractional parts. Double the integer part and add 1 to compensate for the fractional part. Now double the integer w. Compare these two new integers instead to get the result. 回答 1 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 点击查看英文原文 Using gmpy2 with arbitrary precision floats and integers it is possible to get more uniform comparison performance: ~ $ 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

问题:为什么有些float

将浮点数与整数进行比较时,某些值对的评估时间要比其他类似幅度的值花费更长的时间。

例如:

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

但是,如果将float或整数变小或变大一定数量,则比较会更快地运行:

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

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

这不只是涉及到大小,因为采摘较大或较小的值会导致比较快,所以我怀疑它已经降到了一些不幸的方式位排队。

显然,对于大多数用例而言,比较这些值已足够快。我只是对为什么Python似乎在某些价值观上比在其他价值观上挣扎更多感到好奇。

When comparing floats to integers, some pairs of values take much longer to be evaluated than other values of a similar magnitude.

For example:

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

But if the float or integer is made smaller or larger by a certain amount, the comparison runs much more quickly:

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

Changing the comparison operator (e.g. using == or > instead) does not affect the times in any noticeable way.

This is not solely related to magnitude because picking larger or smaller values can result in faster comparisons, so I suspect it is down to some unfortunate way the bits line up.

Clearly, comparing these values is more than fast enough for most use cases. I am simply curious as to why Python seems to struggle more with some pairs of values than with others.


回答 0

浮点对象的Python源代码中的注释确认:

比较几乎是一场噩梦

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

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

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

  • v并且w具有相同的符号(正号或负号),
  • 该整数的w位数很少,可以保存为该size_t类型(通常为32或64位),
  • 整数w至少有49位,
  • float的指数与中的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对象vw两个相应的C双打,i并且j,然后可以很容易地比较以得到正确的结果。Python 2和Python 3都使用相同的想法进行操作(前者只是分别处理intlong键入)。

首先要做的是检查v是否绝对是Python float并将其映射到C double i。接下来,该函数查看是否w也是float并将其映射到C double j。这是该功能的最佳情况,因为可以跳过所有其他检查。该功能还检查是否vinfnan

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和的符号w0如果为零,-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];
    }

现在,该函数查看浮点数的指数。回想一下,可以将浮点数写为有效位数* 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(因此,其大小小于任何整数)。或者,如果指数小于in的位数,wv < |w|由于有效* 2 指数小于2 nbits,我们可以得到

如果这两项检查均未通过,该函数将查看该指数是否大于中的位数w。这表明有效数* 2 指数大于2 nbit,因此v > |w|

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

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

现在可以比较两个值的唯一方法是从v和构造两个新的Python整数w。这个想法是丢弃的小数部分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也是浮点数:

  • 检查wnan还是inf。如果是这样,请根据的类型分别处理此特殊情况w

  • 如果不是,则比较vw直接按其表示形式将C值翻倍。

如果w为整数:

  • 提取的迹象vw。如果它们不同,那么我们知道v并且w不同,那是更大的价值。

  • 符号相同。)检查是否w有太多位不能浮空(大于size_t)。如果是这样,w则其幅度大于v

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

  • w具有超过48位。我们现在将w其视作已适当更改比较操作的正整数。

  • 考虑浮点数的指数v。如果指数为负,则v小于1且因此小于任何正整数。否则,如果指数小于的位数,w则它必须小于w

  • 如果的指数v大于中的位数​​,wv大于w

  • 指数与中的位数相同w

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

A comment in the Python source code for float objects acknowledges that:

Comparison is pretty much a nightmare

This is especially true when comparing a float to an integer, because, unlike floats, integers in Python can be arbitrarily large and are always exact. Trying to cast the integer to a float might lose precision and make the comparison inaccurate. Trying to cast the float to an integer is not going to work either because any fractional part will be lost.

To get around this problem, Python performs a series of checks, returning the result if one of the checks succeeds. It compares the signs of the two values, then whether the integer is “too big” to be a float, then compares the exponent of the float to the length of the integer. If all of these checks fail, it is necessary to construct two new Python objects to compare in order to obtain the result.

When comparing a float v to an integer/long w, the worst case is that:

  • v and w have the same sign (both positive or both negative),
  • the integer w has few enough bits that it can be held in the size_t type (typically 32 or 64 bits),
  • the integer w has at least 49 bits,
  • the exponent of the float v is the same as the number of bits in w.

And this is exactly what we have for the values in the question:

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

We see that 49 is both the exponent of the float and the number of bits in the integer. Both numbers are positive and so the four criteria above are met.

Choosing one of the values to be larger (or smaller) can change the number of bits of the integer, or the value of the exponent, and so Python is able to determine the result of the comparison without performing the expensive final check.

This is specific to the CPython implementation of the language.


The comparison in more detail

The float_richcompare function handles the comparison between two values v and w.

Below is a step-by-step description of the checks that the function performs. The comments in the Python source are actually very helpful when trying to understand what the function does, so I’ve left them in where relevant. I’ve also summarised these checks in a list at the foot of the answer.

The main idea is to map the Python objects v and w to two appropriate C doubles, i and j, which can then be easily compared to give the correct result. Both Python 2 and Python 3 use the same ideas to do this (the former just handles int and long types separately).

The first thing to do is check that v is definitely a Python float and map it to a C double i. Next the function looks at whether w is also a float and maps it to a C double j. This is the best case scenario for the function as all the other checks can be skipped. The function also checks to see whether v is inf or 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;
    }

Now we know that if w failed these checks, it is not a Python float. Now the function checks if it’s a Python integer. If this is the case, the easiest test is to extract the sign of v and the sign of w (return 0 if zero, -1 if negative, 1 if positive). If the signs are different, this is all the information needed to return the result of the comparison:

    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;
        }
    }   

If this check failed, then v and w have the same sign.

The next check counts the number of bits in the integer w. If it has too many bits then it can’t possibly be held as a float and so must be larger in magnitude than the 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;
    }

On the other hand, if the integer w has 48 or fewer bits, it can safely turned in a C double j and compared:

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

From this point onwards, we know that w has 49 or more bits. It will be convenient to treat w as a positive integer, so change the sign and the comparison operator as necessary:

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

Now the function looks at the exponent of the float. Recall that a float can be written (ignoring sign) as significand * 2exponent and that the significand represents a number between 0.5 and 1:

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

This checks two things. If the exponent is less than 0 then the float is smaller than 1 (and so smaller in magnitude than any integer). Or, if the exponent is less than the number of bits in w then we have that v < |w| since significand * 2exponent is less than 2nbits.

Failing these two checks, the function looks to see whether the exponent is greater than the number of bit in w. This shows that significand * 2exponent is greater than 2nbits and so v > |w|:

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

If this check did not succeed we know that the exponent of the float v is the same as the number of bits in the integer w.

The only way that the two values can be compared now is to construct two new Python integers from v and w. The idea is to discard the fractional part of v, double the integer part, and then add one. w is also doubled and these two new Python objects can be compared to give the correct return value. Using an example with small values, 4.65 < 4 would be determined by the comparison (2*4)+1 == 9 < 8 == (2*4) (returning 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
    }
}

For brevity I’ve left out the additional error-checking and garbage-tracking Python has to do when it creates these new objects. Needless to say, this adds additional overhead and explains why the values highlighted in the question are significantly slower to compare than others.


Here is a summary of the checks that are performed by the comparison function.

Let v be a float and cast it as a C double. Now, if w is also a float:

  • Check whether w is nan or inf. If so, handle this special case separately depending on the type of w.

  • If not, compare v and w directly by their representations as C doubles.

If w is an integer:

  • Extract the signs of v and w. If they are different then we know v and w are different and which is the greater value.

  • (The signs are the same.) Check whether w has too many bits to be a float (more than size_t). If so, w has greater magnitude than v.

  • Check if w has 48 or fewer bits. If so, it can be safely cast to a C double without losing its precision and compared with v.

  • (w has more than 48 bits. We will now treat w as a positive integer having changed the compare op as appropriate.)

  • Consider the exponent of the float v. If the exponent is negative, then v is less than 1 and therefore less than any positive integer. Else, if the exponent is less than the number of bits in w then it must be less than w.

  • If the exponent of v is greater than the number of bits in w then v is greater than w.

  • (The exponent is the same as the number of bits in w.)

  • The final check. Split v into its integer and fractional parts. Double the integer part and add 1 to compensate for the fractional part. Now double the integer w. Compare these two new integers instead to get the result.


回答 1

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

Using gmpy2 with arbitrary precision floats and integers it is possible to get more uniform comparison performance:

~ $ 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