Какова временная сложность dict.clear () O (1) в Python? - PullRequest
Новая
       22

Какова временная сложность dict.clear () O (1) в Python?

0 голосов
/ 22 ноября 2018

Согласно https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt, временная сложность dict.clear () равна O (1).

Насколько я знаю, dict.clear () отличается от назначения dict = {}, так как dict.clear () вносит изменения в один и тот же dict, а dict = {} создает новый dict.

Теперь, если dict.clear () очищает тот же объект dict, то как он может его завершитьв O (1).

Ответы [ 2 ]

0 голосов
/ 23 ноября 2018

Некоторое обоснование того, почему его называют O (1):

Метод clear() на самом деле просто присваивает внутренние словарные структуры новым пустым значениям (как можно видеть в * 1004).* источник ).Казалось бы, O (n) часть является результатом уменьшения количества ссылок и других вещей, связанных с GC.Но это чисто функция подхода GC, который использует CPython (т.е. подсчет ссылок);Вы можете представить различные подходы, которые не требуют явной очистки, подобной этой, или где очистка произойдет намного позже (или даже будет амортизирована).Поскольку в идеале временная сложность clear() не должна зависеть от базового подхода к ГХ, все части, связанные с ГХ, опускаются, что делает его "O (1)".ИМО, это в основном определительный аргумент, чем все остальное, но это как минимум какое-то оправдание.

0 голосов
/ 22 ноября 2018

Сначала я подумал, что dict.clear просто выполнил некоторое уменьшение ссылок, чтобы сборщик мусора выполнил грязную работу без O (1), но, глядя на исходный код (спасибо Timgeb за предоставленную ссылкуКажется, это не так: 

   oldvalues = mp->ma_values;
    if (oldvalues == empty_values)
        return;
    /* Empty the dict... */
    dictkeys_incref(Py_EMPTY_KEYS);
    mp->ma_keys = Py_EMPTY_KEYS;
    mp->ma_values = empty_values;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    /* ...then clear the keys and values */
    if (oldvalues != NULL) {
        n = oldkeys->dk_nentries;
        for (i = 0; i < n; i++)
            Py_CLEAR(oldvalues[i]);

Я вижу, что если в словаре есть значения, то выполняется цикл, чтобы уменьшить ссылки на эти значения и установить указатели на NULL.Похоже, что O(n) не O(1), поскольку это зависит от количества значений.

Когда вы присваиваете новый дикт, такой как d = {}, это O(1), но сборщик мусорадолжен удалить старый объект, если на него больше нет ссылок.Это может быть неправильно при назначении, но это произойдет, если Python не завершится внезапно.

...