为什么某些 float < integer 比较比其他比较慢四倍?

2024-05-27

将浮点数与整数进行比较时,某些值对的计算时间比类似大小的其他值要长得多。

例如:

>>> 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 >相反)不会以任何明显的方式影响时间。

这不是solely与幅度相关,因为选择更大或更小的值可以导致更快的比较,所以我怀疑这归因于一些不幸的位排列方式。

显然,对于大多数用例来说,比较这些值的速度已经足够快了。我只是好奇为什么 Python 似乎在处理某些值对时比处理其他值时更困难。


Python 源代码中关于 float 对象的注释承认:

比较几乎是一场噩梦 https://hg.python.org/cpython/file/ea33b61cac74/Objects/floatobject.c#l285

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

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

比较浮点数时v为整数/长整型w,最坏的情况是:

  • v and w具有相同的符号(均为正或均为负),
  • 整数w有足够少的位可以保存在size_t https://stackoverflow.com/a/2550799/3923281类型(通常为 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 实现的。


更详细的比较

The float_richcompare https://hg.python.org/cpython/file/ea33b61cac74/Objects/floatobject.c#l301函数处理两个值之间的比较v and w.

以下是该函数执行的检查的分步说明。当尝试理解函数的作用时,Python 源代码中的注释实际上非常有帮助,因此我将它们保留在相关的位置。我还在答案底部的列表中总结了这些检查。

主要思想是映射Python对象v and w到两个适当的 C 双打,i and j,然后可以轻松比较以给出正确的结果。 Python 2 和 Python 3 都使用相同的想法来做到这一点(前者只处理int and long分别类型)。

首先要做的是检查v绝对是一个 Python float 并将其映射到一个 C doublei。接下来该函数查看是否w也是一个 float 并将其映射到 C doublej。这是该函数的最佳情况,因为可以跳过所有其他检查。该函数还检查是否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;
    }

现在我们知道如果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 and 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 doublej并比较:

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

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

如果此检查没有成功,我们知道浮点数的指数v与整数的位数相同w.

现在比较这两个值的唯一方法是构造两个新的 Python 整数v and w。这个想法是丢弃小数部分v,将整数部分加倍,然后加一。w也加倍,可以比较这两个新的 Python 对象以给出正确的返回值。使用较小值的示例,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 在创建这些新对象时必须执行的额外错误检查和垃圾跟踪。不用说,这会增加额外的开销,并解释了为什么问题中突出显示的值的比较速度明显慢于其他值。


以下是比较函数执行的检查的摘要。

Let v是一个 float 并将其转换为 C double。现在,如果w也是一个浮点数:

  • 检查是否w is nan or inf。如果是的话,根据类型分别处理这种特殊情况w.

  • 如果没有,比较一下v and w直接通过它们的表示作为 C 加倍。

If w是一个整数:

  • 提取符号v and w。如果它们不同那么我们就知道v and w不同,哪个价值更大。

  • (迹象是一样的。) 检查是否w有太多位无法成为浮点数(超过size_t)。如果是这样,w幅度大于v.

  • 检查是否w具有 48 位或更少。如果是这样,它可以安全地转换为 C double,而不会损失其精度,并与v.

  • (w超过 48 位。我们现在将治疗w作为一个正整数,适当地改变了比较操作。)

  • 考虑浮点数的指数v。如果指数为负数,则v小于1因此小于任何正整数。否则,如果指数小于中的位数w那么它一定小于w.

  • 如果指数为v大于位数w then v大于w.

  • (指数与位数相同w.)

  • 最后检查。分裂v分为整数部分和小数部分。将整数部分加倍并加 1 以补偿小数部分。现在将整数加倍w。比较这两个新整数即可得到结果。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

为什么某些 float < integer 比较比其他比较慢四倍? 的相关文章

随机推荐

  • Glide:记录每个请求

    考虑下面的代码 Glide with
  • Gluon 移动 iOS 音频播放器

    由于 JavaFx Media 尚未移植到移动平台 任何人都可以帮助我使用本机 iOS APi 来播放声音 mp3 文件 该文件将存储在我的 gluon 项目的 main resources 文件夹中 在 Android 上 我们可以轻松地
  • java中线程之间的通信:如果另一个线程完成则停止一个线程

    仅当另一个线程也在运行时 如何才能使一个线程运行 这意味着 如果我从一个线程中的运行返回 那么我希望另一个线程也停止运行 我的代码看起来像这样 ClientMessageHandler clientMessagehandler new Cl
  • 使用 Python Paramiko 进行端口转发和开放 SFTP

    我已经使用 ssh 在服务器上执行命令 现在我必须对不同的 IP 执行另一个 ssh 同时保持旧的 ssh 处于活动状态 这个新 IP 是端口转发 然后将用于执行 SFTP 我面临的问题是两个 ssh 连接都在同一端口上 因此无法进行第二次
  • 如何获取subprocess.run启动的进程的pid并杀死它

    我使用的是 Windows 10 和 Python 3 7 我运行了以下命令 import subprocess exeFilePath C Users test test exe subprocess run exeFilePath 使用
  • 计算 TCP 重传次数

    我想知道在LINUX中是否有一种方法可以计算一个流中发生的TCP重传的次数 无论是在客户端还是服务器端 好像netstat s解决了我的目的
  • 源生成器:有关引用项目的信息?

    我开始使用 C 源生成器 我想要的是开始一个git describe tags long处理并填充静态GitVersion具有当前标签和哈希码作为属性的类 问题是 我没有关于引用项目的目录的信息 所以我不知道在哪里运行 git 进程 我在其
  • 连接查询或子查询

    开发人员何时使用联接而不是子查询是否有经验规则 或者它们是否相同 第一个原则是 准确地陈述查询 第二个原则是 简单明了地陈述查询 这是你通常做出选择的地方 第三个是 陈述查询 以便它能够有效地处理 如果它是一个具有良好查询处理器的数据库管理
  • Base 64 编码的有效字符范围

    我对以下内容感兴趣 是否有一个字符列表never作为 Base 64 编码字符串的一部分出现 例如 我不确定这种情况是否会发生 如果原始输入实际上有 作为它的一部分 编码会有所不同吗 这是我可以发现的 RFC 4648 http www r
  • 从函数参数构建模板?

    template
  • 通过 VPN 容器路由 Docker 容器流量

    我在我的上安装了几个容器洛克Pro64 运行 openmediavault 的 ARMv8 处理器 rev 2 v8 版本 4 1 27 1 Arrakis 一切都运转良好 我使用的容器包括 Transmission Jellyfin Ra
  • IntelliSense:对象具有与成员函数不兼容的类型限定符

    我有一个名为 Person 的类 class Person string name long score public Person string name long score 0 void setName string name voi
  • ECS 上蓝/绿部署所需的 Cloudformation 脚本

    我正在尝试编写一个云形成模板具有蓝绿部署支持的 AWS ECS 这项蓝绿功能最近由 AWS 在 ECS 中添加 但在云形成模板中找不到任何更新它的参考 他们提供了有关如何通过 UI 而不是通过云形成来完成此操作的文档 我猜想 AWS 可能不
  • 集到子集点云匹配

    我有两个 3d 坐标的点云 一个是另一个的子集 包含更少的点 它们的规模相同 我需要做的是找到两者之间的平移和旋转 我看过点云库 迭代最近点 https en wikipedia org wiki Iterative closest poi
  • 如何防止 Firefox 缓存

    我尝试了很多可能的解决方案 但无法解决问题 这些不起作用 有人可以帮忙吗 我正在使用jsp servlet application 是websphere Portal 6 1 的一个portlet 切勿
  • 在跨平台的 npm 脚本中使用环境变量

    我正在构建一个 package json 并使用 npm run 来运行一些脚本 确切地说 https docs npmjs com misc scripts https docs npmjs com misc scripts 我的脚本需要
  • Kotlin 无法编译库

    There s this http github com theapache64 BugMailer我创建的库是为了通过电子邮件报告异常情况 它适用于 Android Java 项目 但不适用于 Android Kotlin 当我添加库的编
  • 如何对URL进行分类? URL 的特点是什么?如何从 URL 中选择和提取特征

    我刚刚开始研究分类问题 这是一个两类问题 我的训练模型 机器学习 必须决定 预测是允许 URL 还是阻止它 我的问题非常具体 如何对 URL 进行分类 我应该使用普通的文本分析方法吗 URL 的特点是什么 如何从URL中选择和提取特征 我假
  • 使用事件实现观察者模式

    我正在开发一个 Silverlight 应用程序 其中过度使用了观察者模式 在我的实现中 我创建了两个接口IObservable
  • 为什么某些 float < integer 比较比其他比较慢四倍?

    将浮点数与整数进行比较时 某些值对的计算时间比类似大小的其他值要长得多 例如 gt gt gt import timeit gt gt gt timeit timeit 562949953420000 7 lt 56294995342100