文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python内建类型int源码分析

2023-06-30 14:13

关注

今天小编给大家分享一下Python内建类型int源码分析的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

问题:对于C语言,下面这个程序运行后的结果是什么?是1000000000000吗?

#include <stdio.h>int main(int argc, char *argv[]){    int value = 1000000;    print("%d\n", value * value)}

输出如下:

-727379968

在计算机系统中,如果某种类型的变量的存储空间固定,它能表示的数值范围就是有限的。以int为例,在C语言中,该类型变量长度为32位,能表示的整数范围为-2147483648~2147483647。1000000000000显然是超出范围的,即发生了整数溢出。但是对于Python中的int,则不会出现这种情况:

>>> 1000000 * 10000001000000000000>>> 10 ** 10010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

1 int对象的设计

1.1 PyLongObject

int对象的结构体:

typedef struct _longobject PyLongObject;struct _longobject {    PyObject_VAR_HEAD    digit ob_digit[1];};

digit数组

#if PYLONG_BITS_IN_DIGIT == 30typedef uint32_t digit;// ...#elif PYLONG_BITS_IN_DIGIT == 15typedef unsigned short digit;// ...#endif

digit数组具体用什么整数类型来实现,Python提供了两个版本,一个是32位的unit32_t,一个是16位的unsigned short,可以通过宏定义指定选用的版本。至于为什么这么设计,这主要是出于内存方面的考量,对于范围不大的整数,用16位整数表示即可,用32位会比较浪费。

(注:可以看到PYLONG_BITS_IN_DIGIT宏的值为30或15,也就是说Python只使用了30位或15位,这是为什么呢&mdash;&mdash;这是Python出于对加法进位的考量。如果全部32位都用来保存绝对值,那么为了保证加法不溢出(产生进位),需要先强制转化成64位类型后再进行计算。但牺牲最高1位后,加法运算便不用担心进位溢出了。那么,为什么对32位时是牺牲最高2位呢?可能是为了和16位整数方案统一起来:如果选用16位整数,Python只使用15位;32位就使用30位。)

实际上,由于PyObject_VAR_HEAD头部的存在,32位和16位的选择其实差别不大:

整数对象基本单位16位基本单位32位
124 + 2 * 1 = 2624 + 4 * 1 = 28
100000024 + 2 * 2 = 2824 + 4 * 1 = 28
1000000000024 + 2 * 3 = 3024 + 4 * 2 = 32

int对象结构图示如下:

Python内建类型int源码分析


对于比较大的整数,Python将其拆成若干部分,保存在ob_digit数组中。然而我们注意到在结构体定义中,ob_digit数组长度却固定为1,这是为什么呢?这里资料解释是:“由于C语言中数组长度不是类型信息,我们可以根据实际需要为ob_digit数组分配足够的内存,并将其当成长度为n的数组操作。这也是C语言中一个常用的编程技巧。”

但是根据我对C语言的理解,数组是由基址+偏移来确定位置的,初始长度为1的数组,后续如果强行去索引超过这个长度的位置,不是会出问题吗?不知道是我理解错了还是什么,这里后续还要进一步考证。

1.2 整数的布局

整数分为正数、负数和零,这三种不同整数的存储方式如下:

下面以五个典型的例子来介绍不同情况下的整数存储情况:

Python内建类型int源码分析

对于整数0,ob_size = 0,ob_digit为空,无需分配

对于整数10,其绝对值保存在ob_digit数组中,数组长度为1,ob_size字段为1

对于整数-10,其绝对值保存在ob_digit数组中,数组长度为1,ob_size字段为-1

对于整数1073741824(即2^30),由于Python只使用了32位的后30位,所以2^30次方需要两个数组元素来存储,整数数组的长度为2。绝对值这样计算:

2^0 * 0 + 2^30 * 1 = 1073741824

对于整数-4294967297(即-(2^32 + 1)),同样需要长度为2的数组,但ob_size字段为负数。绝对值这样计算:

2^0 * 1 + 2^30 * 4 = 4294967297

总结:ob_digit数组存储数据时,类似230进制计算(或215进制,取决于数组的类型)

1.3 小整数静态对象池

问题:通过前面章节的学习,我们知道整数对象是不可变对象,整数运算结果都是以新对象返回的:

>>> a = 1>>> id(a)1497146464>>> a += 1>>> id(a)1496146496

Python这样的设计会带来一个性能缺陷,程序运行时必定会有大量对象的创建销毁,即会带来大量的内存分配和回收消耗,严重影响性能。例如对于一个循环100次的for循环,就需要创建100个int对象,这显然是不能接受的。

对此,Python的解决方法是:预先将常用的整数对象创建好,以后备用,这就是小整数对象池。(和float一样运用池技术,但是稍有不同,这也是由int和float实际运用的差别导致的)

小整数对象池相关源码:

#ifndef NSMALLPOSINTS#define NSMALLPOSINTS           257#endif#ifndef NSMALLNEGINTS#define NSMALLNEGINTS           5#endifstatic PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

NSMALLPOSINTS宏规定了对象池正数个数(包括0),默认257个NSMALLNEGINTS宏规定了对象池负数个数,默认为5个small_ints是一个整数对象数组,保存预先创建好的小整数对象

以默认配置为例,Python启动后静态创建一个包含262个元素的整数数组,并依次初始化-5到-1,0,和1到256这些整数对象。小整数对象池结构如下:

Python内建类型int源码分析

1.4 示例

示例1:

>>> a = 1 + 0>>> b = 1 * 1>>> id(a), id(b)(1541936120048, 1541936120048)

由于1 + 0的计算结果为1,在小整数范围内,Python会直接从静态对象池中取出整数1;1 * 1也是同理。名字a和b其实都跟一个对象绑定(有关名字绑定的内容可以看这篇博客:Python源码学习笔记:Python作用域与名字空间),即小整数对象池中的整数1,因此它们的id相同。

示例2:

>>> c = 1000 + 0>>> d = 1000 * 1>>> id(c), id(d)(3085872130224, 3085872130256)

1000 + 0 和1000 * 1的计算结果都是1000,但由于1000不在小整数池范围内,Python会分别创建对象并返回,因此c和d绑定的对象id也就不同了。

注:这里大家如果使用Pycharm来运行的话就会发现它们的id是一样的:

Python内建类型int源码分析

Python内建类型int源码分析

这里的原因本质上是和字节码相关的,在IDLE中,每个命令都会单独去编译,而在Pycharm中是编译整个py文件,在同一上下文。

2 大整数运算

问题:在之前我们了解到了整数对象的内部结构,对于Python如何应对“整数溢出”这个问题有了一个初步的认识。但是真正的难点在于大整数数学运算的实现。

2.1 整数运算概述

整数对象的运算由整数类型对象中的tp_as_number、tp_as_sequence、tp_as_mapping这三个字段所决定。整数类型对象PyLong_Type源码如下:(只列出部分字段)

PyTypeObject PyLong_Type = {    PyVarObject_HEAD_INIT(&PyType_Type, 0)    "int",                                          offsetof(PyLongObject, ob_digit),               sizeof(digit),                                      // ...        &long_as_number,                                0,                                              0,                                                  // ...};

整数对象仅支持数值型操作long_as_number:

static PyNumberMethods long_as_number = {    (binaryfunc)long_add,           (binaryfunc)long_sub,           (binaryfunc)long_mul,           long_mod,                       long_divmod,                    long_pow,                       (unaryfunc)long_neg,            (unaryfunc)long_long,           (unaryfunc)long_abs,            (inquiry)long_bool,             (unaryfunc)long_invert,         long_lshift,                    (binaryfunc)long_rshift,        long_and,                       long_xor,                       long_or,                        long_long,                      0,                              long_float,                     0,                              0,                              0,                              0,                              0,                              0,                              0,                              0,                              0,                              0,                              long_div,                       long_true_divide,               0,                              0,                              long_long,                  };

至此,我们明确了整数对象支持的全部数学运算,以及对应的处理函数:(只列出部分函数)

数学运算处理函数示例
加法long_adda + b
减法long_suba - b
乘法long_mula * b
取模long_moda % b
除法long_divmoda / b
指数long_powa ** b

整数对象、整数类型对象以及整数数学运算处理函数之间的关系:

Python内建类型int源码分析

2.2 大整数运算处理过程

以加法为例,来认识大整数运算的处理过程。

加法处理函数long_add()

1.long_add()源码:
static PyObject *long_add(PyLongObject *a, PyLongObject *b){    PyLongObject *z;    CHECK_BINOP(a, b);    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));    }    if (Py_SIZE(a) < 0) {        if (Py_SIZE(b) < 0) {            z = x_add(a, b);            if (z != NULL) {                                assert(Py_REFCNT(z) == 1);                Py_SIZE(z) = -(Py_SIZE(z));            }        }        else            z = x_sub(b, a);    }    else {        if (Py_SIZE(b) < 0)            z = x_sub(a, b);        else            z = x_add(a, b);    }    return (PyObject *)z;}

主体逻辑如下:

因此,long_add函数实际上将整数加法转化成了绝对值加法x_add和绝对值减法x_sub,以及MEDIUM_VALUE。绝对值加法和绝对值减法不用考虑符号对计算结果的影响,实现较为简单,这是Python将整数运算转化成绝对值运算的原因。(这里也可以学习下)

大整数运算涉及到两个数组之间的加法,整数数值越大,整数对象底层数组就越长,运算开销也会越大。但是运算处理函数提供了一个快速通道:如果参与运算的整数对象底层数组长度均不超过1,直接将整数对象转化成C整数类型进行运算,性能耗损极小。满足这个条件的整数范围在-1073741823~1073747823之间,足以覆盖大部分运算情况了。

2.绝对值加法x_add()

下面我们来看一下Python是如何对数组进行加法运算的。x_add()源码:

static PyLongObject *x_add(PyLongObject *a, PyLongObject *b){    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));    PyLongObject *z;    Py_ssize_t i;    digit carry = 0;        if (size_a < size_b) {        { PyLongObject *temp = a; a = b; b = temp; }        { Py_ssize_t size_temp = size_a;            size_a = size_b;            size_b = size_temp; }    }    z = _PyLong_New(size_a+1);    if (z == NULL)        return NULL;    for (i = 0; i < size_b; ++i) {        carry += a->ob_digit[i] + b->ob_digit[i];        z->ob_digit[i] = carry & PyLong_MASK;        carry >>= PyLong_SHIFT;    }    for (; i < size_a; ++i) {        carry += a->ob_digit[i];        z->ob_digit[i] = carry & PyLong_MASK;        carry >>= PyLong_SHIFT;    }    z->ob_digit[i] = carry;    return long_normalize(z);}

源码分析:

第10~15行:如果a数组长度比较小,将a、b交换,数组长度较大的那个在前面(感觉做算法题有时候就需要交换下,方便统一处理)

第16~18行:创建新整数对象,用于保存计算结果(注意到长度必须要比a大,因为可能要进位)

第19~23行:遍历b底层数组,与a对应部分相机啊并保存在z中,需要注意到进位(可以看到这里是用按位与和右移进行计算的,通过位于算来处理也是很高效的,算法题中也比较常见)

第24~28行:遍历a底层数组的剩余部分,与进位相加后保存在z中,同样要注意进位运算

第29行:将进位写入z底层数组最高位单元中

第30行:标准化z,去除计算结果z底层数组中前面多余的0

3 其他

大整数转float溢出

至此,我们对int和float有了一定的认识,也自然会有一个问题:将大整数int转化为float时发生溢出怎么办?

示例:

>>>i = 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111>>> f = float(i)Traceback (most recent call last):  File "<pyshell#1>", line 1, in <module>    f = float(i)OverflowError: int too large to convert to float

由于float是有长度限制的,它的大小也是有上限的,因此当我们将一个很大的int转化为float时,如果超出上限就会报错。对此我们可以使用Decimal来解决:(这里只介绍了使用方式,具体原理大家可以去了解一下)

>>> from decimal import Decimal>>>d = Decimal(i)>>>f2 = float(d)>>> f2inf

可以看到将i通过Decimal()转化后就不会报错了。

以上就是“Python内建类型int源码分析”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯