На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> поиск максимумов в хеш-таблице
    Всем хай! Сходу к делу!

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

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

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

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

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

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

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

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

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

    спс за внимание
    Сообщение отредактировано: FasterHarder -
      Возможно, подразумевается комплекс мер.

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

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

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

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

      -----
      P.S. Использование кучи смешно смотрится на таких объёмах (5/97), и пятикратный просмотр концов с таким же удалением будет, вероятно, на практике не хуже
      Сообщение отредактировано: MBo -
        Крайне странное описание. Я в нём в упор не вижу подсчёта количества - вариант "Если слово раньше не встречалось" рассмотрен, а обратный как-то стыдливо проигнорирован. В то время как конечная задача требует именно подсчёта количества вхождений, то есть этот обратный вариант даже более важен.

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

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

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

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

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

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

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

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

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

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

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

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


                Рейтинг@Mail.ru
                [ Script execution time: 0,1658 ]   [ 15 queries used ]   [ Generated: 5.12.24, 15:20 GMT ]