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

This article focuses on "how Python implements the list". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how Python implements the list.

I. list structure

Create the underlying structure of the list C language

Lists = [] list.append ('name') list.append (' age') list.append ('grade') typedef struct {struct _ object * _ ob_next; struct _ object * _ ob_prev; / / python put objects in linked lists for memory management Py_ssize_t ob_refcnt; / / reference counters, that is, how many variables use it PyObject * * ob_item / / pointer, Py_ssize_t ob_size; / / number of existing elements in the list Py_ssize_t allocated; / / list capacity, which can hold the number of PyListObject

Create a list

Name_list = []

PyObject * PyList_New (Py_ssize_t size) {PyListObject * op; size_t nbytes;#ifdef SHOW_ALLOC_COUNT static int initialized = 0; if (! initialized) {Py_AtExit (show_alloc); initialized = 1;} # endif / / caching mechanism 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 (); nbytes = size * sizeof (PyObject *); if (numfree) {numfree--; op = free_ list [numfree]; _ Py_NewReference ((PyObject *) op); # ifdef SHOW_ALLOC_COUNT count_reuse++;#endif} else {op = PyObject_GC_New (PyListObject, & PyList_Type) If (op = = NULL) return NULL;Py#ifdef SHOW_ALLOC_COUNT count_alloc++;#endif} if (size 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; / / number of elements op- > allocated = size; / / capacity _ PyObject_GC_TRACK (op); / / put into the two-way linked list to maintain return (PyObject *) op; / / pointer to the return list} III. Add elements

When you insert an element into list, you expand the continuous memory address (capacity), create the content p that needs to be inserted in memory, and put the address * p into the space of list, so the ob_item of PyListObject is the pointer of the pointer.

The curve of capacity expansion is generally 0pm 4pm 8pm 16pm 24.

/ / add element static intapp1 (PyListObject * self, PyObject * v) {/ / get the actual number of elements Py_ssize_t n = PyList_GET_SIZE (self); assert (v! = NULL); if (n = = PY_SSIZE_T_MAX) {PyErr_SetString (PyExc_OverflowError, "cannot add more objects to list"); return-1 } / / calculate the current capacity and the number of internal elements / / add elements directly / expand the capacity to add if (list_resize (self, nasty 1) = =-1) return-1; / / add elements to ob_item,v Py_INCREF (v); PyList_SET_ITEM (self, n, v); return 0;}

Expand capacity

/ / capacity expansion mechanism / / newsize: number of existing elements + 1static intlist_resize (PyListObject * self, Py_ssize_t newsize) {PyObject * * items; size_t new_allocated; Py_ssize_t allocated = self- > allocated / / current capacity / / 1, the capacity is greater than the number / / 2, and the number is more than half of the capacity (sufficient capacity and no memory waste) if (allocated > = newsize & & newsize > = (allocated > > 1) {assert (self- > ob_item! = NULL | | newsize = = 0); Py_SIZE (self) = newsize; return 0 } / * * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,. * / / the algorithm of capacity expansion mechanism 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; / capacity expansion / reduction (involving migration of original elements) items = self- > ob_item; if (new_allocated ob_item = items; Py_SIZE (self) = newsize; self- > allocated = new_allocated Return 0;} IV. Remove elements

List.pop ()

Delete the last element only need to modify the size, do not need to clear the data, the next time append can directly overwrite this location

After the specified index position is removed, it is padded forward.

Static PyObject * listpop (PyListObject * self, PyObject * args) {Py_ssize_t I =-1; PyObject * v; int status; if (! PyArg_ParseTuple (args, "| n:pop", & I)) return NULL; if (Py_SIZE (self) = = 0) {/ * Special-case most common failure cause * / PyErr_SetString (PyExc_IndexError, "pop from empty list"); return NULL } if (I

< 0) i += Py_SIZE(self); if (i < 0 || i >

= Py_SIZE (self)) {PyErr_SetString (PyExc_IndexError, "pop index out of range"); return NULL;} v = self- > ob_ item [I]; / / delete the last one and change only size if (I = = Py_SIZE (self)-1) {status = list_resize (self, Py_SIZE (self)-1); assert (status > = 0); return v / * and v now owns the reference the list had * /} Py_INCREF (v); / / is not the last one and needs to move the data location status = list_ass_slice (self, I, iTun1, (PyObject *) NULL); assert (status > = 0); / * Use status, so that in a release build compilers don't * complain about the unused name. * / (void) status; return v;} 5. Clear

List.clear ()

Static intlist_clear (PyListObject * a) {Py_ssize_t I; PyObject * * item = a-> ob_item; if (item! = NULL) {I = Py_SIZE (a); / / each element is set to empty Py_SIZE (a) = 0; a-> ob_item = NULL; a-> allocated = 0 / / reference counter-1 while (--I > = 0) {Py_XDECREF (item [I]);} PyMem_FREE (item);} return 0;} VI. Destroy

Del list

Destroy the list object

Count the references in the list-1

The reference count is > 0, and if there are applications, do not do so.

Reference count = 0, no one uses it

Process the elements of the list and count all references-1 (GC recycle 0 count)

Ob_item=0,ob_size=0,ob_allocated=0

Remove the list from the two-way linked list and destroy it

In order to improve efficiency, the Python end period internally caches 80 list for free_list, stores unused list, and initializes it directly from the cache when it is created. If 80 have been saved, the object will be destroyed directly in memory when del

Static voidlist_dealloc (PyListObject * op) {Py_ssize_t I; / / determine whether the reference count is 0 PyObject_GC_UnTrack (op); Py_TRASHCAN_SAFE_BEGIN (op) if (op- > ob_item! = NULL) {I = Py_SIZE (op); while (--I > = 0) {Py_XDECREF (op- > ob_ item [I]) } PyMem_FREE (op- > ob_item);} / / if there are no 80 free_list, cache this list if (numfree)

< PyList_MAXFREELIST && PyList_CheckExact(op)) free_list[numfree++] = op; else Py_TYPE(op)->

Tp_free ((PyObject *) op); Py_TRASHCAN_SAFE_END (op)}

That is to say, when you create a list, you don't actually open memory directly, but take a look at free_list first.

# the address of two times list is the same > list1= (list1) 69070216L > del list1 > list2= [0meme0re0] > id (list2) 69303304L > at this point, I believe you have a deeper understanding of "how Python implements the list". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.