Physics.Math.Code: “👨🏻‍💻 Если задача стоит в том, чтобы очистить список от повторяющихс…”

👨🏻‍💻 Если задача стоит в том, чтобы очистить список от повторяющихся элементов, то начиная с Python 3.7+ появляется интересный лайфхак, когда словари сохраняют порядок вставки.

Рассмотрим на принцип работы такого кода:
1. dict.fromkeys(lst) создаёт словарь, где каждый элемент списка становится ключом.
2. Поскольку в словаре ключи уникальны, повторяющиеся элементы автоматически схлопываются.
3. Порядок ключей соответствует порядку их первого появления в исходном списке.
4. Затем list() извлекает ключи обратно в список.

Но зачем тогда нужно множество set() ? Здесь сразу проще привести пример:

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
# Через dict.fromkeys
unique_ordered = list(dict.fromkeys(lst))
print(unique_ordered)  # [3, 1, 4, 5, 9, 2, 6]

# Альтернативы:  set() - но не сохраняет порядок
unique_unordered = list(set(lst))
print(unique_unordered)  # [1, 2, 3, 4, 5, 6, 9] (порядок может быть любым)

⚠️ Этот трюк работает только если элементы списка хешируемы (могут быть ключами словаря) — т.е. неизменяемые типы (int, str, tuple) и не работают с изменяемыми типами (list, set, dict).

lst_with_lists = [[1], [2], [1]]  # TypeError: unhashable type: 'list'
# list(dict.fromkeys(lst_with_lists))  # Ошибка!

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

И тут тоже интересный момент. Сравним сложности алгоритмов.

▪️ Классический вариант (O(n²))

unique_items = []
for i in items:
    if i not in unique_items:
        unique_items.append(i)
print(unique_items)

— В худшем случае (все элементы уникальны): O(n²).
— На каждом шаге проверка i not in unique_items сканирует уже созданный список.
— Для 10 000 элементов → до 50 миллионов сравнений.

▪️ Короткий вариант (O(n))

items = [1, 2, 2, 3, 1]
print(list(dict.fromkeys(items)))

— dict.fromkeys(items): O(n) - один проход для создания словаря
— Поиск/вставка в словаре: O(1) в среднем
— list(): O(n) - ещё один проход

⚙️ Тест производительности:

import timeit

# Подготовка тестовых данных
items = list(range(10000)) + [5000] * 1000  # 11000 элементов

# Классический метод
def classic_method():
    unique = []
    for i in items:
        if i not in unique:
            unique.append(i)
    return unique

# Dict.fromkeys метод
def dict_method():
    return list(dict.fromkeys(items))

# Замер времени
time_classic = timeit.timeit(classic_method, number=100)
time_dict = timeit.timeit(dict_method, number=100)

print(f"Классический: {time_classic:.4f} сек")
print(f"Dict.fromkeys: {time_dict:.4f} сек")
print(f"Dict.fromkeys быстрее в {time_classic/time_dict:.1f} раз")

🖥 На моём AMD Ryzen 5 3600X этот код выдает такой результат:

Классический: 39.9998 сек
Dict.fromkeys: 0.0468 сек
Dict.fromkeys быстрее в 853.9 раз

Почему большая разница в производительности?

➖ Проблема классического метода: постоянное сканирование списка при добавлении каждого нового элемента (1-й элемент: 1 проверка, 2-й элемент: 2 проверки, 10000-й элемент: 10000 проверок)

➕ Преимущество словаря: хеш-таблица в памяти, поиск элемента выполняется за постоянное время O(1), а внутренняя структура оптимизирована на уровне C ( не Python циклы). Нет линейного поиска. #программирование #оптимизация #рефакторинг #алгоритмы #computer_science #задачи

💡 Physics.Math.Code // @physics_lib