Указатели в одну сторону:
повторы и сжатие

Категория

Алгоритм

Уровень

Начальный

Опирается на

Занятие 7: удаление спама на месте, три зоны списка

Зачем это знать

Менять список на месте за один проход без дополнительной памяти

§1Чтение и запись в одном списке

В задаче про спам из занятия 7 уже использовались два указателя в одну сторону. Указатель чтения r проходит все элементы по порядку, по одному разу. Указатель записи w показывает, куда встанет следующий элемент, который нужно оставить. Список при этом делится на три зоны: [0, w) — готовый результат, собранный из прочитанной части; [w, r) — пропущенные элементы и старые копии; [r, n) — то, что ещё не прочитано. В ручном упражнении ниже и в прогонах зоны раскрашены: готовое — зелёным, пропущенное — штриховкой.

Всегда w ≤ r: записывается не больше, чем прочитано. Поэтому запись попадает в уже прочитанную часть и не затирает элементы, до которых r ещё не дошёл. После цикла мусор обрезается одной операцией del a[w:]. Время O(n), дополнительная память O(1).

Задачи этой формы отличаются только правилом «оставить или пропустить» и тем, что пишется в позицию w. Разберём две.

§2Задача 2: удаление повторов

Список отсортирован, поэтому одинаковые значения стоят подряд. Это позволяет обойтись одним сравнением: прочитанное значение сравнивается только с последним записанным ids[w - 1]. Если оно другое — это новое значение, и раньше в списке его не было: иначе оно стояло бы рядом с такими же. Если равное — это повтор, его пропускаем.

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

1. Прочитать. Взять элемент ids[r] и сравнить его с последним записанным ids[w - 1].
2. Новое значение. Если они различаются, записать ids[r] в позицию w и сдвинуть w на одну позицию вправо.
3. Повтор. Если равны, ничего не записывать, w остаётся на месте.
4. Следующий. Сдвинуть r вправо и повторить, пока список не прочитан.
5. Хвост. После прохода удалить всё начиная с позиции w и вернуть w — число различных значений.

§3Удаление повторов вручную

Сделайте проход сами. На каждом шаге прочитан элемент ids[r], и нужно решить, записать его в позицию w или пропустить. Неверное решение не выполняется, вместо него появляется объяснение. Зелёная зона — готовый результат, штриховка — пропущенные повторы и старые копии.

§4Сборка dedup_sorted из строк

Правило из §2 записывается функцией из десяти строк. Расставьте их по порядку: сначала проверка пустого списка и начальное w, затем цикл по r с правилом записи, после цикла — обрезка хвоста. Потом напишите функцию сами в песочнице ниже.

>>> not []
True
>>> not [5]
False

>>> ids = [101, 102, 105, 110, 105, 110]
>>> del ids[4:]
>>> ids
[101, 102, 105, 110]

Напишите функцию сами в окне ниже. «Запустить тесты» проверяет её на пяти входах, как в песочнице главы 8.4; часть из них заготовка проходит сразу.

§5Код и прогон задачи 2

def dedup_sorted(ids):
    if not ids:
        return 0
    w = 1
    for r in range(1, len(ids)):
        if ids[r] != ids[w - 1]:
            ids[w] = ids[r]
            w += 1
    del ids[w:]
    return w

Прогон ниже — на примере из условия. Зелёная зона — готовый результат, штриховка — пропущенные повторы и старые копии.

В задаче 1 пустой список обрабатывался без отдельного if, а здесь проверка if not ids нужна. Причина в начальном значении w = 1: оно означает, что первый элемент уже оставлен. В пустом списке первого элемента нет. Цикл for r in range(1, 0) не выполнится ни разу, и без проверки функция вернёт 1 — одно различное значение в пустом списке. Обе версии запущены на пустом списке.

§6Задача 3: сжатие последовательности

Такой способ записи называется кодированием длин серий, по-английски run-length encoding или RLE. Он выгоден, когда в данных много длинных серий, — например, в изображениях с большими одноцветными областями.

Отличие от задачи 2 в том, что за один шаг читается целая серия. Указатель start запоминает начало серии, внутренний цикл двигает r до первого другого символа. Длина серии — r − start. Затем в позицию w пишется символ и, если серия длиннее одного символа, её длина по цифрам.

1. Начало серии. Запомнить start = r — позицию первого символа серии.
2. Конец серии. Двигать r вправо, пока символ тот же и список не кончился.
3. Символ. Записать символ серии в позицию w, сдвинуть w.
4. Длина. Если серия длиннее одного символа, записать цифры числа r − start по одной, каждый раз сдвигая w.
5. Дальше. Повторять, пока r не дойдёт до конца; затем удалить хвост с позиции w и вернуть w.

Так правило срабатывает на примере list("aaabcc"). Каждая строка таблицы — одна серия:

После трёх серий w = 5, хвост с позиции 5 удаляется, результат ['a', '3', 'b', 'c', '2'].

§7Сборка compress из строк

В функции два цикла: внешний идёт по сериям, внутренний двигает r до конца текущей серии. Расставьте семнадцать строк по порядку, сверяясь с правилом выше, затем напишите функцию сами.

>>> list("abc")
['a', 'b', 'c']
>>> str(12)
'12'
>>> for d in str(12):
...     print(d)
...
1
2

Напишите функцию сами в окне ниже. «Запустить тесты» проверяет её на пяти входах, как в песочнице главы 8.4; часть из них заготовка проходит сразу.

§8Код и прогон задачи 3

def compress(chars):
    w = 0
    r = 0
    n = len(chars)
    while r < n:
        start = r
        while r < n and chars[r] == chars[start]:
            r += 1
        chars[w] = chars[start]
        w += 1
        count = r - start
        if count > 1:
            for d in str(count):
                chars[w] = d
                w += 1
    del chars[w:]
    return w

Во внутреннем цикле порядок условий важен: r < n проверяется первым. Когда серия доходит до конца списка, r становится равным n, и обращение chars[r] дало бы IndexError. Оператор and не вычисляет второе условие, если первое ложно.

>>> chars = ["a"]
>>> r = 1
>>> r < len(chars) and chars[r] == "a"
False
>>> chars[r]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range

Если поменять условия местами — while chars[r] == chars[start] and r < n:, — функция будет работать, пока серия не дойдёт до конца списка. Обе записи условия запущены на list("aab"): последняя серия b заканчивается на последнем элементе.

Ниже — прогон верной функции. Под ячейками три метки: w — запись, start — начало текущей серии, r — чтение. Зелёная зона — уже записанный результат.

>>> chars = list("aaabccddd")
>>> compress(chars)
7
>>> chars
['a', '3', 'b', 'c', '2', 'd', '3']
>>> x = ["x"] * 12
>>> compress(x)
3
>>> x
['x', '1', '2']

§9Почему запись не обгоняет чтение

В задаче 2 это следует из кода: за шаг читается один элемент и записывается не больше одного. В задаче 3 за шаг пишется символ и несколько цифр, и нужно проверить, что w не окажется правее r и не затрёт непрочитанную серию.

Серия длины c занимает в исходном списке c позиций, а в результате — один символ и количество цифр числа c. Таблица сравнивает эти два числа.

Записанный вариант серии никогда не длиннее исходного. Значит, после обработки каждой серии w ≤ r, и запись идёт в уже прочитанную часть. Так проверяется сохранение инварианта задачи 3: «chars[0:w] — сжатая запись прочитанной части chars[0:r]».

§10Поиск по двум последовательностям

До сих пор указатели в одну сторону шли по одному списку: один читал, другой писал. Та же форма работает и для поиска, когда последовательностей две. Пример — задача о подпоследовательности. Сам термин разбирали в занятии 7: элементы идут в исходном порядке, но между ними могут быть пропуски.

Указатель j идёт по тексту и читает каждую букву. Указатель i показывает следующую нужную букву слова и сдвигается, только когда она нашлась. Оба двигаются только вперёд, поэтому шагов не больше длины текста: время O(len(text)), память O(1).

1. Начало. i = 0: ещё не найдено ни одной буквы слова.
2. Чтение. j проходит все буквы текста по порядку.
3. Совпадение. Если text[j] равна следующей нужной букве word[i], сдвинуть i. Если слово уже найдено целиком, дальше ничего не сравнивать.
4. Ответ. После текста слово получилось, если найдены все его буквы: i == len(word).

Напишите функцию сами в окне ниже. «Запустить тесты» проверяет её на пяти входах, как в песочнице главы 8.4; часть из них заготовка проходит сразу.

def is_subsequence(word, text):
    i = 0
    for j in range(len(text)):
        if i < len(word) and text[j] == word[i]:
            i += 1
    return i == len(word)

В прогонах под ячейками текста стоит указатель j, а i — сколько букв слова уже найдено — видно в таблице переменных.

В условии if две проверки. Первая, i < len(word), нужна для случая, когда все буквы слова уже найдены, а текст ещё не дочитан. Тогда i == len(word), и обращение word[i] выходит за границу слова. Как и в compress, and не вычисляет вторую проверку, если первая ложна. Обе версии запущены на слове «кот» и тексте «котик»: буквы слова кончаются раньше текста.

Остаётся вопрос, почему можно брать первую подходящую букву текста и не проверять другие. Пусть «к» нашлась на позиции 0. Любая другая «к» в тексте стоит правее, и после неё для остальных букв слова остаётся меньше текста. Значит, выбор самой ранней буквы никогда не хуже выбора более поздней, и возвращаться к уже пройденным буквам текста не нужно. Поэтому оба указателя двигаются только вперёд.

§11Проверьте себя