Software testing | the underlying implementation of list in Python

This article describes CPython in list How to implement . Link to the original text ：https://ceshiren.com/t/topic/10916

C Languages are represented by structures List object

C Language uses structs to implement list object , The structure code is as follows .

typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item; // Point to list Objects in the
Py_ssize_t allocated; // Memory allocation slot
} PyListObject;

List initialization

With I = [] For example

list Quantity of means len(l). The number of slots allocated refers to the number actually allocated in memory . General situation , The amount allocated in memory should be greater than list The number of . This is for when adding new elements , Avoid memory reallocation .

Append

When running l.append(1) when , CPython Will call app1()：

list_resize() Will deliberately allocate more memory , Avoid being called more than once . The allocated memory size increases ：0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

For the first time 4 Slots ,I[0] Points to a numeric object 1 . The square dotted line indicates unused slots . The averaging complexity of the append operation is O(1) .

Average time complexity is a kind of average time complexity , It is a simplified calculation method .

Continue appending elements ：l.append(2). call list_resize Realization n + 1 = 2. Due to the allocation of four spaces , No need to allocate memory . When two more numbers are appended to the list ,l.append(3), l.append(4), As shown in the figure below ：

Insert

In position 1 Insert integer 5 , That is to call python Of l.insert(1, 5) .CPython Would call ins1() ：

The insert operation needs to migrate the remaining elements to the right ：

The dotted line in the figure above indicates the unused slot position （slots）, Allocated 8 Slots , but list The length of is only 5 . insert The time complexity of is O(n).

pop

The last element of the pop-up list uses l.pop(),CPython Use listpop() To achieve this process . If the new memory size is less than half the allocated size , listpop() Will call list_resize Reduce list Memory .

Pop The time complexity of is O(1).

Be careful , Now slot position 4 Still points to an integer 4 , however list The size is 4 . Only pop More elements can be called list_resize() Reduce memory , If it were pop An element , size - 1 = 4 - 3 = 3, 3 Less than half of the allocated slot 8/2 = 4 . therefore list shrink to 6 Slots , list The size is 3 . Although the slot 3 and 4 Still point to an integer object , But the overall size becomes 3 .

remove

Python It can be used remove Deletes the specified element ：l.remove(5). At this point the call listremove() .

CPython call list_ass_slice() Function to slice the list and delete the elements . When in position 1 Remove elements 5 when , Low offset （low offset） yes 1 , High offset （high offset） yes 2 ：

remove The time complexity is O(n).

Article reference ：http://www.laurentluce.com/posts/python-list-implementation/