python - 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. 它只复制原始列表的引用并制作 k 个副本。因此它将占用 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 对象的指针数组的浅层包装器。因此，包含 1, 2, 3 的 Python 列表将如下所示:

l = [1, 2, 3]

如果将它乘以 5，索引仍将引用相同的项，例如索引 0、3、6、9、12 将存储相同的内存地址(这解释了为什么更改一项不会更改所有项) :

l2 = l * 5

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

>>> 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 等整数时，最后的图像是不准确的......它就像第二张图像 - 但对于其他类，它们(还有更多异常(exception))将是不同的对象。然而，这只会影响因数，因此无论如何都会在 O 表示法中消失，但很高兴知道这一点。

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

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