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