Почему в Python последовательность append-ов суммируется в O(n), а не в O(n logn)?

Question

[Егор Полянский]

Добрый день.

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

Разбирая исходный код метода append CPython (указан выше), разобрался в том, что сложность append равна O(1) при условии, что в массиве есть свободное место, иначе Python увеличивает новый размер экспоненциально (+3/+6 фиксированного количества памяти для списков) и копирует существующие элементы в новый массив. Получается так, что количество перераспределений уменьшается с ростом списка за счет экспоненциального роста выделенного размера массива. Так, например:

lst = []
for i in range(10):  
    lst.append(i)

На первом перераспределении копируется 1 элемент, на втором - 4, на третьем - 10, и так далее, что в теории дает геометрическую прогрессию вида: 1+4+10+⋯≤O(n). Как я понимаю, c каждой следующей итерацией количество операций между перераспределениями растёт линейно, а общее число перераспределений для n добавлений уменьшается как O(logn). Почему тогда в таком случае для n последовательности append-ов общая сложность равна O(n), а не O(n logn)?

Answer 1

[Сергей Соловьев]

Потому что, здесь вступает в игру такое понятие как амортизированная сложность. Для динамических массивов, которые увеличиваются в несколько раз (т.е. не + 10, а *2 например), амортизированная сложность - O(1).
Поэтому, у тебя O(n) * O(1) = O(n) (амортизированное)

Answer 2

[Wataru]

а общее число перераспределений для n добавлений уменьшается как O(logn). Почему тогда в таком случае для n последовательности append-ов общая сложность равна O(n), а не O(n logn)?

Потому что эти распределения разного размера. Первое - совсем маленькое. Второе чуть больше и т.д. Чтобы суммарно было O(n Log n), каждое из них должно быть пропорционально n.

1+4+10+⋯≤O(n)

Вот это и есть ответ. Первые слагаемые маленькие. Получается геометрическая прогрессия, которая дает линейную сумму от n.