Python內(nèi)建類型int源碼學(xué)習(xí)

更新時(shí)間：2022年05月17日 17:10:42 作者：Blanker_711

這篇文章主要為大家介紹了Python內(nèi)建類型int源碼學(xué)習(xí)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

在計(jì)算機(jī)系統(tǒng)中，如果某種類型的變量的存儲(chǔ)空間固定，它能表示的數(shù)值范圍就是有限的。以int為例，在C語(yǔ)言中，該類型變量長(zhǎng)度為32位，能表示的整數(shù)范圍為-2147483648~2147483647。1000000000000顯然是超出范圍的，即發(fā)生了整數(shù)溢出。但是對(duì)于Python中的int，則不會(huì)出現(xiàn)這種情況：

>>> 1000000 * 1000000
1000000000000
>>> 10 ** 100
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

1 int對(duì)象的設(shè)計(jì)

1.1 PyLongObject

int對(duì)象的結(jié)構(gòu)體：

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

digit數(shù)組

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

digit數(shù)組具體用什么整數(shù)類型來實(shí)現(xiàn)，Python提供了兩個(gè)版本，一個(gè)是32位的unit32_t，一個(gè)是16位的unsigned short，可以通過宏定義指定選用的版本。至于為什么這么設(shè)計(jì)，這主要是出于內(nèi)存方面的考量，對(duì)于范圍不大的整數(shù)，用16位整數(shù)表示即可，用32位會(huì)比較浪費(fèi)。

（注：可以看到PYLONG_BITS_IN_DIGIT宏的值為30或15，也就是說Python只使用了30位或15位，這是為什么呢——這是Python出于對(duì)加法進(jìn)位的考量。如果全部32位都用來保存絕對(duì)值，那么為了保證加法不溢出（產(chǎn)生進(jìn)位），需要先強(qiáng)制轉(zhuǎn)化成64位類型后再進(jìn)行計(jì)算。但犧牲最高1位后，加法運(yùn)算便不用擔(dān)心進(jìn)位溢出了。那么，為什么對(duì)32位時(shí)是犧牲最高2位呢？可能是為了和16位整數(shù)方案統(tǒng)一起來：如果選用16位整數(shù)，Python只使用15位；32位就使用30位。）

實(shí)際上，由于PyObject_VAR_HEAD頭部的存在，32位和16位的選擇其實(shí)差別不大：

整數(shù)對(duì)象	基本單位16位	基本單位32位
1	24 + 2 * 1 = 26	24 + 4 * 1 = 28
1000000	24 + 2 * 2 = 28	24 + 4 * 1 = 28
10000000000	24 + 2 * 3 = 30	24 + 4 * 2 = 32

int對(duì)象結(jié)構(gòu)圖示如下：

對(duì)于比較大的整數(shù)，Python將其拆成若干部分，保存在ob_digit數(shù)組中。然而我們注意到在結(jié)構(gòu)體定義中，ob_digit數(shù)組長(zhǎng)度卻固定為1，這是為什么呢？這里資料解釋是：“由于C語(yǔ)言中數(shù)組長(zhǎng)度不是類型信息，我們可以根據(jù)實(shí)際需要為ob_digit數(shù)組分配足夠的內(nèi)存，并將其當(dāng)成長(zhǎng)度為n的數(shù)組操作。這也是C語(yǔ)言中一個(gè)常用的編程技巧。”

但是根據(jù)我對(duì)C語(yǔ)言的理解，數(shù)組是由基址+偏移來確定位置的，初始長(zhǎng)度為1的數(shù)組，后續(xù)如果強(qiáng)行去索引超過這個(gè)長(zhǎng)度的位置，不是會(huì)出問題嗎？不知道是我理解錯(cuò)了還是什么，這里后續(xù)還要進(jìn)一步考證。

1.2 整數(shù)的布局

整數(shù)分為正數(shù)、負(fù)數(shù)和零，這三種不同整數(shù)的存儲(chǔ)方式如下：

將整數(shù)的絕對(duì)值保存在ob_digit數(shù)組中
ob_digit數(shù)組長(zhǎng)度保存在ob_size字段，若整數(shù)為負(fù)，則ob_size為負(fù)數(shù)
整數(shù)零的ob_size為0，ob_digit數(shù)組為空

下面以五個(gè)典型的例子來介紹不同情況下的整數(shù)存儲(chǔ)情況：

對(duì)于整數(shù)0，ob_size = 0，ob_digit為空，無(wú)需分配

對(duì)于整數(shù)10，其絕對(duì)值保存在ob_digit數(shù)組中，數(shù)組長(zhǎng)度為1，ob_size字段為1

對(duì)于整數(shù)-10，其絕對(duì)值保存在ob_digit數(shù)組中，數(shù)組長(zhǎng)度為1，ob_size字段為-1

對(duì)于整數(shù)1073741824（即2^30），由于Python只使用了32位的后30位，所以2^30次方需要兩個(gè)數(shù)組元素來存儲(chǔ)，整數(shù)數(shù)組的長(zhǎng)度為2。絕對(duì)值這樣計(jì)算：

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

對(duì)于整數(shù)-4294967297（即-(2^32 + 1)），同樣需要長(zhǎng)度為2的數(shù)組，但ob_size字段為負(fù)數(shù)。絕對(duì)值這樣計(jì)算：

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

總結(jié)：ob_digit數(shù)組存儲(chǔ)數(shù)據(jù)時(shí)，類似230進(jìn)制計(jì)算（或215進(jìn)制，取決于數(shù)組的類型）

1.3 小整數(shù)靜態(tài)對(duì)象池

問題：通過前面章節(jié)的學(xué)習(xí)，我們知道整數(shù)對(duì)象是不可變對(duì)象，整數(shù)運(yùn)算結(jié)果都是以新對(duì)象返回的：

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

Python這樣的設(shè)計(jì)會(huì)帶來一個(gè)性能缺陷，程序運(yùn)行時(shí)必定會(huì)有大量對(duì)象的創(chuàng)建銷毀，即會(huì)帶來大量的內(nèi)存分配和回收消耗，嚴(yán)重影響性能。例如對(duì)于一個(gè)循環(huán)100次的for循環(huán)，就需要?jiǎng)?chuàng)建100個(gè)int對(duì)象，這顯然是不能接受的。

對(duì)此，Python的解決方法是：預(yù)先將常用的整數(shù)對(duì)象創(chuàng)建好，以后備用，這就是小整數(shù)對(duì)象池。（和float一樣運(yùn)用池技術(shù)，但是稍有不同，這也是由int和float實(shí)際運(yùn)用的差別導(dǎo)致的）

小整數(shù)對(duì)象池相關(guān)源碼：

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

NSMALLPOSINTS宏規(guī)定了對(duì)象池正數(shù)個(gè)數(shù)（包括0），默認(rèn)257個(gè)NSMALLNEGINTS宏規(guī)定了對(duì)象池負(fù)數(shù)個(gè)數(shù)，默認(rèn)為5個(gè)small_ints是一個(gè)整數(shù)對(duì)象數(shù)組，保存預(yù)先創(chuàng)建好的小整數(shù)對(duì)象

以默認(rèn)配置為例，Python啟動(dòng)后靜態(tài)創(chuàng)建一個(gè)包含262個(gè)元素的整數(shù)數(shù)組，并依次初始化-5到-1，0，和1到256這些整數(shù)對(duì)象。小整數(shù)對(duì)象池結(jié)構(gòu)如下：

1.4 示例

示例1：

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

由于1 + 0的計(jì)算結(jié)果為1，在小整數(shù)范圍內(nèi)，Python會(huì)直接從靜態(tài)對(duì)象池中取出整數(shù)1；1 * 1也是同理。名字a和b其實(shí)都跟一個(gè)對(duì)象綁定（有關(guān)名字綁定的內(nèi)容可以看這篇博客：Python源碼學(xué)習(xí)筆記：Python作用域與名字空間），即小整數(shù)對(duì)象池中的整數(shù)1，因此它們的id相同。

示例2：

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

1000 + 0 和1000 * 1的計(jì)算結(jié)果都是1000，但由于1000不在小整數(shù)池范圍內(nèi)，Python會(huì)分別創(chuàng)建對(duì)象并返回，因此c和d綁定的對(duì)象id也就不同了。

注：這里大家如果使用Pycharm來運(yùn)行的話就會(huì)發(fā)現(xiàn)它們的id是一樣的：

這里的原因本質(zhì)上是和字節(jié)碼相關(guān)的，在IDLE中，每個(gè)命令都會(huì)單獨(dú)去編譯，而在Pycharm中是編譯整個(gè)py文件，在同一上下文（這里“同一上下文”其實(shí)比較模糊，筆者水平有限，解釋得也不太好）中的相同值的整數(shù)就是同一個(gè)對(duì)象，可以試著把字節(jié)碼打印出來看一下（有關(guān)字節(jié)碼的內(nèi)容可以看下這篇博客：Python源碼學(xué)習(xí)筆記：Python程序執(zhí)行過程與字節(jié)碼）。

2 大整數(shù)運(yùn)算

問題：在之前我們了解到了整數(shù)對(duì)象的內(nèi)部結(jié)構(gòu)，對(duì)于Python如何應(yīng)對(duì)“整數(shù)溢出”這個(gè)問題有了一個(gè)初步的認(rèn)識(shí)。但是真正的難點(diǎn)在于大整數(shù)數(shù)學(xué)運(yùn)算的實(shí)現(xiàn)。

2.1 整數(shù)運(yùn)算概述

整數(shù)對(duì)象的運(yùn)算由整數(shù)類型對(duì)象中的tp_as_number、tp_as_sequence、tp_as_mapping這三個(gè)字段所決定。整數(shù)類型對(duì)象PyLong_Type源碼如下：（只列出部分字段）

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    
    // ...
    
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    
    // ...
};

整數(shù)對(duì)象僅支持?jǐn)?shù)值型操作long_as_number：

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    (unaryfunc)long_long,       /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    (binaryfunc)long_rshift,    /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

至此，我們明確了整數(shù)對(duì)象支持的全部數(shù)學(xué)運(yùn)算，以及對(duì)應(yīng)的處理函數(shù)：（只列出部分函數(shù)）

數(shù)學(xué)運(yùn)算	處理函數(shù)	示例
加法	long_add	a + b
減法	long_sub	a - b
乘法	long_mul	a * b
取模	long_mod	a % b
除法	long_divmod	a / b
指數(shù)	long_pow	a ** b

整數(shù)對(duì)象、整數(shù)類型對(duì)象以及整數(shù)數(shù)學(xué)運(yùn)算處理函數(shù)之間的關(guān)系：

2.2 大整數(shù)運(yùn)算處理過程

以加法為例，來認(rèn)識(shí)大整數(shù)運(yùn)算的處理過程。

加法處理函數(shù)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) {
                /* x_add received at least one multiple-digit int,
                   and thus z must be a multiple-digit int.
                   That also means z is not an element of
                   small_ints, so negating it in-place is safe. */
                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;
}

主體邏輯如下：

第4行：定義變量z用于臨時(shí)保存計(jì)算結(jié)果
第8~10行：如果兩個(gè)對(duì)象數(shù)組長(zhǎng)度均不超過1，用MEDIUM_VALUE宏將其轉(zhuǎn)化成C整數(shù)進(jìn)行運(yùn)算（這種優(yōu)化也是可以學(xué)習(xí)的）
第13~17行：如果兩個(gè)整數(shù)均為負(fù)數(shù)，調(diào)用x_add計(jì)算兩者絕對(duì)值之和，再將結(jié)果符號(hào)設(shè)置為負(fù)（16行處）
第20行：如果a為負(fù)數(shù)，b為正數(shù)，調(diào)用x_sub計(jì)算b和a的絕對(duì)值之差即為最終結(jié)果
第24行：如果a為正數(shù)，b為負(fù)數(shù)，調(diào)用x_sub計(jì)算a和b的絕對(duì)值之差即為最終結(jié)果
第26行：如果兩個(gè)整數(shù)均為正數(shù)，調(diào)用x_add計(jì)算兩個(gè)絕對(duì)值之和即為最終結(jié)果

因此，long_add函數(shù)實(shí)際上將整數(shù)加法轉(zhuǎn)化成了絕對(duì)值加法x_add和絕對(duì)值減法x_sub，以及MEDIUM_VALUE。絕對(duì)值加法和絕對(duì)值減法不用考慮符號(hào)對(duì)計(jì)算結(jié)果的影響，實(shí)現(xiàn)較為簡(jiǎn)單，這是Python將整數(shù)運(yùn)算轉(zhuǎn)化成絕對(duì)值運(yùn)算的原因。（這里也可以學(xué)習(xí)下）

大整數(shù)運(yùn)算涉及到兩個(gè)數(shù)組之間的加法，整數(shù)數(shù)值越大，整數(shù)對(duì)象底層數(shù)組就越長(zhǎng)，運(yùn)算開銷也會(huì)越大。但是運(yùn)算處理函數(shù)提供了一個(gè)快速通道：如果參與運(yùn)算的整數(shù)對(duì)象底層數(shù)組長(zhǎng)度均不超過1，直接將整數(shù)對(duì)象轉(zhuǎn)化成C整數(shù)類型進(jìn)行運(yùn)算，性能耗損極小。滿足這個(gè)條件的整數(shù)范圍在-1073741823~1073747823之間，足以覆蓋大部分運(yùn)算情況了。

2.絕對(duì)值加法x_add()

下面我們來看一下Python是如何對(duì)數(shù)組進(jìn)行加法運(yùn)算的。x_add()源碼：

/* Add the absolute values of two integers. */

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;

    /* Ensure a is the larger of the two: */
    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數(shù)組長(zhǎng)度比較小，將a、b交換，數(shù)組長(zhǎng)度較大的那個(gè)在前面（感覺做算法題有時(shí)候就需要交換下，方便統(tǒng)一處理）

第16~18行：創(chuàng)建新整數(shù)對(duì)象，用于保存計(jì)算結(jié)果（注意到長(zhǎng)度必須要比a大，因?yàn)榭赡芤M(jìn)位）

第19~23行：遍歷b底層數(shù)組，與a對(duì)應(yīng)部分相機(jī)啊并保存在z中，需要注意到進(jìn)位（可以看到這里是用按位與和右移進(jìn)行計(jì)算的，通過位于算來處理也是很高效的，算法題中也比較常見）

第24~28行：遍歷a底層數(shù)組的剩余部分，與進(jìn)位相加后保存在z中，同樣要注意進(jìn)位運(yùn)算

第29行：將進(jìn)位寫入z底層數(shù)組最高位單元中

第30行：標(biāo)準(zhǔn)化z，去除計(jì)算結(jié)果z底層數(shù)組中前面多余的0

3 其他

大整數(shù)轉(zhuǎn)float溢出

至此，我們對(duì)int和float有了一定的認(rèn)識(shí)，也自然會(huì)有一個(gè)問題：將大整數(shù)int轉(zhuǎn)化為float時(shí)發(fā)生溢出怎么辦？

示例：

>>>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是有長(zhǎng)度限制的，它的大小也是有上限的，因此當(dāng)我們將一個(gè)很大的int轉(zhuǎn)化為float時(shí)，如果超出上限就會(huì)報(bào)錯(cuò)。對(duì)此我們可以使用Decimal來解決：（這里只介紹了使用方式，具體原理大家可以去了解一下）

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

可以看到將i通過Decimal()轉(zhuǎn)化后就不會(huì)報(bào)錯(cuò)了。

以上就是Python內(nèi)建類型int源碼學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于Python內(nèi)建類型int的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

軟件下載

源碼下載

軟件編程

網(wǎng)絡(luò)編程

在線工具

數(shù)據(jù)庫(kù)

CMS

常用工具