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

資訊專欄INFORMATION COLUMN

Python: 淺析列表的變長變短

AlphaGooo / 670人閱讀

摘要:前言的列表是一個非常靈活的數組,可以隨意調整長度。所以可以猜測這塊應該是沒有這樣的一個預分配內存池。比方說上面的觸發時,是,而不是這邊比較重要,因為在這類減少列表成員時候,就是傳入縮減后的總數目。

前言

Python 的列表(list)是一個非常靈活的數組,可以隨意調整長度。正是因為這種便利,使得我們會情不自禁地去修改數組以滿足我們的需求,其中相比于insert, pop 等等而言, append 用法更常見。

有像這樣使用:

>>> test = []
>>> test.append(1)
>>> test.append({2})
>>> test.append([3])
>>> print test

# 輸出 
[1, set([2]), [3]]

也有像這樣使用的:

test = []

for i in range(4):
    test.append(i)
print test

# 輸出 
[0, 1, 2, 3]

這樣用很開心,也很滿足。

但其實只要遇到能夠動態修改數據長度場景,我們都應該馬上反應過來一點,那就是內存管理的問題。

如果運行效率和便捷性同時滿足的話,那簡直就是大大的福音呀。

然而,上帝為你開啟一扇窗的同時肯定也已經關上了一扇門了!

吝嗇的初始化

深受預分配知識的熏陶,我們也是覺得 list 在初始化是有分配一定的長度的,要不然每次都申請內存那得多 ”low“ 啊。

然后實際上 list 真的就是這么 ”low“:

import sys

test = []
test_1 = [1]
print sys.getsizeof(test)
print sys.getsizeof(test_1) - sys.getsizeof(test)

# 輸出 
72     # 空列表內存大小,也是 list 對象的總大小
8       # 代表增加一個成員,list 增加的大小 ( 此大小為對象指針的長度 )

我們的猜測是,list 在定義之后,會預先分配好一個一定大小的池用來塞數據,以避免動不動就申請內存。

但是在上面的實驗看出,一個成員的列表,比一個空列表,長度僅僅只是大了 8 字節(對象指針的大小),如果真的存在這樣一個預分配的池,那么在預分配個數之內添加成員,兩者的內存大小應該是保持不變才對。

所以可以猜測這塊 list 應該是沒有這樣的一個預分配內存池。這里需要來個實錘

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
        
    // list對象指針的緩存
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    
    // list 成員的內存申請
    nbytes = size * sizeof(PyObject *);
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

當我們在執行 test = [1] 時,實際上只做了兩件事:

根據成員的數目,構建相應長度的空列表;(上述代碼)

一個個將這些成員塞進去;

可能有童鞋會覺得,在塞成員的那一步,說不定會觸發什么機制使它變大?

很可惜,因為初始化用的方法是 PyList_SET_ITEM, 所以這里是木有的觸發什么機制,只是簡單的數組成員賦值而已:

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

所以整個 list 的初始化,還真的就是木有預分配的內存池,直接按需申請,一個蘿卜一個坑,實在得狠;

可變長的關鍵

初始化過程是這樣還可以理解,如果運行中還這樣的話,那就有點說不過去了。

試想下,在文章開頭用 append 的例子中,如果每 append 一個元素就申請一次內存,那么list 可能要被吐槽到懷疑人生了, 所以很明顯,在對于內存的申請,它還是有自己的套路的。

list 里面,不管是 insertpop 還是 append,都會遇到 list_resize,故名思義,這個函數就是用來調整 list 對象的內存占用的。

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    # 確定新擴展之后的占坑數
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;

    # 申請內存
    items = self->ob_item;
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

在上面的代碼中,頻繁看到兩個名詞:newsizenew_allocated, 這里需要解釋下,newsize 并不是 增加/減少 的個數,而是 增加/減少 之后的成員總數目。比方說:

a = [1, 2, 3]
a.append(1)

上面的 append 觸發list_resize 時, newsize 是 3 + 1, 而不是 1;這邊比較重要,因為在 pop 這類減少列表成員時候,就是傳入縮減后的總數目。

在 list 的結構定義中,關于長度的定義有兩個,分別是 ob_size(實際的成員數)allocated(總成員數)

它們之間的關系就是:

 0 <= ob_size <= allocated
 len(list) == ob_size

所以 new_allocated 就很好理解了,這個就是新的總坑數。

當名詞含義理解得差不多時,我們就能順藤摸瓜知道一個列表在list_resize 之后,大小會變成怎樣?

方法其實從上面注釋和代碼都說得很明白了,這里再簡單整理下:

先確定一個基數:new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

判斷下 new_allocated + newsize 有沒有超過 PY_SIZE_MAX, 如果超過了,直接報錯;

最終確定新的總坑數是:new_allocated + newsize, 如果 newsize 是 0, 那么總坑數直接為 0 ;

下面演示下:

#coding: utf8
import sys

test = []
raw_size = sys.getsizeof(test)

test.append(1)
print "1 次 append 減去空列表的內存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "2 次 append 減去空列表的內存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "3 次 append 減去空列表的內存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "4 次 append 減去空列表的內存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "5 次 append 減去空列表的內存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "6 次 append 減去空列表的內存大小:%s " % (sys.getsizeof(test) - raw_size)
# 輸出結果
1 次 append 減去空列表的內存大小:32
2 次 append 減去空列表的內存大小:32
3 次 append 減去空列表的內存大小:32
4 次 append 減去空列表的內存大小:32
5 次 append 減去空列表的內存大小:64
6 次 append 減去空列表的內存大小:64

開始簡單的代入法一步步算:

其中:

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize (因為下面的 newsize > 0)

當原allocated >= newsize 并且 newsize >= 原allocated / 2 時,不改變 allocated 不申請內存直接返回

第 n 次 append 列表原長度 新增成員數 原 allocated newsize new_allocated
1 0 1 0 0 + 1 = 1 3 + 1 = 4
2 1 1 4 1 + 1 = 2 無需改變
3 2 1 4 2 + 1 = 3 無需改變
4 3 1 4 3 + 1 = 4 無需改變
5 4 1 4 4 + 1 = 5 3 + 5 = 8
6 5 1 8 5 + 1 = 6 無需改變

通過上面的表格,應該比較清楚看到什么時候會觸發改變 allocated,并且當觸發時它們是如何計算的。為什么我們需要這樣關注 allocated?理由很簡單,因為這個值決定了整個 list 的動態內存的占用大小;

擴容是這樣,縮容也是照貓畫虎。反正都是算出新的 allocated, 然后由 PyMem_RESIZE 來處理。

#define PyMem_REALLOC(p, n)    ((size_t)(n) > (size_t)PY_SSIZE_T_MAX  ? NULL 
                : realloc((p), (n) ? (n) : 1))

#define PyMem_RESIZE(p, type, n) 
  ( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL :    
    (type *) PyMem_REALLOC((p), (n) * sizeof(type)) 

基本上,就是判斷是否超過最大數,否則的話就是和C realloc函數近似了,以下摘抄了一段關于C realloc函數的描述:

多說幾句

綜上所述,在一些明確列表成員或者簡單處理再塞入列表的情況下,我們不應該再用下面的方式:

test = []

for i in xrange(4):
    test.append(i)
print test

而是應該用列表推導式:test = [i for i in xrange(4)]

為什么推薦列表推導呢?顯而易見的效果就有:

簡練、清晰;

用多少就申請多少,不會因為 append 觸發 PyMem_RESIZE 申請過多內存;容易造成內存浪費;

相比 for i in xxx,列表推導方式直接增加元素,少了一些函數調用,如:SETUP_LOOPCALL_FUNCTION 等;

但是上面的推薦肯定也是在某些前提條件下才合適咯:

真的只是為了得到一個列表;

循環體內邏輯簡單,沒有太復雜的處理、判斷、調用等等;

PS: 切記勿為了使用列表推導而使用,合理使用才是科學之道;

歡迎各位大神指點交流, QQ討論群: 258498217
轉載請注明來源: https://segmentfault.com/a/11...

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

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

相關文章

  • SVG + CSS 實現 Material Design Loading

    摘要:在研究的過程中,發現有大神用在上實現了它。由制定,是一個開放標準。省略這時,你就能看到線段周而復始地從一根細線變為一個圓圈。這次感覺是不是很相像了,只是現在它的開口一直處于一個位置,就沒什么魔性了。 showImg(http://upload-images.jianshu.io/upload_images/1258730-02e5f2eca07eaa59.gif?imageMogr2/...

    txgcwm 評論0 收藏0
  • 智能合約語言Solidity教程系列5 - 數組介紹

    摘要:還需注意的一點是,定長數組,不能與變長數組相互賦值,我們來看下面的代碼無法編譯已經計劃在未來移除這樣的限制。的變長數組,可以通過給賦值調整數組長度。的變長數組不支持。 本文首發于深入淺出區塊鏈社區原文鏈接:智能合約語言Solidity教程系列5 - 數組介紹原文已更新,請讀者前往原文閱讀 Solidity 教程系列第5篇 - Solidity 數組介紹。Solidity 系列完整的文章...

    draveness 評論0 收藏0
  • Python入門-高級數據結構

    摘要:下面讓我們一塊來看下的中高級數據結構。到現在,我們學習了列表元組字典和集合種高級數據結構。 < 返回索引頁 高級數據結構 列表與元組 什么是列表 列表的操作 什么是元組 元組的操作 字典與集合 字典的定義 字典的操作 集合的定義 集合的操作 序列 序列的通用操作 可變類型和不可變類型 深copy和淺copy 總結 練習 參考 高級數據結構 我們知道P...

    jayzou 評論0 收藏0

發表評論

0條評論

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