Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912693 Tue, 05 Nov 2024 08:45:02 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912693 Цитата FasterHarder @
почитал немного про хеш-таблицы
в общем пришел к выводу, что ХТ вот ни разу не предназначены для выборки каких-то ТОП-данных. Вставка, удаление и поиск ПО КЛЮЧУ - это, да, всегда пожалуйста и быстро

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

По поводу ТОПА. Если он подразумевается небольшой - даже и полной индексации хэша не нужно, и даже вредно! Просто дополнительно заводится упорядоченный массив топов, где есть поля: 'значение', 'ключ_из_хэша'. И при каждом занесении очередного элемента в хэш просто актуализируется эта таблица. А это задача быстрая и тривиальная. В таком массиве можно конечно и просто одни 'значения' оставить, но если потом понадобится узнать каким ключам они соответствуют - понадобится полный перебор. И я думаю, это не то место, где следует экономить.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912672 Tue, 05 Nov 2024 04:24:40 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912672 Цитата FasterHarder @
пришел к выводу, что ХТ вот ни разу не предназначены для выборки каких-то ТОП-данных.

Ну в общем да. Основное назначение хэша с этой точки зрения - обеспечение сравнительно равномерного распределения в поле возможных значений, когда оригинальные данные такой равномерности не имеют.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912671 Tue, 05 Nov 2024 01:02:49 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912671 в общем пришел к выводу, что ХТ вот ни разу не предназначены для выборки каких-то ТОП-данных. Вставка, удаление и поиск ПО КЛЮЧУ - это, да, всегда пожалуйста и быстро

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

всем спс за участие]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912569 Fri, 01 Nov 2024 10:47:04 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912569 Цитата FasterHarder @
но по условию надо вставлять только в начало

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

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

Вот и я говорю ;) Что мешает завести индексацию этой самой хэш-таблицы, периодически ее актуализировать (пересортировывать)? По итогу - хэш-таблица хранит предметные данные, а индекс - хранит упорядоченность.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912532 Fri, 01 Nov 2024 04:42:36 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912532
В качестве решения вижу добавление к полю хэша ещё и поля количества, которое устанавливается равным 1 при начальной вставке и инкрементируется при повторной вставке. Для ускорения процедуры разбора таблица поддерживается сортированной по хэшу. А после завершения подсчёта таблица пересортировывается по полю количества, и можно брать топ-5. Если нужен строго топ-5, то быстрее, вероятно, будет сортировка поля количества с игнорированием записей ниже первых 5 (получаем топ-5 количеств), а затем выборка записей с накопленными количествами и выбор топ-5 уже записей (заодно надо решить, что делать с дубликатами). Это два прохода и дополнительная сортировка массива из 5 значений.

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

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

В любом случае худшие начальные условия - это когда все слова присутствуют в одинаковом количестве.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912531 Fri, 01 Nov 2024 03:42:03 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912531
--------
При вставке, если слово новое, проходим всю цепочку, и потом вставляем в начало со счётчиком 1. По сути, обхода цепочки не избежать.

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

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

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

-----
P.S. Использование кучи смешно смотрится на таких объёмах (5/97), и пятикратный просмотр концов с таким же удалением будет, вероятно, на практике не хуже]]> MBo Алгоритмы https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912530 Thu, 31 Oct 2024 23:36:38 +0000 поиск максимумов в хеш-таблице https://forum.sources.ru/index.php?showtopic=452734&view=findpost&p=3912530
Есть текст на английском языке. Нужно разбить его на отдельные слова и поместить в хеш-таблицу, которая на цепочках. При этом считается частотность каждого слова ( отдельное поле ). Если слово раньше не встречалось, то оно вставляется в НАЧАЛО цепочки ( вычислительная сложность О(1) этой операции ).

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

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

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

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

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

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

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

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

спс за внимание]]> FasterHarder Алгоритмы