Python內(nèi)建類型int源碼學習
“深入認識Python內(nèi)建類型”這部分的內(nèi)容會從源碼角度為大家介紹Python中各種常用的內(nèi)建類型。
問題：對于C語言，下面這個程序運行后的結(jié)果是什么？是1000000000000嗎？
#include <stdio.h>
int main(int argc, char *argv[])
{
int value = 1000000;
print("%d\n", value * value)
}
輸出如下：
-727379968
在計算機系統(tǒng)中，如果某種類型的變量的存儲空間固定，它能表示的數(shù)值范圍就是有限的。以int為例，在C語言中，該類型變量長度為32位，能表示的整數(shù)范圍為-2147483648~2147483647。1000000000000顯然是超出范圍的，即發(fā)生了整數(shù)溢出。但是對于Python中的int，則不會出現(xiàn)這種情況：
>>> 1000000 * 1000000 1000000000000 >>> 10 ** 100 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1 int對象的設(shè)計
1.1 PyLongObject
int對象的結(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ù)類型來實現(xiàn)，Python提供了兩個版本，一個是32位的unit32_t，一個是16位的unsigned short，可以通過宏定義指定選用的版本。至于為什么這么設(shè)計，這主要是出于內(nèi)存方面的考量，對于范圍不大的整數(shù)，用16位整數(shù)表示即可，用32位會比較浪費。
（注：可以看到PYLONG_BITS_IN_DIGIT宏的值為30或15，也就是說Python只使用了30位或15位，這是為什么呢——這是Python出于對加法進位的考量。如果全部32位都用來保存絕對值，那么為了保證加法不溢出（產(chǎn)生進位），需要先強制轉(zhuǎn)化成64位類型后再進行計算。但犧牲最高1位后，加法運算便不用擔心進位溢出了。那么，為什么對32位時是犧牲最高2位呢？可能是為了和16位整數(shù)方案統(tǒng)一起來：如果選用16位整數(shù)，Python只使用15位；32位就使用30位。）
實際上，由于PyObject_VAR_HEAD頭部的存在，32位和16位的選擇其實差別不大：
| 整數(shù)對象 | 基本單位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對象結(jié)構(gòu)圖示如下：
對于比較大的整數(shù)，Python將其拆成若干部分，保存在ob_digit數(shù)組中。然而我們注意到在結(jié)構(gòu)體定義中，ob_digit數(shù)組長度卻固定為1，這是為什么呢？這里資料解釋是：“由于C語言中數(shù)組長度不是類型信息，我們可以根據(jù)實際需要為ob_digit數(shù)組分配足夠的內(nèi)存，并將其當成長度為n的數(shù)組操作。這也是C語言中一個常用的編程技巧。”
但是根據(jù)我對C語言的理解，數(shù)組是由基址+偏移來確定位置的，初始長度為1的數(shù)組，后續(xù)如果強行去索引超過這個長度的位置，不是會出問題嗎？不知道是我理解錯了還是什么，這里后續(xù)還要進一步考證。
1.2 整數(shù)的布局
整數(shù)分為正數(shù)、負數(shù)和零，這三種不同整數(shù)的存儲方式如下：
- 將整數(shù)的絕對值保存在ob_digit數(shù)組中
- ob_digit數(shù)組長度保存在ob_size字段，若整數(shù)為負，則ob_size為負數(shù)
- 整數(shù)零的ob_size為0，ob_digit數(shù)組為空
下面以五個典型的例子來介紹不同情況下的整數(shù)存儲情況：
對于整數(shù)0，ob_size = 0，ob_digit為空，無需分配
對于整數(shù)10，其絕對值保存在ob_digit數(shù)組中，數(shù)組長度為1，ob_size字段為1
對于整數(shù)-10，其絕對值保存在ob_digit數(shù)組中，數(shù)組長度為1，ob_size字段為-1
對于整數(shù)1073741824（即2^30），由于Python只使用了32位的后30位，所以2^30次方需要兩個數(shù)組元素來存儲，整數(shù)數(shù)組的長度為2。絕對值這樣計算：
2^0 * 0 + 2^30 * 1 = 1073741824
對于整數(shù)-4294967297（即-(2^32 + 1)），同樣需要長度為2的數(shù)組，但ob_size字段為負數(shù)。絕對值這樣計算：
2^0 * 1 + 2^30 * 4 = 4294967297
總結(jié)：ob_digit數(shù)組存儲數(shù)據(jù)時，類似230進制計算（或215進制，取決于數(shù)組的類型）
1.3 小整數(shù)靜態(tài)對象池
問題：通過前面章節(jié)的學習，我們知道整數(shù)對象是不可變對象，整數(shù)運算結(jié)果都是以新對象返回的：
>>> a = 1 >>> id(a) 1497146464 >>> a += 1 >>> id(a) 1496146496
Python這樣的設(shè)計會帶來一個性能缺陷，程序運行時必定會有大量對象的創(chuàng)建銷毀，即會帶來大量的內(nèi)存分配和回收消耗，嚴重影響性能。例如對于一個循環(huán)100次的for循環(huán)，就需要創(chuàng)建100個int對象，這顯然是不能接受的。
對此，Python的解決方法是：預先將常用的整數(shù)對象創(chuàng)建好，以后備用，這就是小整數(shù)對象池。（和float一樣運用池技術(shù)，但是稍有不同，這也是由int和float實際運用的差別導致的）
小整數(shù)對象池相關(guān)源碼：
#ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257 #endif #ifndef NSMALLNEGINTS #define NSMALLNEGINTS 5 #endif static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
NSMALLPOSINTS宏規(guī)定了對象池正數(shù)個數(shù)（包括0），默認257個NSMALLNEGINTS宏規(guī)定了對象池負數(shù)個數(shù)，默認為5個small_ints是一個整數(shù)對象數(shù)組，保存預先創(chuàng)建好的小整數(shù)對象
以默認配置為例，Python啟動后靜態(tài)創(chuàng)建一個包含262個元素的整數(shù)數(shù)組，并依次初始化-5到-1，0，和1到256這些整數(shù)對象。小整數(shù)對象池結(jié)構(gòu)如下：
1.4 示例
示例1：
>>> a = 1 + 0 >>> b = 1 * 1 >>> id(a), id(b) (1541936120048, 1541936120048)
由于1 + 0的計算結(jié)果為1，在小整數(shù)范圍內(nèi)，Python會直接從靜態(tài)對象池中取出整數(shù)1；1 * 1也是同理。名字a和b其實都跟一個對象綁定（有關(guān)名字綁定的內(nèi)容可以看這篇博客：Python源碼學習筆記：Python作用域與名字空間），即小整數(shù)對象池中的整數(shù)1，因此它們的id相同。
示例2：
>>> c = 1000 + 0 >>> d = 1000 * 1 >>> id(c), id(d) (3085872130224, 3085872130256)
1000 + 0 和1000 * 1的計算結(jié)果都是1000，但由于1000不在小整數(shù)池范圍內(nèi)，Python會分別創(chuàng)建對象并返回，因此c和d綁定的對象id也就不同了。
注：這里大家如果使用Pycharm來運行的話就會發(fā)現(xiàn)它們的id是一樣的：
這里的原因本質(zhì)上是和字節(jié)碼相關(guān)的，在IDLE中，每個命令都會單獨去編譯，而在Pycharm中是編譯整個py文件，在同一上下文（這里“同一上下文”其實比較模糊，筆者水平有限，解釋得也不太好）中的相同值的整數(shù)就是同一個對象，可以試著把字節(jié)碼打印出來看一下（有關(guān)字節(jié)碼的內(nèi)容可以看下這篇博客：Python源碼學習筆記：Python程序執(zhí)行過程與字節(jié)碼）。
2 大整數(shù)運算
問題：在之前我們了解到了整數(shù)對象的內(nèi)部結(jié)構(gòu)，對于Python如何應(yīng)對“整數(shù)溢出”這個問題有了一個初步的認識。但是真正的難點在于大整數(shù)數(shù)學運算的實現(xiàn)。
2.1 整數(shù)運算概述
整數(shù)對象的運算由整數(shù)類型對象中的tp_as_number、tp_as_sequence、tp_as_mapping這三個字段所決定。整數(shù)類型對象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ù)對象僅支持數(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ù)對象支持的全部數(shù)學運算，以及對應(yīng)的處理函數(shù)：（只列出部分函數(shù)）
| 數(shù)學運算 | 處理函數(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ù)對象、整數(shù)類型對象以及整數(shù)數(shù)學運算處理函數(shù)之間的關(guān)系：
2.2 大整數(shù)運算處理過程
以加法為例，來認識大整數(shù)運算的處理過程。
加法處理函數(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用于臨時保存計算結(jié)果
- 第8~10行：如果兩個對象數(shù)組長度均不超過1，用MEDIUM_VALUE宏將其轉(zhuǎn)化成C整數(shù)進行運算（這種優(yōu)化也是可以學習的）
- 第13~17行：如果兩個整數(shù)均為負數(shù)，調(diào)用x_add計算兩者絕對值之和，再將結(jié)果符號設(shè)置為負（16行處）
- 第20行：如果a為負數(shù)，b為正數(shù)，調(diào)用x_sub計算b和a的絕對值之差即為最終結(jié)果
- 第24行：如果a為正數(shù)，b為負數(shù)，調(diào)用x_sub計算a和b的絕對值之差即為最終結(jié)果
- 第26行：如果兩個整數(shù)均為正數(shù)，調(diào)用x_add計算兩個絕對值之和即為最終結(jié)果
因此，long_add函數(shù)實際上將整數(shù)加法轉(zhuǎn)化成了絕對值加法x_add和絕對值減法x_sub，以及MEDIUM_VALUE。絕對值加法和絕對值減法不用考慮符號對計算結(jié)果的影響，實現(xiàn)較為簡單，這是Python將整數(shù)運算轉(zhuǎn)化成絕對值運算的原因。（這里也可以學習下）
大整數(shù)運算涉及到兩個數(shù)組之間的加法，整數(shù)數(shù)值越大，整數(shù)對象底層數(shù)組就越長，運算開銷也會越大。但是運算處理函數(shù)提供了一個快速通道：如果參與運算的整數(shù)對象底層數(shù)組長度均不超過1，直接將整數(shù)對象轉(zhuǎn)化成C整數(shù)類型進行運算，性能耗損極小。滿足這個條件的整數(shù)范圍在-1073741823~1073747823之間，足以覆蓋大部分運算情況了。
2.絕對值加法x_add()
下面我們來看一下Python是如何對數(shù)組進行加法運算的。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ù)組長度比較小，將a、b交換，數(shù)組長度較大的那個在前面（感覺做算法題有時候就需要交換下，方便統(tǒng)一處理）
第16~18行：創(chuàng)建新整數(shù)對象，用于保存計算結(jié)果（注意到長度必須要比a大，因為可能要進位）
第19~23行：遍歷b底層數(shù)組，與a對應(yīng)部分相機啊并保存在z中，需要注意到進位（可以看到這里是用按位與和右移進行計算的，通過位于算來處理也是很高效的，算法題中也比較常見）
第24~28行：遍歷a底層數(shù)組的剩余部分，與進位相加后保存在z中，同樣要注意進位運算
第29行：將進位寫入z底層數(shù)組最高位單元中
第30行：標準化z，去除計算結(jié)果z底層數(shù)組中前面多余的0
3 其他
大整數(shù)轉(zhuǎn)float溢出
至此，我們對int和float有了一定的認識，也自然會有一個問題：將大整數(shù)int轉(zhuǎn)化為float時發(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是有長度限制的，它的大小也是有上限的，因此當我們將一個很大的int轉(zhuǎn)化為float時，如果超出上限就會報錯。對此我們可以使用Decimal來解決：（這里只介紹了使用方式，具體原理大家可以去了解一下）
>>> from decimal import Decimal >>>d = Decimal(i) >>>f2 = float(d) >>> f2 inf
可以看到將i通過Decimal()轉(zhuǎn)化后就不會報錯了。
以上就是Python內(nèi)建類型int源碼學習的詳細內(nèi)容，更多關(guān)于Python內(nèi)建類型int的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細介紹了基于OpenCV如何實現(xiàn)答題卡識別，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要介紹了一文秒懂Python中的字符串,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
這篇文章主要介紹了jupyter notebook的安裝與使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
用于ETL的Python數(shù)據(jù)轉(zhuǎn)換工具詳解
這篇文章主要介紹了用于ETL的Python數(shù)據(jù)轉(zhuǎn)換工具,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
這篇文章主要為大家詳細介紹了如何基于Python實現(xiàn)一個簡單的文件夾整理工具,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2023-10-10
Python爬蟲爬取新浪微博內(nèi)容示例【基于代理IP】
這篇文章主要介紹了Python爬蟲爬取新浪微博內(nèi)容,結(jié)合實例形式分析了Python基于代理IP實現(xiàn)的微博爬取與抓包分析相關(guān)操作技巧,需要的朋友可以參考下2018-08-08
Python中判斷subprocess調(diào)起的shell命令是否結(jié)束
這篇文章主要介紹了Python中判斷subprocess調(diào)起的shell命令是否結(jié)束的方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
Python 判斷是否為質(zhì)數(shù)或素數(shù)的實例
下面小編就為大家?guī)硪黄狿ython 判斷是否為質(zhì)數(shù)或素數(shù)的實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
這篇文章主要介紹了python實現(xiàn)計算資源圖標crc值的方法,通過解析資源文件找到icon的數(shù)據(jù),從而實現(xiàn)該功能,需要的朋友可以參考下2014-10-10
python字典中g(shù)et()函數(shù)的基本用法實例
在字典內(nèi)置的方法中,想說的方法為get,這個方法是通過鍵來獲取相應(yīng)的值,但是如果相應(yīng)的鍵不存在則返回None,這篇文章主要給大家介紹了關(guān)于python字典中g(shù)et()函數(shù)的基本用法,需要的朋友可以參考下2022-03-03