Какова временная сложность del[pos:] для списка в Python?

Question

[d_ilyich]

Если удалить правую часть списка с помощью

del my_list[pos:]

то по времени это будет O(1) или O(N) ? Как это можно проверить? Я попытался оценить разницу с помощью pytest-benchmark на таком коде:

def del_slice() -> None:
    for _ in range(10_000):
        my_list = [1]*1_000_000
        del my_list[500_000:]

def del_last() -> None:
    for _ in range(10_000):
        my_list = [1]*1_000_000
        for _ in range(500_000):
            del my_list[-1]

def test_del_slice(benchmark):
    benchmark(del_slice)

def test_del_last(benchmark):
    benchmark(del_last)

Результаты:

----------------------------------------------------------------------------
Name (time in s)          Min                 Max                Mean       
----------------------------------------------------------------------------
test_del_slice        43.8683 (1.0)       57.6685 (1.0)       48.2936 (1.0) 
test_del_last        203.9794 (4.65)     239.6570 (4.16)     226.9720 (4.70)
----------------------------------------------------------------------------

Потом поменял немного:

def del_slice2() -> None:
    my_list = [[1]*500_000 for _ in range(5_000)]
    for l in my_list:
        del l[250_000:]

def del_last2() -> None:
    my_list = [[1]*500_000 for _ in range(5_000)]
    for l in my_list:
        for _ in range(250_000):
            del l[-1]

Результаты:

-------------------------------------------------------------------------
Name (time in s)         Min                Max               Mean       
-------------------------------------------------------------------------
test_del_slice       27.8310 (1.0)      36.0834 (1.0)      30.5021 (1.0) 
test_del_last        87.6777 (3.15)     97.6951 (2.71)     93.4931 (3.07)
-------------------------------------------------------------------------

По моим представлениям, если бы del_slice выполнялся за O(1), разница была бы больше. Возможно, я неправильно замеряю. Если же сложность не O(1), то почему? Ведь перемещать ничего не надо.

Answer 1

[dim5x]

Сложность O(n).
Если делать замеры для списков разных размеров, то увидим что время выполнения растёт линейно, что подтверждает сложность O(n).

Если же сложность не O(1), то почему? Ведь перемещать ничего не надо.

Удаление среза реализовано как проход по удаляемым элементам с вызовом Py_DECREF на каждый.

З.Ы. чисто теоретически сложность O(1) может быть для крайнего случая с pos = 0, если целиком уничтожается вся структура (но так ли это в реальности надо проверять) и pos = n - 1.
Ну и надо разделять абстрактную алгоритмику и конкретные бенчмарки.

Код.

import time
import matplotlib.pyplot as plt


def test_del_slice_complexity():
    sizes = [10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6]
    times = []

    for n in sizes:
        # Создаем список
        my_list = [1] * n

        # Замеряем время удаления
        start_time = time.perf_counter()
        del my_list[n // 2:]  # Удаляем 50% элементов
        end_time = time.perf_counter()

        elapsed = end_time - start_time
        times.append(elapsed)

        print(f"n = {n:>7}: {elapsed:.6f} сек")

    # Визуализация результатов
    plt.figure(figsize=(10, 5))
    plt.plot(sizes, times, 'o-', label='Измеренное время')
    plt.plot(sizes, [times[0] * n / sizes[0] for n in sizes], '--', label='Ожидаемое линейное время')
    plt.xscale('log')
    plt.yscale('log')
    plt.xlabel('Размер списка (n)')
    plt.ylabel('Время выполнения (сек)')
    plt.title('Сложность операции del my_list[n//2:]')
    plt.legend()
    plt.grid(True)
    plt.show()


if __name__ == "__main__":
    test_del_slice_complexity()

Comments

[fenrir]

Я не у компа чтобы посмотреть внимательно исходники, но готов поставить сотку, что описанный случай это корнеркейс при котором просто ob_size обрезается за O(1).

А линейно растёт время создания списка, которое тоже попало в измеряемую функцию.

[dim5x]

fenrir,
Создание списка выше, измеряю только del.

start_time = time.perf_counter()
del my_list[n // 2:]  # Удаляем 50% элементов
end_time = time.perf_counter()

[fenrir]

dim5x, да, действительно O(n).
listobject.c -> list_ass_slice_lock_held
Указатели на все удаляемые объекты копируются в recycle и далее по каждому проходим и освобождаем.

item = a->ob_item;
    /* recycle the items that we are about to remove */
    s = norig * sizeof(PyObject *);
    /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
    if (s) {
        if (s > sizeof(recycle_on_stack)) {
            recycle = (PyObject **)PyMem_Malloc(s);
            if (recycle == NULL) {
                PyErr_NoMemory();
                goto Error;
            }
        }
        memcpy(recycle, &item[ilow], s);
    }

    if (d < 0) { /* Delete -d items */
        Py_ssize_t tail;
        tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
        // TODO: these memmove/memcpy calls are not safe for shared lists in
        // GIL_DISABLED builds. (See issue #129069)
        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;
    }
    else if (d > 0) { /* Insert d items */
        ...
    }
    for (k = 0; k < n; k++, ilow++) {
        PyObject *w = vitem[k];
        FT_ATOMIC_STORE_PTR_RELEASE(item[ilow], Py_XNewRef(w));
    }
    for (k = norig - 1; k >= 0; --k)
        Py_XDECREF(recycle[k]);
    result = 0;
 Error:
    if (recycle != recycle_on_stack)
        PyMem_Free(recycle);
    Py_XDECREF(v_as_SF);
    return result;

[dim5x]

fenrir, сотку можно перевести на телефон :)