Анализ исходного кода
def dedup(items):
result = []
for x in items:
if x not in result:
result.append(x)
return result
- Временная сложность: в худшем случае (все элементы уникальны) проверка `x not in result` каждый раз сканирует `result`, поэтому суммарно $\mathcal{O}(1+2+\cdots +n)=\mathcal{O}(n^2)$.
- Пространственная сложность: дополнительная память для `result` — в худшем случае хранится все уникальные элементы, т.е. $\mathcal{O}(n)$.
- Замечания: стоимость сравнения элементов может быть не $\mathcal{O}(1)$ (зависит от типа). При больших входных данных $\mathcal{O}(n^2)$ делает функцию непригодной.
Проблемы на больших данных
- Очень медленно при больших $n$ (особенно $n\gtrsim 10^5$ и выше).
- Если элементы не хешируемы, приходится оставлять линейные проверки (или конвертировать), что дорого.
- Память растёт с числом уникальных элементов (может не влезать в ОЗУ).
Альтернативы (с оценками, плюсы/минусы)
1) Сохраняем порядок, используем множество для отслеживания (hashable элементы)
- Код:
def dedup(items):
seen = set()
result = []
for x in items:
if x not in seen:
seen.add(x)
result.append(x)
return result
- Время: в среднем $\mathcal{O}(n)$ (по амортизированной стоимости операций множества).
- Память: $\mathcal{O}(n)$ для `seen` + `result`.
- Плюсы: быстро, сохраняет порядок первых вхождений.
- Минусы: требует хешируемых элементов; в теории возможен деградированный случай до $\mathcal{O}(n^2)$ при плохих коллизиях (на практике редкость).
2) Однострочник для Python 3.7+: сохранить порядок
- Код: `list(dict.fromkeys(items))`
- Время: в среднем $\mathcal{O}(n)$.
- Плюсы: коротко, эффективно.
- Минусы: как и предыдущий — требует хешируемых ключей (или годной хеш-функции).
3) Не требуется порядок — просто множество
- Код: `set(items)`
- Время: в среднем $\mathcal{O}(n)$.
- Память: $\mathcal{O}(n)$.
- Плюсы: максимально просто и быстро.
- Минусы: порядок теряется; элементы должны быть хешируемы.
4) Потоковая/ленивая обработка (генератор), сохраняем порядок
- Код:
def dedup_stream(items):
seen = set()
for x in items:
if x not in seen:
seen.add(x)
yield x
- Время: в среднем $\mathcal{O}(n)$.
- Память: $\mathcal{O}(u)$, где $u$ — число уникальных элементов (может быть всё те же $\mathcal{O}(n)$).
- Плюсы: можно начать выдавать результаты сразу, подходит для больших потоков.
- Минусы: всё равно хранит `seen`; если уникальных много — память растёт.
5) При ограниченной памяти: приближённый дедуп (Bloom filter)
- Идея: вместо полного `seen` хранить Bloom-фильтр; при первом вхождении проверять и добавлять; фильтр даёт ложные срабатывания (удаляет некоторые уникальные элементы).
- Время: $\mathcal{O}(1)$ на элемент. Память: значительно меньше, зависит от допустимой вероятности ложных срабатываний.
- Плюсы: экономия памяти, потоковая.
- Минусы: вероятностный — возможны пропуски уникальных элементов (false positives); нельзя удалить и получить точный результат.
6) Внешняя обработка для очень больших данных (диск)
- Варианты: внешняя сортировка + проход по отсортированным записям (убирает соседние дубликаты), или хеш-партицирование на файлы и дедуп в каждой партиции.
- Время: примерно $\mathcal{O}(n\log n)$ (сортировка) или зависит от I/O при партицировании; память на диске $\mathcal{O}(n)$.
- Плюсы: позволяет точно дедупать данные, превышающие ОЗУ.
- Минусы: сложнее в реализации, интенсивный I/O, может не сохранить исходный порядок (для сохранения первого вхождения нужна дополнительная логика).
7) Нехешируемые объекты
- Варианты: преобразовать в хешируемую форму (tuple, frozenset, json.dumps с сортировкой ключей) и применять `seen`-подход; или использовать equality-based методы (медленнее).
- Плюсы/минусы: трансформация может быть дорогой или невозможна (сложные структуры); equality-подход медленный.
Рекомендации
- Для большинства задач, когда элементы хешируемы и нужно сохранить порядок: используйте `seen=set()` + результат или `list(dict.fromkeys(items))` (в среднем $\mathcal{O}(n)$, память $\mathcal{O}(n)$).
- Для потоковой обработки с ограничением времени — генератор с `seen`.
- Если память критична и точность не обязательна — Bloom filter.
- Для точного дедупа при данных, не помещающихся в ОЗУ — внешняя сортировка или партицирование на диск.
Если нужно, могу привести конкретные реализации для каждого варианта или оценить параметры Bloom-фильтра / партиционирования для вашего объёма данных.