Коротко — алгоритмы и их поведение.
Алгоритмы
- Сортировка: собрать список всех слов (длина списка $n$), отсортировать, затем один проход подсчитать переходы между соседями.
- Хеш-таблица (set/dict): для каждого слова вставлять в хеш-таблицу, итог — размер таблицы (количество уникальных слов $u$).
Сложность времени
- Сортировка: $O(n\log n)$ сравнений; при сравнении строк каждая операция может стоить $\Theta (\ell )$ (длина слова), поэтому реальная стоимость $O(n\log n\cdot \ell )$.
- Хеш-таблица: среднее $O(n)$ хешей/сравнений (реальная — $O(n\cdot \ell )$), худший случай при коллизиях — $O(n^2)$ для плохой хеш-функции/атаки.
Память
- Сортировка: нужно хранить список всех ссылок на слова — $O(n)$ ссылок; сортировка in-place может требовать дополнительно $O(\log n)$ или $O(n)$ вспомогательной памяти в зависимости от алгоритма. Если слова хранятся как отдельные строки, каждое слово уже занимает память независимо от метода.
- Хеш-таблица: требует памяти для $u$ записей плюс резерв (load factor), обычно реальная память для таблицы $\sim c\cdot u$ где $c\approx 2\text{–}3$ (включая указатели/метаданные). Если $u\ll n$ (много повторов), то хеш выигрывает по памяти, т.к. не хранит дубликаты. Если $u$ близко к $n$, хеш часто использует больше памяти, чем упакованный массив ссылок.
Практическая производительность (малые и большие тексты)
- Малые тексты (например $n\le 10^5$ слов): разница невелика; хеш-таблица обычно быстрее из‑за линейного профиля и отсутствия логарифмического множителя, но накладные расходы на инициализацию и хеширование могут нивелировать преимущество при очень маленьких $n$. Сортировка может выигрывать, если весь массив и строки располагаются компактно в памяти.
- Очень большие тексты (например $n\ge 10^7$): обычно хеш быстрее по времени (линейное поведение), но:
- память хеша может стать лимитом (резерв/реаллоцирование); если $u$ велик — хеш потребует существенно больше RAM;
- сортировка списка всех слов требует хранения $n$ ссылок и работы $O(n\log n)$ — медленнее, но позволяет использовать внешнюю сортировку (disk-based) с контролируемым использованием RAM.
Рекомендация: при достаточно RAM используйте хеш; при ограниченной RAM — внешняя сортировка или потоковые/дифференцируемые методы.
Влияние кэш-памяти и GC
- Кеш: массив ссылок и алгоритмы сортировки (особенно сравнение/свопы по индексам) часто имеют лучшую локальность данных, что улучшает скорость за счёт меньшего числа кеш-промахов. Хеш-таблица чаще дает «рандомный» доступ → больше кеш-промахов и медленнее память-ввиду случайной адресации. Современные реализации (open addressing) стараются улучшить локальность, но всё равно хуже упорядоченных массивов.
- GC (в языках с GC, Python/Java/.NET):
- Хеш-подход создаёт/удерживает множество хеш-записей и внутренних структур, вызывает больше аллокаций и потенциально сильнее нагружает GC (перераспределения при росте таблицы).
- Сортировка оперирует списком ссылок; если слова уже аллоцированы, дополнительных долгоживущих аллокаций может быть меньше. Но сортировка требует дополнительной временной памяти и временные объекты (в некоторых реализациях) — тоже нагрузка на GC.
- Реаллоцирование хеш-таблицы приводит к пикам аллокаций/копирований и может вызвать паузы.
Практические советы
- Если RAM достаточна и нужна простота/скорость — используйте хеш-таблицу (set).
- Если много повторов ($u\ll n$) — хеш особенно выгоден по времени и памяти.
- Если RAM ограничена или $n$ экстремально велико — используйте внешний/дисковый подход: сортировка на диске или потоковое агрегирование (sharding, частичные подсчёты), либо приближённые структуры (HyperLogLog/Bloom) для оценки количества уникальных.
- В языках с GC: минимизируйте количество короткоживущих аллокаций (интернируйте строки, переиспользуйте буферы), заранее резервируйте ёмкость контейнеров, чтобы избежать частых ресайзов.
Кратко: асимптотически хеш $O(n)$ быстрее сортировки $O(n\log n)$; на практике выбор зависит от доступной памяти, распределения уникальных слов, влияния кеша и поведения GC.