Вход · задача «удалить лишние элементы из списка»

Две ошибочные версии удаления спама

Занятие начинается с кода, который часто пишут первым. В списке четыре комментария, в двух есть ссылка — это спам. Обе версии удаляют элементы из списка во время прохода по нему. Первая оставляет в списке один спам-комментарий, вторая завершается с IndexError. Вывод настоящий, Python 3.12.

def is_spam(text):
    return "http" in text

comments = ["Отличный урок", "http://win.ru",
            "http://prize.ru", "Спасибо"]
for text in comments:
    if is_spam(text):
        comments.remove(text)
print(comments)

['Отличный урок', 'http://prize.ru', 'Спасибо']

comments = ["Отличный урок", "http://win.ru",
            "http://prize.ru", "Спасибо"]
for i in range(len(comments)):
    if is_spam(comments[i]):
        del comments[i]
print(comments)

Traceback (most recent call last):
  File "moderation_v2.py", line 6, in <module>
    if is_spam(comments[i]):
               ~~~~~~~~^^^
IndexError: list index out of range

Чтобы объяснить обе ошибки, нужны понятия индекса, границы и инварианта прохода. Занятие вводит их по порядку, и в части 6 этот код разбирается по шагам.

Часть 1 · массив в памяти · определение и демонстрация адреса

Массив и индекс

Все задачи занятия работают со списком Python, а список устроен как массив: элементы лежат в памяти подряд, одним непрерывным блоком, в ячейках одинакового размера. Поэтому адрес любой ячейки вычисляется по её номеру: адрес = начало + индекс × размер ячейки.

Шаги за пять дней: день 0 в первой ячейке, день 4 в последней. Нажмите на ячейку, чтобы увидеть расчёт.

Адреса условные: настоящее начало блока в каждом запуске своё. Под ячейкой — индекс слева направо и отрицательный индекс справа налево, о нём экран 6.

Часть 1 · список Python · определение

Список Python хранит ссылки

Формула адреса требует ячеек одного размера, а число, строка и другой список занимают разное место. Список Python решает это так: в ячейках лежат не сами объекты, а ссылки на них.

Часть 1 · цена доступа

Доступ по индексу за O(1), поиск по значению за O(n)

Из формулы адреса следует цена операций. По индексу адрес вычисляется одним умножением и одним сложением при любой длине списка. По значению формулы нет: чтобы найти 10 500, элементы сравниваются по порядку.

Решения раздела строятся на этом различии: алгоритм обращается к элементам по индексу, а поиск по значению внутри цикла не используется, потому что превращает O(n) в O(n²).

Часть 1 · отрицательный индекс · выход за границы

Отрицательный индекс и IndexError

Индекс -k перед вычислением адреса заменяется на len(a) - k, поэтому a[-1] стоит столько же, сколько a[4]. У списка длины n допустимы индексы от -n до n - 1. Любой другой не соответствует ни одной ячейке: программа останавливается и показывает строку.

>>> a = [10, 20, 30, 40, 50]
>>> a[4], a[-1]
(50, 50)
>>> a[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range

Где опасно: если индекс вычисляется в цикле и случайно стал −1, ошибки не будет — вернётся последний элемент. В ошибочной версии задачи 2 правый указатель доходит до −1, экран 27.

Часть 1 · выход за границы · срез

Срез за границами списка: без ошибки

Со срезом Python поступает иначе, чем с индексом. Границы среза обрезаются до диапазона [0, len(a)], и исключения нет. Поэтому ошибка в границе среза не останавливает программу: результат просто оказывается короче.

>>> a = [10, 20, 30, 40, 50]
>>> a[1:3], a[3:10], a[10:20]
([20, 30], [40, 50], [])

Поэтому ошибку границы в срезе обнаруживает только тест, который сравнивает ответ с ожидаемым.

Часть 2 · границы · срез и полуинтервал

Срез и полуинтервал [l, r)

Срез a[l:r] — новый список из элементов с индексами от l до r - 1. Python копирует в него ссылки на элементы участка: время и память O(r − l). Поэтому в решениях на O(1) памяти срезы внутри цикла не используют. Левая граница входит в срез, правая нет — у такой записи есть название.

Часть 2 · полуинтервал · три следствия

Три следствия полуинтервала

Запись [l, r) выбрана не случайно: с ней три частых действия с участками записываются без поправок на единицу.

days[0:5]  # 5 − 0 = 5 дней
days[5:7]  # 7 − 5 = 2 дня

a[:k] + a[k:] == a
a[:l] + a[l:r] + a[r:] == a

days[3:3]          # []
list(range(3, 3))  # []
days[7:]           # []

Часть 2 · демонстрация · границы среза

Демонстрация: границы среза

Все три следствия видны, если нарисовать границы между ячейками. Граница 0 стоит перед первым элементом, граница n — после последнего. Нажмите на две границы: первая станет l, вторая r. Проверьте длину, склейку и пустой участок кнопкой a[3:3].

Часть 2 · число итераций

Элементы, границы, пары, окна: сколько итераций

На демонстрации у восьми элементов было девять границ — как у забора: четыре пролёта стоят на пяти столбах. Цикл перебирает элементы, границы, пары соседей или окна, и число итераций у них разное: оно равно числу начальных позиций.

Часть 2 · ошибки на единицу · в циклах, индексах и срезах

Шесть частых ошибок на единицу

Первые три строки — неверное число итераций: элементы вместо пар, окна без последнего, список без первого элемента. Последние три — неверная граница в одном обращении: путают длину с последним индексом и включённую границу из условия с невключённой в срезе.

Последняя строка — одна из задач домашнего задания: ошибка в ней не даёт исключения, её находит только тест с n больше длины.

Часть 2 · крайние входы

Пустой и короткий вход

Ошибки на единицу чаще всего проявляются на самых коротких списках. Таблица показывает, что делают частые выражения на пустом списке, на одном и на двух элементах.

Пустой вход падает только там, где код обращается к конкретному элементу до цикла: a[0], a[-1], max(a). Циклы и срезы на пустом списке работают.

Часть 3 · инвариант прохода · определение и три проверки · возврат к занятию 5

Инвариант прохода

Инвариант прохода — утверждение о переменных цикла, которое верно перед первой итерацией и остаётся верным после каждой. Обычно он звучит так: «переменная X хранит такую-то величину для просмотренной части a[0:i]». Из инварианта следуют начальные значения, тело цикла и ответ. На занятии 5 инвариант проверялся на готовом коде, здесь по нему пишется код. Самый короткий пример — сумма цен в корзине.

def total(prices):
    s = 0            # s == sum(prices[0:i])
    for i in range(len(prices)):
        s += prices[i]
    return s

Часть 3 · задача 1 · решение

Решение задачи 1

В сумме хватало одной переменной, здесь нужны две: cur — длина серии, которая заканчивается на текущем дне, и best — лучшая серия среди просмотренных дней. На дне без цели cur обнуляется, а best помнит лучшую. Выделенные строки — обновление best сразу после роста серии.

def max_streak(steps, goal=10_000):
    best = 0   # лучшая серия среди дней с 0 по i
    cur = 0    # серия, которая заканчивается на i
    for s in steps:
        if s >= goal:
            cur += 1
            if cur > best:
                best = cur
        else:
            cur = 0
    return best

Часть 3 · типичная ошибка

Ошибка: best обновляется только при обрыве серии

Частая версия переносит обновление best в ветку else: лучшая серия запоминается, когда текущая оборвалась. Если за последней серией нет дня без цели, ветка else для неё не выполнится.

for s in steps:
    if s >= goal:
        cur += 1
    else:
        best = max(best, cur)
        cur = 0
return best

Часть 4 · задача 2 · решение

Решение задачи 2

Сначала проверка границ, потом цикл обменов. Инвариант описывает, что лежит снаружи необработанной середины: там всё уже на итоговых местах.

def reverse_segment(tracks, l, r):
    if not (0 <= l <= r < len(tracks)):
        raise ValueError("неверные границы")
    i, j = l, r
    while i < j:
        tracks[i], tracks[j] = tracks[j], tracks[i]
        i += 1
        j -= 1

Часть 4 · сравнение способов

Способы развернуть участок

Тот же участок можно развернуть одной строкой со срезом. По времени способы одинаковы, по памяти — нет: срез создаёт копию участка, об этом был экран 8.

В рабочем коде строка со срезом читается проще, и при небольших k копия занимает мало памяти. На собеседовании условие «без срезов» ставят, чтобы проверить работу с индексами: где стоят границы, когда остановиться, что происходит при чётной длине.

Часть 5 · снимок Python Tutor

Присваивание не копирует список

В Python изменение на месте видно не только внутри функции. Переменная хранит ссылку, поэтому backup = feed копирует ссылку, и обе переменные указывают на один список. Функция получает ту же ссылку, удаляет последний элемент, и изменение видно через backup.

Строка	Что происходит
4	создан список из трёх комментариев, feed ссылается на него
5	backup получает ту же ссылку
6	drop_last получает ссылку в параметре comments и вызывает pop()
7	печать backup — два элемента
8	feed is backup — True: объект один

Часть 5 · копия списка

Как получить отдельный список

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

В тестах занятия проверяется обратное: same = comments до вызова и same is comments после. Так тест убеждается, что функция изменила тот же объект и не подменила его новым.

Часть 5 · контракт функции

Контракт функции, которая меняет список

Раз функция может менять вход, в контракте записывают, что она возвращает. В Python и в задачах собеседований встречаются три варианта, и в трёх задачах занятия есть все три.

Часть 6 · задача 3 · условие и ограничения

Задача 3: удаление спама на месте

Третья задача возвращает к коду из начала занятия. Модерация получает список комментариев, спам — комментарий со ссылкой, функция is_spam уже написана. Нужно удалить спам из того же списка, сохранить порядок остальных и вернуть их число. Ограничения исключают два очевидных решения: новый список нарушает требование к памяти, удаление по одному — к времени.

Часть 6 · разбор версии с del

Разбор версии с del по индексу

Теперь есть всё, чтобы объяснить вторую версию из начала занятия. range(len(comments)) вычисляется один раз до цикла, а длина списка после каждого del уменьшается. Индексы цикла и индексы элементов перестают совпадать.

Следующий экран показывает это на тех же четырёх комментариях. Нарушено утверждение «каждый элемент проверен ровно один раз».

Часть 6 · демонстрация · версия с del

Демонстрация: удаление по индексу в цикле

Красная рамка — элемент, который сдвинулся на проверенную позицию и был пропущен. Следите за столбцом len: он уменьшается, а i продолжает расти до 3.

Часть 6 · разбор версии с remove()

Разбор версии с remove() в цикле for

Первая версия не использует индексы явно, но ошибается по той же причине. Цикл for text in comments хранит внутренний номер текущей позиции и на каждом шаге увеличивает его на 1. remove() сдвигает хвост, и следующий элемент оказывается на уже пройденной позиции.

Итог совпадает с выводом на экране 2: ['Отличный урок', 'http://prize.ru', 'Спасибо']. Правило для обеих версий: список не меняют по длине во время прохода по нему.

Часть 6 · демонстрация · remove_spam

Демонстрация: удаление на месте

Семь комментариев, три из них спам. Зелёная зона — готово, штриховка — мусор, бледные ячейки — не просмотрено. Обычный комментарий переписывается в позицию w, спам остаётся в мусоре. В последнем кадре хвост обрезается одной операцией.

Часть 6 · задача 3 · решение

Решение задачи 3

Код записывает демонстрацию: один проход указателем r, запись по w, одна обрезка хвоста после цикла. Три проверки инварианта — справа.

def remove_spam(comments):
    w = 0
    for r in range(len(comments)):
        if not is_spam(comments[r]):
            comments[w] = comments[r]
            w += 1
    del comments[w:]
    return w

Часть 6 · сравнение способов · оценка и замер · Python 3.12, медиана 7 запусков, 30 % спама

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

Две версии из начала занятия дают неверный результат: remove() в for text in comments пропускает спам, del comments[i] в for i in range(len(...)) падает с IndexError. Верные способы сравнены по оценке и замером на списках из 10³, 10⁴ и 10⁵ элементов.

Замер на ноутбуке автора, time.perf_counter(), копия входа создаётся вне замера. На другой машине числа будут другими, соотношение сохранится.

Часть 6 · вариант условия

Удаление без сохранения порядка

Если условие не требует сохранять порядок, удаляемый элемент можно заменить последним из непроверенных. Число записей тогда равно числу удалённых комментариев. Вариант выгоден, когда спама мало.

def remove_spam_unordered(comments):
    i, n = 0, len(comments)
    while i < n:
        if is_spam(comments[i]):
            n -= 1
            comments[i] = comments[n]
            # i не двигается: на место i пришёл
            # непроверенный элемент
        else:
            i += 1
    del comments[n:]
    return n

Часть 7 · динамический массив · определение

Динамический массив: размер и ёмкость

Список умеет расти: append добавляет элемент в конец. Блок при этом должен остаться непрерывным, иначе формула адреса перестанет работать. Если за последней ячейкой места нет, выделяется блок больше и все ссылки копируются в него — это O(n). Если бы так было при каждом append, n добавлений стоили бы O(n²). Python этого избегает: память выделяется с запасом.

Часть 7 · эксперимент · sys.getsizeof

Замер ёмкости через sys.getsizeof

Ёмкость из Python не видна, но её можно вычислить: sys.getsizeof возвращает размер объекта списка — 56 байт заголовка и 8 байт на каждую выделенную ячейку, без самих объектов. Программа печатает строку, когда размер изменился.

import sys

lst = []
prev = sys.getsizeof(lst)
print(0, prev)
for i in range(1, 33):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev:
        print(i, size, (size - 56) // 8)
    prev = size

0 56
1 88 4
5 120 8
9 184 16
17 248 24
25 312 32

Часть 7 · исходник · CPython 3.12, Objects/listobject.c

Формула запаса в функции list_resize

Последовательность 4, 8, 16, 24, 32 из замера задана в исходнике интерпретатора. Функция list_resize вызывается при каждом изменении длины списка и решает, нужен ли переезд и какой будет новая ёмкость.

55–59	если новая длина помещается в выделенную память и не меньше её половины, меняется только поле размера: переезда нет
67	последовательность ёмкостей 0, 4, 8, 16, 24, 32, 40, 52… — та же, что в замере
71	newsize + newsize / 8 + 6, округлённое вниз до кратного 4: запас около 12,5 % плюс константа
63–65	комментарий разработчиков: запаса достаточно для линейного общего времени длинной серии append

Переезд выполняет PyMem_Realloc. Если за блоком свободно, система расширяет его без копирования; если нет — копирует в новый. Анализ считает худший случай, копирование.

Часть 7 · демонстрация · стоимость append

Демонстрация: стоимость append

Стоимость одного append считается в операциях: 1 запись, а при переезде ещё копирование всех элементов. Добавьте 64 элемента в каждом из трёх режимов и сравните линию среднего. При запасе, пропорциональном размеру, она выходит на константу. Без запаса переезд идёт на каждом вызове, и среднее растёт вместе с n.

Часть 7 · амортизированная стоимость · расчёт и сравнение режимов

Расчёт: удвоение, запас ⅛ и рост без запаса

Проще всего посчитать режим «удвоение»: ёмкость растёт 1, 2, 4, 8…, переезд происходит, когда размер достигает степени двойки, и копируется столько элементов, сколько было в списке. Числа совпадают с демонстрацией.

Для КТП достаточно объяснения: отдельный переезд дорогой, но запас растёт пропорционально размеру, поэтому переезды редкие и их суммарная цена распределяется по всем вызовам.

Домашнее задание № 7 · порядок сдачи

Куда положить и как сдать

Про ИИ: код и тесты пишете сами — на занятии 8 решение объясняется без подсказок. Оформление .md и редактуру формулировок можно поручить модели. Я сам так делаю всегда, поэтому и вам запрещать не буду.