Информатика · объяснение и практика

Почему множество не заменяет упорядоченное удаление повторов

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Переменные, ветвления, циклы и функции · Учебная карта

Главная мысль

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

Почему одинаковый состав не означает одинаковую последовательность

Из списка[4,2,4,1,2] нужен результат[4,2,1]: оставляем первое появление каждого числа. Преобразование в set даёт правильный состав уникальных значений, но возвращать его как обещанную последовательность нельзя. Порядок обхода множества не является гарантией исходного порядка, даже если на одном запуске выглядит удобным.

Сортировка множества дала бы[1,2,4], то есть другой полезный, но иной результат. Сохранение первого появления, сортировка и произвольный порядок уникальных значений — три разных контракта. Перед выбором короткой конструкции следует выяснить, какой нужен пользователю. Тест, сравнивающий только множества, не обнаружит потерю порядка в задаче об упорядоченном выводе.

Как работает проход с памятью встреченных

Начинаем с пустых seen и result. Для каждого элемента исходного списка проверяем, был ли он в seen. Если нет, добавляем в seen и в конец result. Для[4,2,4,1,2] сначала сохраняются 4 и 2, второй 4 пропускается, затем сохраняется 1, последний 2 пропускается. Порядок result определяется обходом исходного списка.

Для хешируемых элементов в современных версиях Python можно также использовать list(dict.fromkeys(items)): словарь сохраняет порядок добавления ключей. Но это свойство словаря, а не множества. Если явно нужен более переносимый или наглядный учебный алгоритм, последовательный проход показывает оба состояния и позволяет объяснить, почему первый экземпляр остаётся, а поздние исчезают.

Пример

Удалите повторы из[3,1,3,2,1] с сохранением первого появления.

Получится[3,1,2]. Число 3 остаётся первым, потому что встретилось раньше 1 и 2. Сортировка[1,2,3] нарушила бы указанное условие.

Что считается одинаковым элементом

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

Для строк отдельно решают, учитывать ли регистр, пробелы и Unicode-нормализацию. «Дом» и«дом» по обычному равенству Python различаются. Если сравнение нормализовано, полезно сохранять исходный первый текст для вывода и отдельно вычислять ключ сравнения. Буквы е иё не становятся одинаковыми от канонической нормализации. Таким образом, удаление дублей требует двух решений: что считать равным и какой представитель оставить, а не одной универсальной команды set.

От чтения к действию

А теперь — вы

Каков результат удаления повторов с сохранением первого появления из[2,5,2,3,5]?

Частые вопросы

sorted(set(items)) сохраняет первое появление?

Нет. Оно сортирует уникальные элементы и тем самым задаёт другой порядок.

Можно ли положить обычный список в set?

Нет. Список изменяемый и нехешируемый; нужен иной ключ или другой алгоритм сравнения.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться