Python如何执行[list]*num？什么是时间复杂性和内存复杂性？

Question

我是Python的新手.我最近被语法"[list]*k"搞糊涂了.我想了解Python如何实际执行它.例:

>>> 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]

假设len(list)= n,当Python解释它时,我跟随我的有限知识进行猜测.

1. 它使用list.extend(list)方法.因此它将占用O(n*k)空间并使用O(n*k)时间.

2. 它只复制原始列表的引用并制作它的副本.因此,它将占用O(k)空间并使用O(k)时间.

如果我的第二个猜测是这样的,为什么以及如何跟随声明有效？

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

欢迎任何官方设计文档,源代码和PEP参考!

跟进,

@JoshLee和@MSeifert提供的源代码链接非常有助于理解内部机制.请参阅list_repeat

以下代码片段确认空间复杂度为O(n*k).

size = Py_SIZE(a) * n;

以下代码片段确认时间复杂度为O(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++;
    }
}

Answer 1

列表是围绕Python对象指针数组的浅包装器.所以包含的Python列表1, 2, 3如下所示:

l = [1, 2, 3]

如果将它乘以5,则索引仍将引用相同的项,例如索引0,3,6,9,12将存储相同的内存地址(这解释了为什么更改一个项目并未全部更改它们):

l2 = l * 5

但是,当列表指向的对象是可变的时,对其中一个项的更改(与示例中的替换相反)将反映在所有项中:

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

因此,虽然它具有空间和时间复杂度,O(n*k)但它并不像创建包含指向不同对象的指针的列表那样糟糕:

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

请注意,CPython实际上重用了小整数 - 所以当处理像1,2,3等整数时,最后的图像是不准确的.它就像第二个图像 - 但对于其他类,它们(除了一些例外)会是不同的对象.然而,这只会影响因素,所以O无论如何都会在符号中消失,但很高兴知道.

列表乘法代码是用C语言编写的(就像许多内置函数和类型一样),你可以在这里看到它(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;
}

我添加了评论,只是为了解释(未记录的)源代码.