питон: временная сложность [: 10] = [1,2,3]

Question

A большое: len(a)=10000000

Будет ли интерпретатор python оптимизировать операцию, например, с a[:10]=[1,2,3] до O(1) времени?Есть ли разница между a[:10]=[1,2,3] и a[:3]=[1,2,3]?Я имею в виду разницу между тем, изменяется ли длина.

Answer 1

Существует очень большая разница между двумя операторами:

a[:10] = [1,2,3]
a[:3]  = [1,2,3]

Первая включает в себя фактическое удаление некоторых элементов в списке, тогда как вторая можетпросто измените элементы, которые уже есть.Вы можете проверить это, выполнив:

print(len(a))

до и после операции.

Есть полезная веб-страница , которая показывает различные операции над стандартными структурами данных Python вместес их временными сложностями.Удаление из списка (который на самом деле является массивом под обложками) - это O(n), поскольку оно включает перемещение всех элементов за пределы области удаления, чтобы заполнить пробел, который в противном случае остался бы.

---

И,на самом деле, если вы посмотрите на код list_ass_slice, отвечающий за назначение фрагментов списка (несмотря на неудачный выбор имени в некоторых культурах), вы увидите, что он имеет число memcpy и memmove операции по изменению списка, например:

if (d < 0) { /* Delete -d items */
    Py_ssize_t tail;
    tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
    memmove(&item[ihigh+d], &item[ihigh], tail);
    if (list_resize(a, Py_SIZE(a) + d) < 0) {
        memmove(&item[ihigh], &item[ihigh+d], tail);
        memcpy(&item[ilow], recycle, s);
        goto Error;
    }
    item = a->ob_item;
}