Python list length adjustment method (with code)

The content of this article is about the length adjustment method of Python lists (with code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Python's list (list) is a very flexible array, and the length can be adjusted at will. It is precisely because of this convenience that we can't help but modify the array to meet our needs. Compared with insert, pop, etc., append usage is more common.

Some are used like this:

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

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

Also some are used like this:

test = []

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

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

It’s very happy and satisfying to use it like this.

But in fact, whenever we encounter a scenario where the data length can be dynamically modified, we should immediately react, that is, the problem of memory management.

If operating efficiency and convenience are met at the same time, it will be great news.

However, when God opens a window for you, he must have also closed a door!

Penny-pinching initialization

We are deeply influenced by the knowledge of pre-allocation. We also feel that the list is allocated a certain length during initialization, otherwise it would be "low" to apply for memory every time. ah.

Then in fact the list is really so "low":

import sys

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

# 输出 
72     # 空列表内存大小，也是 list 对象的总大小
8       # 代表增加一个成员，list 增加的大小

Our guess is that after the list is defined, a pool of a certain size will be pre-allocated to fill the data. Avoid applying for memory at every turn.

But the above experiment shows that the length of a member list is only 8 bytes larger than an empty list. If there really is such a pre-allocated pool, then the number of pre-allocated When adding members, the memory size of both should remain unchanged.

So it can be guessed that this list should not have such a pre-allocated memory pool. Here we need a real hammer

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;
}

When we execute test = [1], we actually only do two things:

Construct an empty list of corresponding length based on the number of members ;(Above code)

Put these members in one by one;

Some children may think that in the step of stuffing the members, some mechanism may be triggered to make it bigger?

It's a pity, because the initialization method is PyList_SET_ITEM, so there is no triggering mechanism here, it is just a simple assignment of array members:

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

So the initialization of the entire list is really The only thing is that there is no pre-allocated memory pool. You can directly apply for it on demand. Every carrot is a pit, which is really cruel;

The key to variable length

The initialization process is This is understandable, but if it continues to be like this during operation, it would be a bit unreasonable.

Just imagine, in the example of using append at the beginning of the article, if memory is applied for every time an element is appended, the list may be criticized to the point of doubting life, so it is obvious that when applying for memory, it He still has his own routine.

In the list, whether it is insert, pop or append, you will encounter list_resize. As the name suggests, this function is used to adjust the memory usage of the list object.

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;
}

In the above code, two nouns are frequently seen: newize and new_allocated. It needs to be explained here that newsize is not the number of increases/decreases, but the total number of members after the increase/decrease. For example:

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

When the above append triggers list_resize, newsize is 3 1, not 1; this is more important, because when pop is used to reduce list members, the reduced total number is passed in.

In the structure definition of list, there are two definitions of length, namely ob_size (actual number of members) and allocated (total number of members)

The relationship between them is:

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

So new_allocated is easy to understand. This is the new total number of pits.

When the meaning of the noun is almost understood, we can follow the clues to know what the size of a list will become after list_resize?

The method is actually very clear from the above comments and code. Here is a brief summary:

First determine a base: new_allocated = (newsize >> 3) (newsize < ; 9 ? 3 : 6);

Determine whether new_allocated newsize exceeds PY_SIZE_MAX. If it exceeds, an error will be reported directly;

Finally determine the new total number of pits: new_allocated newsize, if newsize is 0, then the total number of pits is directly 0;

The following is a demonstration:

#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

Start with a simple substitution method to calculate step by step:

Among them:

new_allocated = (newsize >> 3) (newsize < 9 ? 3 : 6) newsize (because the following newsize > 0)

When the original allocated >= newize and newize >= original When allocated / 2, allocated is not changed and memory is returned directly without applying for it

第 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 来处理。

总结

综上所述，在一些明确列表成员或者简单处理再塞入列表的情况下，我们不应该再用下面的方式：

test = []

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

而是应该用更加 pythonic 和 更加高效的列表推导式：test = [i for i in range(4)]。

The above is the detailed content of Python list length adjustment method (with code). For more information, please follow other related articles on the PHP Chinese website!