averov90 / word-frequrency

One of the types of tasks that the programmer faces quite often. Here is one of the optimal algorithms for solving it.

Word Frequrency

🔸 English version

Данный код позволяет выстроить рейтинг слов по частоте употребления в исходном тексте, который должен находиться в файле text.txt в исходной папке (папке, в которой находится программа).
Для подсчёта частоты используется опитимизированная под данную задачу структура unordered dictionary. Благодаря использованию структуры вместо прохода по массиву циклом, удаётся значимо ускорить программу. Под конкретную ситуацию может быть изменён порог создания нового блока (UD_BLOCK_THRESHOLD), а так же размер блока структуры (по умолчанию - 1024 слова). Так же может появиться необходимость замены хэш-функции т.к. текущая была выбрана из соображений скорости вычисления на большом числе архитектур (в том числе, и микроконтроллеры) и сравнительно приемлемой частоте коллизий.
Выигрыш алгоритма unordered dictionary в этой ситуации заключается в отсутствии необходимости прохода по массиву слов в поиске нужного - сначала от слова вычисляется хэш-функция (эффективность - O(1)), а затем это значение используется как индекс в хэш-таблице (эффективность - O(1), в худшем случае - O(B * N), где B - количестов блоков, N - число слов в каждом блоке). Вероятности худшего случая (и близкого к нему) в эффективности хэш-таблиц крайне мала, поэтому наиболее часто будет эффективность O(1). Худший случай хэш-таблицы эквивалентен худшему случаю массива (у массива эффективность O(n)).

Формат файла

Для работы программы с файлов в нём должен быть набор слов, разделённых следующими знаками препинания: .,:;-?!"() или пробелом, или переносом строки. После последнего слова так же должен стоять знак препинания. Любое число знаков препинания может стоять подряд. Вы можете поправить правила определения знака препинания без особых проблем в коде программы (в switch).

Пример:

hello, hello,some.test here?