国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

深度剖析憑什么python中整型不會溢出

MSchumi / 701人閱讀

摘要:前言本次分析基于解釋器,版本在時代,整型有類型和長整型,長整型不存在溢出問題,即可以存放任意大小的整數。在后,統一使用了長整型。

前言

本次分析基于 CPython 解釋器,python3.x版本

在python2時代,整型有 int 類型和 long 長整型,長整型不存在溢出問題,即可以存放任意大小的整數。在python3后,統一使用了長整型。這也是吸引科研人員的一部分了,適合大數據運算,不會溢出,也不會有其他語言那樣還分短整型,整型,長整型...因此python就降低其他行業的學習門檻了。

那么,不溢出的整型實現上是否可行呢?

不溢出的整型的可行性

盡管在 C 語言中,整型所表示的大小是有范圍的,但是 python 代碼是保存到文本文件中的,也就是說,python代碼中并不是一下子就轉化成 C 語言的整型的,我們需要重新定義一種數據結構來表示和存儲我們新的“整型”。

怎么來存儲呢,既然我們要表示任意大小,那就得用動態的可變長的結構,顯然,數組的形式能夠勝任:

[longintrepr.h]
struct _longobject {
    PyObject_VAR_HEAD
    int *ob_digit;
};

長整型的保存形式

長整型在python內部是用一個 int 數組( ob_digit[n] )保存值的. 待存儲的數值的低位信息放于低位下標, 高位信息放于高下標.比如要保存 123456789 較大的數字,但我們的int只能保存3位(假設):

ob_digit[0] = 789;
ob_digit[1] = 456;
ob_digit[2] = 123;

低索引保存的是地位,那么每個 int 元素保存多大的數合適?有同學會認為數組中每個int存放它的上限(2^31 - 1),這樣表示大數時,數組長度更短,更省空間。但是,空間確實是更省了,但操作會代碼麻煩,比方大數做乘積操作,由于元素之間存在乘法溢出問題,又得多考慮一種溢出的情況。

怎么來改進呢?在長整型的 ob_digit 中元素理論上可以保存的int類型有 32 位,但是我們只保存 15 位,這樣元素之間的乘積就可以只用 int 類型保存即可, 結果做位移操作就能得到尾部和進位 carry 了,定義位移長度為 15

#define PyLong_SHIFT  15
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 1))

PyLong_MASK 也就是 0b111111111111111 ,通過與它做位運算 的操作就能得到低位數。

有了這種存放方式,在內存空間允許的情況下,我們就可以存放任意大小的數字了。

長整型的運算

加法與乘法運算都可以使用我們小學的豎式計算方法,例如對于加法運算:

ob_digit[2] ob_digit[1] ob_digit[0]
加數a 23 934 543
加數b + 454 632
結果z 24 389 175

為方便理解,表格展示的是數組中每個元素保存的是 3 位十進制數,計算結果保存在變量z中,那么 z 的數組最多只要 size_a + 1 的空間(兩個加數中數組較大的元素個數 + 1),因此對于加法運算,可以這樣來處理:

[longobject.c]
static PyLongObject * x_add(PyLongObject *a, PyLongObject *b) {
    int size_a = len(a), size_b = len(b);
    PyLongObject *z;
    int i;
    int carry = 0; // 進位
    
    // 確保a是兩個加數中較大的一個
    if (size_a < size_b) {
        // 交換兩個加數
        swap(a, b);
        swap(&size_a, &size_b);
    }
    
    z = _PyLong_New(size_a + 1);  // 申請一個能容納size_a+1個元素的長整型對象
    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;                 // 移除低15位, 得到進位
    }
    for (; i < size_a; ++i) {                   // 多帶帶處理a中高位數字
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
    return long_normalize(z);                   // 整理元素個數
    
}

這部分的過程就是,先將兩個加數中長度較長的作為第一個加數,再為用于保存結果的 z 申請空間,兩個加數從數組從低位向高位計算,處理結果的進位,將結果的低 15 位賦值給 z 相應的位置。最后的 long_normalize(z) 是一個整理函數,因為我們 z 申請了 a_size + 1 的空間,但不意味著 z 會全部用到,因此這個函數會做一些調整,去掉多余的空間,數組長度調整至正確的數量,若不方便理解,附錄將給出更利于理解的python代碼。

豎式計算不是按個位十位來計算的嗎,為什么這邊用整個元素?

豎式計算方法適用與任何進制的數字,我們可以這樣來理解,這是一個 32768 (2的15次方) 進制的,那么就可以把數組索引為 0 的元素當做是 “個位”,索引 1 的元素當做是 “十位”。

乘法運算

乘法運算一樣可以用豎式的計算方式,兩個乘數相乘,存放結果的 z 的元素個數為 size_a + size_b 即可:

操作 ob_digit[2] ob_digit[1] ob_digit[0]
乘數a 23 934 543
乘數b * 454 632
結果z 15 126 631 176
10 866 282 522
結果z 10 881 409 153 176

這里需要主意的是,當乘數 b 用索引 i 的元素進行計算時,結果 z 也是從 i 索引開始保存。先創建 z 并初始化為 0,這 z 上做累加操作,加法運算則可以利用前面的 x_add 函數:

// 為方便理解,會與cpython中源碼部分稍有不同
static PyLongObject * x_mul(PyLongObject *a, PyLongObject *b)
{
    int size_a = len(a), size_b = len(b);
    PyLongObject *z = _PyLong_New(size_a + size_b);
    memset(z->ob_digit, 0, len(z) * sizeof(int)); // z 的數組清 0
    
    for (i = 0; i < size_b; ++i) {
        int carry = 0;          // 用一個int保存元素之間的乘法結果
        int f = b->ob_digit[i]; // 當前乘數b的元素
        
        // 創建一個臨時變量,保存當前元素的計算結果,用于累加
        PyLongObject *temp = _PyLong_New(size_a + size_b);
        memset(temp->ob_digit, 0, len(temp) * sizeof(int)); // temp 的數組清 0
        
        int pz = i; // 存放到臨時變量的低位
        
        for (j = 0; j < size_a; ++j) {
            carry = f * a[j] + carry;
            temp[pz] = carry & PyLong_MASK;  // 取低15位
            carry = carry >> PyLong_SHIFT;  // 保留進位
            pz ++;
        }
        if (carry){     //  處理進位
            carry += temp[pz];
            temp[pz] = carry & PyLong_MASK;
            carry = carry >> PyLong_SHIFT;
        }
        if (carry){
            temp[pz] += carry & PyLong_MASK;
        }
        temp = long_normalize(temp);
        z = x_add(z, temp);
    }
    
    return z
    
}

這大致就是乘法的處理過程,豎式乘法的復雜度是n^2,當數字非常大的時候(數組元素個數超過 70 個)時,python會選擇性能更好,更高效的 Karatsuba multiplication 乘法運算方式,這種的算法復雜度是 3nlog3≈3n1.585,當然這種計算方法已經不是今天討論的內容了。有興趣的小伙伴可以去了解下。

總結

要想支持任意大小的整數運算,首先要找到適合存放整數的方式,本篇介紹了用 int 數組來存放,當然也可以用字符串來存儲。找到合適的數據結構后,要重新定義整型的所有運算操作,本篇雖然只介紹了加法和乘法的處理過程,但其實還需要做很多的工作諸如減法,除法,位運算,取模,取余等。

python代碼以文本形式存放,因此最后,還需要一個將字符串形式的數字轉換成這種整型結構:

[longobject.c]
PyObject * PyLong_FromString(const char *str, char **pend, int base)
{
}

這部分不是本篇的重點,有興趣的同學可以看看這個轉換的過程。

參考

longobject.c

附錄
# 例子中的表格中,數組元素最多存放3位整數,因此這邊設置1000
# 對應的取低位與取高位也就變成對 1000 取模和取余操作
PyLong_SHIFT = 1000
PyLong_MASK = 999

# 以15位長度的二進制
# PyLong_SHIFT = 15
# PyLong_MASK = (1 << 15) - 1

def long_normalize(num):
    """
    去掉多余的空間,調整數組的到正確的長度
    eg: [176, 631, 0, 0]  ==>  [176, 631]
    :param num:
    :return:
    """
    end = len(num)
    while end >= 1:
        if num[end - 1] != 0:
            break
        end -= 1

    num = num[:end]
    return num

def x_add(a, b):
    size_a = len(a)
    size_b = len(b)
    carry = 0

    # 確保 a 是兩個加數較大的,較大指的是元素的個數
    if size_a < size_b:
        size_a, size_b = size_b, size_a
        a, b = b, a

    z = [0] * (size_a + 1)
    i = 0
    while i < size_b:
        carry += a[i] + b[i]
        z[i] = carry % PyLong_SHIFT
        carry //= PyLong_SHIFT
        i += 1

    while i < size_a:
        carry += a[i]
        z[i] = carry % PyLong_SHIFT
        carry //= PyLong_SHIFT
        i += 1
    z[i] = carry

    # 去掉多余的空間,數組長度調整至正確的數量
    z = long_normalize(z)

    return z


def x_mul(a, b):
    size_a = len(a)
    size_b = len(b)
    z = [0] * (size_a + size_b)

    for i in range(size_b):
        carry = 0
        f = b[i]

        # 創建一個臨時變量
        temp = [0] * (size_a + size_b)
        pz = i
        for j in range(size_a):
            carry += f * a[j]
            temp[pz] = carry % PyLong_SHIFT
            carry //= PyLong_SHIFT
            pz += 1

        if carry:    # 處理進位
            carry += temp[pz]
            temp[pz] = carry % PyLong_SHIFT
            carry //= PyLong_SHIFT
            pz += 1

        if carry:
            temp[pz] += carry % PyLong_SHIFT
        temp = long_normalize(temp)
        z = x_add(z, temp)   # 累加

    return z


a = [543, 934, 23]
b = [632, 454]
print(x_add(a, b))
print(x_mul(a, b))

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/41848.html

相關文章

  • python中的無窮大

    摘要:起步中整型不用擔心溢出,因為理論上可以表示無限大的整數,直到把內存擠爆。而無窮大在編程中常常需要的。比如,從一組數字中篩選出最小的數字。而這臨時變量一般要初始無窮大或者去第一個元素的值。 起步 python中整型不用擔心溢出,因為python理論上可以表示無限大的整數,直到把內存擠爆。而無窮大在編程中常常需要的。比如,從一組數字中篩選出最小的數字。一般使用一個臨時變量用于存儲最后結果,...

    lordharrd 評論0 收藏0
  • Python貓薦書系統之四:《Python源碼剖析

    摘要:以下內容僅針對版書籍,等新版上市后,薦書欄目會對兩版的差異跟進介紹。當然,后續其它薦書的書目,也很有可能會送福利,一樣不容錯過。 showImg(https://segmentfault.com/img/bVbjIxq?w=6000&h=4000); 大家好,新一期的薦書欄目如期跟大家見面了。 先來看看今天的主角是誰:《Python源碼剖析——深度探索動態語言核心技術》,2008年出版...

    simpleapples 評論0 收藏0
  • 【C語言】從入門到入土(進階之數據的存儲)

    摘要:還不清楚原碼反碼補碼的可以到語言從入門到入土操作符篇中的移位操作符處學習一下。比如原碼反碼補碼原碼顯示值補碼數據存放內存中其實存放的是補碼補碼的表示與存儲在計算機系統中,數值一律用補碼來表示和存儲。 ...

    mcterry 評論0 收藏0
  • 【數據類型存儲原理】數據的存儲 - 深度剖析數據在內存中的存儲

    摘要:數據的存儲前言數據類型匯總整型家族浮點型家族自定義類型指針類型。整型家族注在之后的標準規定,將類型數據劃分為整型家族,因為字符在內存中會將其轉化為碼值進行存儲。 ...

    yuanzhanghu 評論0 收藏0

發表評論

0條評論

MSchumi

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<