Удаление дубликатов с сохранением порядка

Удаление дубликатов с сохранением порядка

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

Решение 1: С использованием set и сохранением порядка (Python 3.7+)

В Python 3.7+ словари и set сохраняют порядок вставки:

def remove_duplicates(lst):
    """
    Удаляет дубликаты, сохраняя порядок первого появления.
    
    Алгоритм:
    - Используем set как временное хранилище для проверки уникальности
    - Проходим по списку и добавляем элементы, которые не видели ранее
    - dict.fromkeys() сохраняет порядок ключей
    """
    return list(dict.fromkeys(lst))

# Примеры
print(remove_duplicates([1, 2, 2, 3, 1, 4]))           # [1, 2, 3, 4]
print(remove_duplicates(["a", "b", "a", "c", "b"]))   # ["a", "b", "c"]
print(remove_duplicates([1, 1, 1, 1]))                 # [1]
print(remove_duplicates([]))                           # []

Как это работает:

• dict.fromkeys(lst) создаёт словарь, где ключи — элементы списка
• В словаре каждый ключ уникален и сохраняет порядок вставки
• list() преобразует ключи обратно в список

Решение 2: Явный проход с set (самое читаемое)

def remove_duplicates_explicit(lst):
    """
    Явный проход по списку с отслеживанием виденных элементов.
    Наиболее читаемое и понятное решение.
    """
    seen = set()
    result = []
    
    for item in lst:
        if item not in seen:
            result.append(item)
            seen.add(item)
    
    return result

print(remove_duplicates_explicit([1, 2, 2, 3, 1, 4]))  # [1, 2, 3, 4]

Плюсы:

• Очень читаемо и понятно
• Работает с любыми типами данных
• Легко дебажить

Решение 3: Список comprehension (компактное)

def remove_duplicates_comprehension(lst):
    """
    Компактный вариант с list comprehension и set.
    """
    seen = set()
    return [x for x in lst if not (x in seen or seen.add(x))]

print(remove_duplicates_comprehension([1, 2, 2, 3, 1, 4]))  # [1, 2, 3, 4]

# Объяснение:
# seen.add(x) всегда возвращает None (falsy)
# поэтому `x in seen or seen.add(x)` работает как проверка + добавление

Минус: Менее читаемо, используется побочный эффект (add() в условии)

Решение 4: Для работы с неhash-объектами

Если список содержит unhashable типы (списки, словари), нужен другой подход:

def remove_duplicates_unhashable(lst):
    """
    Удаляет дубликаты из списка, содержащего unhashable типы.
    Медленнее, но работает с любыми типами.
    """
    result = []
    
    for item in lst:
        if item not in result:  # O(n) поиск для каждого элемента
            result.append(item)
    
    return result

# Примеры с неhashable типами
print(remove_duplicates_unhashable([[1, 2], [3], [1, 2], [4]]))  
# [[1, 2], [3], [4]]

print(remove_duplicates_unhashable([{"a": 1}, {"b": 2}, {"a": 1}]))  
# [{"a": 1}, {"b": 2}]

Сложность: O(n²), медленнее, но работает с любыми типами

Решение 5: С использованием индексов

def remove_duplicates_index(lst):
    """
    Использует индексы для проверки первого появления.
    """
    return [x for i, x in enumerate(lst) if lst.index(x) == i]

print(remove_duplicates_index([1, 2, 2, 3, 1, 4]))  # [1, 2, 3, 4]

# Как работает:
# lst.index(x) возвращает индекс ПЕРВОГО появления x
# Если текущий индекс равен индексу первого появления, то это первое появление

Минусы:

• O(n²) сложность
• Медленнее других решений
• Используется только для демонстрации

Решение 6: С поддержкой пользовательских функций ключей

def remove_duplicates_with_key(lst, key=None):
    """
    Удаляет дубликаты с поддержкой функции ключа.
    key — функция для извлечения ключа сравнения.
    """
    if key is None:
        return list(dict.fromkeys(lst))
    
    seen = set()
    result = []
    
    for item in lst:
        k = key(item)
        if k not in seen:
            result.append(item)
            seen.add(k)
    
    return result

# Примеры с функцией ключа
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __repr__(self):
        return f"Person({self.name}, {self.age})"

people = [
    Person("Alice", 30),
    Person("Bob", 25),
    Person("Alice", 30),  # дубликат
    Person("Charlie", 35),
]

# Удалить дубликаты по имени
result = remove_duplicates_with_key(people, key=lambda p: p.name)
print(result)  # [Person(Alice, 30), Person(Bob, 25), Person(Charlie, 35)]

# Удалить дубликаты по возрасту
result = remove_duplicates_with_key(people, key=lambda p: p.age)
print(result)  # [Person(Alice, 30), Person(Bob, 25), Person(Charlie, 35)]

Сравнение решений

Бенчмарк производительности

import time

def benchmark(func, lst, iterations=10000):
    start = time.time()
    for _ in range(iterations):
        func(lst)
    return time.time() - start

lst = list(range(100)) * 10  # 1000 элементов с дубликатами

print(f"dict.fromkeys():   {benchmark(remove_duplicates, lst):.4f}s")
print(f"Явный проход:      {benchmark(remove_duplicates_explicit, lst):.4f}s")
print(f"List comprehension: {benchmark(remove_duplicates_comprehension, lst):.4f}s")

# Обычно dict.fromkeys() немного быстрее

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

def deduplicate_users(users):
    """
    Удаляет дубликаты пользователей, сохраняя первое появление.
    """
    seen = set()
    result = []
    
    for user in users:
        user_id = user.get('id')
        if user_id not in seen:
            result.append(user)
            seen.add(user_id)
    
    return result

users = [
    {'id': 1, 'name': 'Alice'},
    {'id': 2, 'name': 'Bob'},
    {'id': 1, 'name': 'Alice'},  # дубликат
    {'id': 3, 'name': 'Charlie'},
]

print(deduplicate_users(users))
# [{'id': 1, 'name': 'Alice'}, {'id': 2, 'name': 'Bob'}, {'id': 3, 'name': 'Charlie'}]

Рекомендация

Для большинства случаев используй:

def remove_duplicates(lst):
    return list(dict.fromkeys(lst))

Это решение:

• Самое быстрое: O(n)
• Компактное и читаемое
• Работает в Python 3.7+
• Сохраняет порядок

Для большей читаемости:

def remove_duplicates(lst):
    seen = set()
    result = []
    for item in lst:
        if item not in seen:
            result.append(item)
            seen.add(item)
    return result

Этот вариант понятнее новичкам и легче дебажится.