поиск максимумов в хеш-таблице

[FasterHarder]

Всем хай! Сходу к делу!

Есть текст на английском языке. Нужно разбить его на отдельные слова и поместить в хеш-таблицу, которая на цепочках. При этом считается частотность каждого слова ( отдельное поле ). Если слово раньше не встречалось, то оно вставляется в НАЧАЛО цепочки ( вычислительная сложность О(1) этой операции ).

Пусть размер хеш-таблицы = 97( simple number ) - это примерно середина между 2⁶ и 2⁷. Но это не суть, можно и др.параметры взять.

В общем с построением хеш-таблицы проблем 0.0 ( вопросов по хеш-функции нет ).

==========================================

И когда входной текст обработан, сформирована хеш-таблица, то нужно вывести на экран ТОП-5 САМЫХ часто встречающихся слова.

А разве хеш-таблицы имеют какое-то отношение к "упорядоченности" данных?? Нет, разумеется, можно 5 раз ПРОСМОТРЕТЬ ВСЮ хеш-таблицу, помечая каким-то флагом найденные ТОПЫ до текущего, но это вроде не кажется разумным ни разу)

Можно еще отсортировать цепочки по убыванию частотности слов, но тоже как-то все кажется не к месту...
Можно еще при вставке в нужную цепочку ( в зависимости от хеша, получаемого от хеш-функции ) вставлять в упорядоченное место по частотности, но по условию надо вставлять только в начало, если слово раньше не встречалось, поэтому это точно не вариант

============================================

что-то не понимаю, как связать построенную хеш-таблицу с поиском ТОП-5 самых частых слов. Такое чувство, что никак или все-таки...?

спс за внимание

Сообщение отредактировано: FasterHarder - 31.10.24, 23:37

[MBo]

Возможно, подразумевается комплекс мер.

--------
При вставке, если слово новое, проходим всю цепочку, и потом вставляем в начало со счётчиком 1. По сути, обхода цепочки не избежать.

Если слово нашли, увеличиваем счётчик пары в цепочке и сдвигаем пару ближе к концу, если счётчик превысил счётчик следующих - при этом поддерживается упорядоченность цепочек, как ты и написал. Существенно, что эта операция той же сложности, как и предыдущая.

-------
В конце работы создаём кучу/пирамиду max-heap из номеров цепочек по ключу счётчика. Пять раз снимаем с кучи верхний номер, выдавая слово из концевой пары соотв. цепочки.

Если цепочка не опустела - вставляем этот же номер в кучу снова, используя последнюю пару в данной цепочке (она была предпоследней раньше)

-----
P.S. Использование кучи смешно смотрится на таких объёмах (5/97), и пятикратный просмотр концов с таким же удалением будет, вероятно, на практике не хуже

Сообщение отредактировано: MBo - 01.11.24, 03:52

[Akina]

Крайне странное описание. Я в нём в упор не вижу подсчёта количества - вариант "Если слово раньше не встречалось" рассмотрен, а обратный как-то стыдливо проигнорирован. В то время как конечная задача требует именно подсчёта количества вхождений, то есть этот обратный вариант даже более важен.

В качестве решения вижу добавление к полю хэша ещё и поля количества, которое устанавливается равным 1 при начальной вставке и инкрементируется при повторной вставке. Для ускорения процедуры разбора таблица поддерживается сортированной по хэшу. А после завершения подсчёта таблица пересортировывается по полю количества, и можно брать топ-5. Если нужен строго топ-5, то быстрее, вероятно, будет сортировка поля количества с игнорированием записей ниже первых 5 (получаем топ-5 количеств), а затем выборка записей с накопленными количествами и выбор топ-5 уже записей (заодно надо решить, что делать с дубликатами). Это два прохода и дополнительная сортировка массива из 5 значений.

Альтернатива - опять же поле количества, плюс дополнительная структура ссылок на элементы массива, сортированные по этому количеству. Это замедлит начальный разбор, но ускорит финальную обработку. Правда, суммарно будет медленнее первого варианта.

Ну и совсем альтернатива - просто накапливать хэши без оглядки на "уже присутствует", а потом, после обработки текста - сортировка подсчётом.

В любом случае худшие начальные условия - это когда все слова присутствуют в одинаковом количестве.

Сообщение отредактировано: Akina - 01.11.24, 04:44

[Majestio]

Цитата FasterHarder @ 31.10.24, 23:36

но по условию надо вставлять только в начало

Вообще без проблем. Но не нужно от одного "инструмента", который хорошо выполняет свои функции - требовать что-то еще другое, если это функционально не предусмотрено.

Цитата Akina @ 01.11.24, 04:42

А после завершения подсчёта таблица пересортировывается по полю количества

Вот и я говорю Что мешает завести индексацию этой самой хэш-таблицы, периодически ее актуализировать (пересортировывать)? По итогу - хэш-таблица хранит предметные данные, а индекс - хранит упорядоченность.

[FasterHarder]

почитал немного про хеш-таблицы
в общем пришел к выводу, что ХТ вот ни разу не предназначены для выборки каких-то ТОП-данных. Вставка, удаление и поиск ПО КЛЮЧУ - это, да, всегда пожалуйста и быстро

поиск каких-то ТОП данных из ХТ какое-то извращение вообще получается. Есть море более подходящих структур для таких операций ( даже просто массив отсортировать и выбрать нужный ТОП первых слов )

всем спс за участие

[Akina]

Цитата FasterHarder @ 05.11.24, 01:02

пришел к выводу, что ХТ вот ни разу не предназначены для выборки каких-то ТОП-данных.

Ну в общем да. Основное назначение хэша с этой точки зрения - обеспечение сравнительно равномерного распределения в поле возможных значений, когда оригинальные данные такой равномерности не имеют.

[Majestio]

Цитата FasterHarder @ 05.11.24, 01:02

почитал немного про хеш-таблицы
в общем пришел к выводу, что ХТ вот ни разу не предназначены для выборки каких-то ТОП-данных. Вставка, удаление и поиск ПО КЛЮЧУ - это, да, всегда пожалуйста и быстро

Все верно. Во многих языках программирования хэш-таблицы (они же карты, они же map, они же ассоциативные контейнеры) имеют две реализации - обычный хэш, и хэш, отсортированный по ключам. Оба варианта имеют и преимущества, и недостатки в зависимости от контекста использования. Как правило, они разняться по двум критериям "скорость получения элемента по ключу", "скорость записи элемента с ключом". Но в вопросе речь идет о топе значений. Тут, если нет каких-то внешних механизмов индексирования, нужен полный перебор всех элементов хэша, без этого никак.

По поводу ТОПА. Если он подразумевается небольшой - даже и полной индексации хэша не нужно, и даже вредно! Просто дополнительно заводится упорядоченный массив топов, где есть поля: 'значение', 'ключ_из_хэша'. И при каждом занесении очередного элемента в хэш просто актуализируется эта таблица. А это задача быстрая и тривиальная. В таком массиве можно конечно и просто одни 'значения' оставить, но если потом понадобится узнать каким ключам они соответствуют - понадобится полный перебор. И я думаю, это не то место, где следует экономить.