Python的extend是如何工作的？

Question

如果我有一个列表：

a = [1,2,3,4]

然后我用扩展方法添加4个元素：

a.extend(range(5,10))

最后我得到：

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]

那么，Python是怎么做到的呢？它是创建一个新列表然后把元素复制过去，还是直接把'a'变大了？我有点担心使用扩展会占用太多内存。另外，我还看到在我正在修改的代码里，有个评论说扩展10000次每次100比一次性扩展1000000要快。

Answer 1

它的工作方式就像是这样定义的

def extend(lst, iterable):
    for x in iterable:
        lst.append(x)

这会改变原来的列表，而不是创建一个副本。

根据具体的实现方式，append（添加）和extend（扩展）可能会让列表复制它自己的数据结构，但这很正常，不用担心。例如，基于数组的实现通常会以指数方式增长底层数组，因此在增长时需要复制元素列表。

Answer 2

Python的文档上是这么说的：

通过把给定列表中的所有项目添加到当前列表的末尾来扩展这个列表；这相当于 a[len(a):] = L。

至于它背后是如何实现的，其实你不需要太担心这个。

Answer 3

L.extend(M) 的时间复杂度是摊销 O(n)，其中 n 是 m 的长度，所以一般来说，过多的复制并不是个大问题。只有在没有足够空间来扩展时，才会出现复制的情况。当列表很大，而你对单次扩展调用的时间有要求时，这就成了一个问题。

在这种情况下，你应该考虑寻找一种更高效的数据结构来解决你的问题。不过在实际使用中，这种情况很少发生。

下面是 CPython 中相关的代码，你可以看到在扩展列表时会额外分配空间，以避免过多的复制。

static PyObject *
listextend(PyListObject *self, PyObject *b)
{
    PyObject *it;      /* iter(v) */
    Py_ssize_t m;                  /* size of self */
    Py_ssize_t n;                  /* guess for size of b */
    Py_ssize_t mn;                 /* m + n */
    Py_ssize_t i;
    PyObject *(*iternext)(PyObject *);

    /* Special cases:
       1) lists and tuples which can use PySequence_Fast ops
       2) extending self to self requires making a copy first
    */
    if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
        PyObject **src, **dest;
        b = PySequence_Fast(b, "argument must be iterable");
        if (!b)
            return NULL;
        n = PySequence_Fast_GET_SIZE(b);
        if (n == 0) {
            /* short circuit when b is empty */
            Py_DECREF(b);
            Py_RETURN_NONE;
        }
        m = Py_SIZE(self);
        if (list_resize(self, m + n) == -1) {
            Py_DECREF(b);
            return NULL;
        }
        /* note that we may still have self == b here for the
         * situation a.extend(a), but the following code works
         * in that case too.  Just make sure to resize self
         * before calling PySequence_Fast_ITEMS.
         */
        /* populate the end of self with b's items */
        src = PySequence_Fast_ITEMS(b);
        dest = self->ob_item + m;
        for (i = 0; i < n; i++) {
            PyObject *o = src[i];
            Py_INCREF(o);
            dest[i] = o;
        }
        Py_DECREF(b);
        Py_RETURN_NONE;
    }

    it = PyObject_GetIter(b);
    if (it == NULL)
        return NULL;
    iternext = *it->ob_type->tp_iternext;

    /* Guess a result list size. */
    n = _PyObject_LengthHint(b, 8);
    if (n == -1) {
        Py_DECREF(it);
        return NULL;
    }
    m = Py_SIZE(self);
    mn = m + n;
    if (mn >= m) {
        /* Make room. */
        if (list_resize(self, mn) == -1)
            goto error;
        /* Make the list sane again. */
        Py_SIZE(self) = m;
    }
    /* Else m + n overflowed; on the chance that n lied, and there really
     * is enough room, ignore it.  If n was telling the truth, we'll
     * eventually run out of memory during the loop.
     */

    /* Run iterator to exhaustion. */
    for (;;) {
        PyObject *item = iternext(it);
        if (item == NULL) {
            if (PyErr_Occurred()) {
                if (PyErr_ExceptionMatches(PyExc_StopIteration))
                    PyErr_Clear();
                else
                    goto error;
            }
            break;
        }
        if (Py_SIZE(self) < self->allocated) {
            /* steals ref */
            PyList_SET_ITEM(self, Py_SIZE(self), item);
            ++Py_SIZE(self);
        }
        else {
            int status = app1(self, item);
            Py_DECREF(item);  /* append creates a new ref */
            if (status < 0)
                goto error;
        }
    }

    /* Cut back result list if initial guess was too large. */
    if (Py_SIZE(self) < self->allocated)
        list_resize(self, Py_SIZE(self));  /* shrinking can't fail */

    Py_DECREF(it);
    Py_RETURN_NONE;

  error:
    Py_DECREF(it);
    return NULL;
}

PyObject *
_PyList_Extend(PyListObject *self, PyObject *b)
{
    return listextend(self, b);
}