在将浮点数与整数进行比较时,某些值对的评估时间比其他类似大小的值要长得多。
例如:
>>> 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
更改比较运算符(例如使用==or>代替)不会以任何明显的方式影响时间。
==
>
这 不仅仅 与幅度有关,因为选择更大或更小的值可以导致更快的比较,所以我怀疑这归结为位排列的一些不幸方式。
显然,比较这些值对于大多数用例来说已经足够快了。我只是很好奇为什么 Python 似乎在某些值对上比在其他值上更挣扎。
浮点对象的 Python 源代码中的注释承认:
比较几乎是一场噩梦
在将浮点数与整数进行比较时尤其如此,因为与浮点数不同,Python 中的整数可以任意大并且总是精确的。尝试将整数转换为浮点数可能会丢失精度并使比较不准确。尝试将浮点数转换为整数也不行,因为任何小数部分都会丢失。
为了解决这个问题,Python 执行了一系列检查,如果其中一个检查成功,则返回结果。它比较两个值的符号,然后整数是否“太大”而不能成为浮点数,然后将浮点数的指数与整数的长度进行比较。如果所有这些检查都失败,则需要构造两个新的 Python 对象进行比较以获得结果。
将 floatv与 integer/long进行比较时w,最坏的情况是:
v
w
size_t
这正是我们对问题中的值所拥有的:
>>> 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
float_richcompare
v``w
以下是该函数执行的检查的分步说明。Python 源代码中的注释在试图理解函数的作用时实际上非常有帮助,因此我将它们留在了相关的地方。我还在答案底部的列表中总结了这些检查。
主要思想是将 Python 对象映射v到w两个适当的 C 双精度i和j,然后可以很容易地比较它们以给出正确的结果。Python 2 和 Python 3 都使用相同的想法来做到这一点(前者只是分别处理int和long类型)。
i
j
int
long
首先要做的是检查这v绝对是一个 Python 浮点数并将其映射到一个 C 双精度数i。接下来,该函数查看是否w也是一个浮点数并将其映射到 C 中的 double j。这是该功能的最佳情况,因为可以跳过所有其他检查。该函数还检查是否v是inf或nan:
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如果为正则返回)。如果符号不同,这就是返回比较结果所需的所有信息:
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(因此在幅度上小于任何整数)。或者,如果指数小于位数,w那么我们就有了,v < |w|因为有效位 * 2指数小于 2 nbits。
v < |w|
如果这两项检查失败,函数会查看指数是否大于 中的位数w。这表明有效数 * 2指数大于 2 nbits,因此v > |w|:
v > |w|
if ((size_t)exponent > nbits) { i = 2.0; j = 1.0; goto Compare; }
如果此检查不成功,我们知道浮点数的指数v与整数中的位数相同w。
现在可以比较这两个值的唯一方法是从v和构造两个新的 Python 整数w。这个想法是丢弃 的小数部分v,将整数部分加倍,然后加一。w也加倍,这两个新的 Python 对象可以进行比较以给出正确的返回值。使用具有小值的示例,4.65 < 4将由比较确定(2*4)+1 == 9 < 8 == (2*4)(返回 false)。
4.65 < 4
(2*4)+1 == 9 < 8 == (2*4)
{ 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 双精度。现在, ifw也是一个浮点数:
检查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视作更改比较操作的正整数。)
考虑 float 的指数v。如果指数为负,则v小于1因此小于任何正整数。否则,如果指数小于 中的位数,w则它必须小于w。
如果 的指数v大于 中的位数,w则v大于w。
( 指数与 中的位数相同w。)
最后的检查。分成v整数部分和小数部分。将整数部分加倍并加 1 以补偿小数部分。现在将整数加倍w。比较这两个新整数以获得结果。