Коротко — почему проблемно
- set(a) удаляет дубликаты, но не сохраняет исходный порядок; порядок обхода множества не гарантирован и зависит от хешей/реализации Python. Значит uniq(a) может вернуть элементы в произвольном порядке.
- Требование: все элементы должны быть hashable; для unhashable (напр. списки, dict) set(a) вызовет TypeError.
- Время/память: построение множества обычно быстрое, но имеет накладные расходы памяти.
Какие гарантии даёт исходный код
- Результат: все уникальные элементы из a, тип списка.
- Порядок: НЕ гарантируется (не сохраняется порядок первого появления).
- Сложность: в среднем время $\mathrm{O}(n)$ и память $\mathrm{O}(n)$ (где $n$ = len(a)), при крайне плохих хешах возможна деградация до $\mathrm{O}(n^2)$. Элементы должны быть hashable.
Корректные альтернативы (сохранение порядка и оценка производительности)
1) Самый компактный (Python 3.7+ — dict сохраняет порядок):
list(dict.fromkeys(a))
- Поведение: сохраняет порядок первых вхождений.
- Сложность: в среднем время $\mathrm{O}(n)$, память $\mathrm{O}(n)$.
- Требование: элементы hashable.
2) Явный алгоритм с seen-set:
def uniq_preserve(a):
seen = set()
res = []
for x in a:
if x not in seen:
seen.add(x)
res.append(x)
return res
- Поведение и сложность: как в (1), понятный код.
3) Если элементы не hashable (нельзя использовать set/dict):
def uniq_unhashable(a):
res = []
for x in a:
if x not in res:
res.append(x)
return res
- Сложность: время $\mathrm{O}(n^2)$, память $\mathrm{O}(n)$. Подходит только для небольших входов.
4) Если нужен отсортированный список уникальных элементов:
sorted(set(a))
- Поведение: уникальность + сортировка.
- Сложность: построение множества $\mathrm{O}(n)$ + сортировка $\mathrm{O}(k\log k)$, итого $\mathrm{O}(n+k\log k)$, где $k$ — число уникальных элементов.
Практические замечания для больших входов
- set/dict дают лучшую производительность ($\mathrm{O}(n)$ средне), но требуют памяти примерно $\mathrm{O}(n)$ с заметной константой (каждая запись имеет накладные расходы).
- Для миллионов элементов следите за оперативной памятью; при нехватке памяти можно использовать внешние/стриминговые алгоритмы или сортировку на диске.
- Избегайте алгоритмов $\mathrm{O}(n^2)$ для больших n.
Итого: если нужно сохранить порядок — используйте list(dict.fromkeys(a)) или явный seen-set; если элементы не hashable — используйте алгоритм с проверкой в списке (но он медленный).