How to execute Python [list] * num? what time is the complexity and complexity of the memory?

Question

I am new to Python. Recently I was confused by the syntax "[list] * k". I want to understand how Python actually executes it. Example:

>>> l = [1, 2] * 10 >>> l [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2] 

Suppose len (list) = n, when Python interprets it, I have the following assumptions with my limited knowledge.

• The list.extend (list) method is used. Thus, it will occupy the space O (n * k) and use the time O (n * k).

• it only copies the source list and makes it a k-copy. So it will take O (k) space and use O (k) time.

If my second assumption is correct, why and how does the following statement work?

 >>> l[3] = 100 >>> l [1, 2, 1, 100, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2] 

Any official project document, source code and PEP link are welcome!

Following actions,

The source code link provided by @JoshLee and @MSeifert is very useful for understanding the internal mechanism. See here list_repeat

The following code snippet confirms the complexity of the O (n * k) space.

 size = Py_SIZE(a) * n; 

Also the following code snippet confirms O (n * k) time complexity.

 p = np->ob_item; items = a->ob_item; for (i = 0; i < n; i++) { for (j = 0; j < Py_SIZE(a); j++) { *p = items[j]; Py_INCREF(*p); p++; } } 

Answer 1

A list is a small wrapper around an array of pointers to Python objects. So a Python list containing 1, 2, 3 would look like this:

 l = [1, 2, 3] 

If you multiply it by 5, the indices will refer to the same element, for example, the index 0, 3, 6, 9, 12 will keep the same memory address (which explains why changing one element did not change all of them)

 l2 = l * 5 

However, when the objects pointed to by the list were mutable , a change (as opposed to replacing, as in your example) to one of the elements will be reflected in all of them:

 >>> ls = [{1}, {2}, {3}] >>> ls2 = ls*3 >>> ls[0].add(2) >>> ls2 [{1, 2}, {2}, {3}, {1, 2}, {2}, {3}, {1, 2}, {2}, {3}] 

So, although this has the spatial and temporal complexity of O(n*k) , it is not so bad if you created a list containing pointers to different objects:

 [int(i % 3 + 1) for i in range(15)] 

Note that CPython actually reuses small integers, so the last images are inaccurate when dealing with integers like 1, 2, 3, ... This will look like the second image, but for other classes they are (with a few more exceptions ) are different objects. However, this only affects the factors, so in any case it will disappear in the notation O , but it's nice to know.

The list multiplication code is written in C (as many built-in functions and types), and you can see it here (CPython 3.6.4) :

 static PyObject * list_repeat(PyListObject *a, Py_ssize_t n) { Py_ssize_t i, j; Py_ssize_t size; PyListObject *np; PyObject **p, **items; PyObject *elem; if (n < 0) n = 0; if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n) return PyErr_NoMemory(); /* Create an empty list: Space complexity: k * n */ size = Py_SIZE(a) * n; if (size == 0) return PyList_New(0); np = (PyListObject *) PyList_New(size); if (np == NULL) return NULL; items = np->ob_item; /* Special case: The multiplied list contains one item. Time complexity: k */ if (Py_SIZE(a) == 1) { elem = a->ob_item[0]; for (i = 0; i < n; i++) { items[i] = elem; Py_INCREF(elem); } return (PyObject *) np; } /* General case: The multiplied list contains more than one item: Time complexity: n * k */ p = np->ob_item; items = a->ob_item; for (i = 0; i < n; i++) { for (j = 0; j < Py_SIZE(a); j++) { *p = items[j]; Py_INCREF(*p); p++; } } return (PyObject *) np; } 

Comments were added by me to explain the source code (undocumented).