Shulou(Shulou.com)06/02 Report--

This article introduces you how to go deep into the internal implementation of the Python list, the content is very detailed, interested friends can refer to, hope to be helpful to you.

The list in Python is very powerful, and it must be interesting to see what its internal implementation mechanism looks like.

Here is a Python script that adds a few integers to the list and then prints the list.

> > l = [] > > l.append (1) > > l.append (2) > > l.append (3) > > l [1,2,3] > for e in l:. Print e... 1 2 3

As you can see, the list is an iterator.

C language structure of list object

The list implementation in Cpython is similar to the following C structure. Ob_item is an array of pointers to list objects. Allocated is the number of slots requesting memory.

Typedef struct {PyObject_VAR_HEAD PyObject * * ob_item; Py_ssize_t allocated;} PyListObject

List initialization

See what happens when you initialize an empty list, for example: l = [].

Arguments: size of the list = 0 returns: list object = [] PyListNew: nbytes = size * size of global Python object = 0 allocate new list object allocate list of pointers (ob_item) of size nbytes = 0 clear ob_item set list's allocated var to 0 = 0 slots return list object

It is important to distinguish between the list size and the allocated slot size. The size of the list is the same as that of len (l). The size of the allocation slot refers to the number of slot space that has been allocated in memory. The size of the allocated slot is usually larger than the list size to avoid calling the function that allocates memory every time an element is added to the list. It will be described in detail below.

Append operation

What happens when you add an integer: l.append (1) to the list? The underlying C function app1 () is called.

Arguments: list object, new element returns: 0 if OK,-1 if not app1: n = size of list call list_resize () to resize the list to size nasty 1 = 0 + 1 = 1 list [n] = list [0] = new element return 0

Here is the list_resize () function. It requests more memory to avoid frequent calls to the list_resize () function. The growth pattern of the list is as follows: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88.

Arguments: list object, newsize returns: 0 if OK,-1 if not list_resize: new_allocated = (newsize > > 3) + (newsize

< 9 ? 3 : 6) = 3 new_allocated += newsize = 3 + 1 = 4 resize ob_item (list of pointers) to size new_allocated return 0 现在分配了 4 个用来装列表元素的槽空间，并且***个空间中为整数 1。如下图显示 l[0] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。 列表追加元素操作的平均复杂度为 O(1)。 继续添加新的元素：l.append(2)。调用 list_resize 函数，参数为 n+1 = 2， 但是因为已经申请了 4 个槽空间，所以不需要再申请内存空间。再添加两个整数的情况也是一样的：l.append(3)，l.append(4)。下图显示了我们现在的情况。 Insert 操作 在列表偏移量 1 的位置插入新元素，整数 5：l.insert(1,5)，内部调用ins1() 函数。 arguments: list object, where, new element returns: 0 if OK, -1 if not ins1: resize list to size n+1 = 5 ->

4 more slots will be allocated starting at the last element up to the offset where, right shift each element set new element at offset where return 0

The box of the dotted line still indicates the slot space that has been allocated but not used. Eight slots are now allocated, but the size of the list is only 5.

The average complexity of a list insert operation is O (n).

Pop operation

Take out an element in the list *, namely l.pop (), and call the listpop () function. The list_resize function is called in the listpop () function, and if the size of the list after the element is taken out is less than half of the allocated slot space, the size of the list will be reduced.

Arguments: list object returns: element popped listpop: if list empty: return null resize list with size 5-1 = 4.4 is not less than 8 so no shrinkage set list object size to 2 so no shrinkage set list object size to 4 return last element

The average complexity of the list pop operation is O (1).

You can see that slot space 4 still points to the original integer object after the pop operation, but the most important thing is that the size of the list has now changed to 4.

Continue to pop an element. In the list_resize () function, size-1 = 4-1 = 3 is already less than half the allocated slot space, so the allocated slot space is reduced to 6, and now the size of the list is 3.

You can see that slot spaces 3 and 4 still point to the original integer, but now the size of the list has changed to 3.

Remove operation

Python's list object has a method to delete the specified element: l.remove (5). The underlying listremove () function is called.

Arguments: list object, element to remove returns none if OK, null if not listremove: loop through each list element: if correct element: slice list between element's slot and element's slot + 1 return none return null

In order to slice the list and delete the elements, the list_ass_slice () function is called, and its implementation is interesting. When we delete element 5 in position 1 of the list, the offset of the low position is 1 and the offset of the high position is 2. 5.

Arguments: list object, low offset, high offset returns: 0 if OK list_ass_slice: copy integer 5 to recycle list to dereference it shift elements from slot 2 to slot 1 resize list to 5 slots return 0

The complexity of the list remove operation is O (n).

On how to go deep into the internal implementation of the Python list to share here, I hope that the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.