Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 21.05.2012, 20:08   #1
vedro-compota
любитель-далеко не
Участник клуба
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Сообщений: 1,156
По умолчанию Оптимальный алгоритм - получить список из N наиболее часто встречающихся элементов

Друзья, приветствую всех и здравия желаю)

Если кто когда-то уже размышлял над проблемой указанной в заголовке выскажите какие-нибудь соображения по поводу решения задачи вроде следующей:
Цитата:
есть здоровенный текстовый файл - из него можно так ли иначе получить длинный массив элементов .задача: получить N наиболее часто встречающихся элементов (подразумевается, что полученный массив при решении "в лоб" обрабатывается недопустимо долго)
Насколько я понимаю - если отбросить вопрос о методе получения данных, то задача делиться на следующие подзадачи:
  • 1) Получения списка "уникальных " элементов из исходного списка
  • 2) Определение "веса " каждого элемента при повторном просмотре исходного списка
  • 3) Сортировка второго списка уникальных элементов с учётом веса

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

Особенно алгоритм сортировки .

p.s. - да - знаю, что об этом писал великий Дональд Кнут - и буду очень благодарен если вы не просто отошлёте меня к данной книги (надеюсь, что к книге))) и ещё и скажите название алгоритма (который рассматривается у Кнута) наиболее оптимального в данном случае.

Заранее благодарю)
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума Ответить с цитированием
Старый 21.05.2012, 21:07   #2
Levsha100
Заблокирован
Старожил
 
Регистрация: 20.07.2008
Сообщений: 4,033
По умолчанию

Самый простой способ это двоичное дерево, где хранится слово и число раз сколько оно встретилось. Проходим по файлу, если не нашли слово, то добаляем в дерево и счетчик ставим 1, иначе увеличиваем счетчик.
Это сбор уникальных слов и их количества.
Как найти наиболее часто встречаемые нужно подумать, но думаю нужно этим занимается при увеличении счетчика.
Levsha100 вне форума Ответить с цитированием
Старый 21.05.2012, 21:32   #3
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Ну да, мне тоже видится список образцов и частота их использования... Вариант 2. Отсортировать все слова (в смысле текст) и считать количество повторений. Но не знаю что будет быстрей... Для русского языка наверно это будет союз и
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 21.05.2012, 22:11   #4
akasex
Форумчанин Подтвердите свой е-майл
 
Аватар для akasex
 
Регистрация: 31.03.2008
Сообщений: 179
По умолчанию

Цитата:
Сообщение от Levsha100 Посмотреть сообщение
Как найти наиболее часто встречаемые нужно подумать, но думаю нужно этим занимается при увеличении счетчика.
Maybe use a binary heap instead? http://en.wikipedia.org/wiki/Binary_heap

Последний раз редактировалось akasex; 22.05.2012 в 00:41. Причина: Added link
akasex вне форума Ответить с цитированием
Старый 21.05.2012, 22:30   #5
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
Самый простой способ это двоичное дерево
Это не просто самый простой, это пожалуй самый быстрый - содержать список, сортируемый по мере внесения в него данных, при этом определение места для внесения нового, еще не содержащегося слова в списке или нахождение элемента, содержащего такое слово, проводится бинарным поиском.
По-моему так свои индексы обновляют все серьезные СУБД при вставке записи.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 21.05.2012, 22:49   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Возможно поможет эта реализация http://morpher.ru/Russian/Stats.aspx
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 22.05.2012, 08:42   #7
vedro-compota
любитель-далеко не
Участник клуба
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Сообщений: 1,156
По умолчанию

Цитата:
Вариант 2. Отсортировать все слова (в смысле текст) и считать количество повторений.
Utkin , придётся же выполнять сортировку строк , но для этого для каждой строки (слова) надо будет какой-то ключ сформировать - напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
(но вообще -насколько я понимаю - это лишь конкретный способ определения "веса слова" - так как после того, как текст отсортирован - нам придётся считать повторы - после же сортировать результирующий массив и получать эти самые N значений)
Аватар, akasex благодарю за ссылки.
Levsha100 , Stilet наверное правда лучше всего что-то "бинарное"...буду смотреть.
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума Ответить с цитированием
Старый 22.05.2012, 09:38   #8
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Цитата:
напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
Не знаю, хеши строк это отдельный вопрос Надо подумать
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 22.05.2012, 20:55   #9
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
На коллизии не боишься нарваться? Впрочем существуют методы индексации по хешам и битовым маскам (В Оракле я подобное встречал)
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 23.05.2012, 02:50   #10
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,520
По умолчанию

Решил вспомнить молодость, написал на плюсах какую-то фигню, но баги вылазят, судя по результатам, но сути дела эти ошибки не должны менять.
Скачал где-то войну и мир на 3 метра, написал прогу. Она насчитала вот это:
Цитата:
Всего слов: 466023
20319: и
10223: ве
8469: нес
7850: что
5760: сн
3866: его
3705: как
3408: кt
2130: яз
2016: сказал
В диспетчере задач почти 26 метров памяти занятой показывается, а по скорости буквально секунд 5 на моём Core i3. Баги на скорость работы вряд ли повлияли, а по памяти можно еще много оптимизировать при желании.
Описываю принцип:
Слова загоняются в дерево (не помню только уже как оно называется, в разделах про поиск описывается оно). Ветви дерева - буквы слов, а листья - специальный маркер, показывающий конец слова. В общем, ветви корня дерева - первые буквы всех найденных слов. От всех этих первых букв идут уже вторых буквы этих самых слов. Если слово состоит из одной буквы, то вместо второй буквы должен быть маркер, который можно совместить со счетчиком популярности слова. Таким образом, если идти от корня к листьям, то можно прочесть все найденные слова.
Ну, а потом нужно найти N листьев этого дерева, с наибольшим счетчиком. Я сделал это через тупую рекурсию. Из STL использовал только list и его sort с merge для сортировки и объединения упорядоченных списков, соответственно.
Попробовал скопировать этот же текст несколько раз. В итоге получил 64 метра на диске, оперативки в диспетчере жрала прога столько же, а время выполнения не больше 15 секунд (основное время заняло чтение из файла и создание дерева на основе этих данных).
pu4koff вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
из текстового файл получить 5 наиболее часто встречающихся слов и число их появлений (на Delphi) sifa Помощь студентам 5 09.01.2012 18:34
в тексте слова, содержащие ровно одну из 10 наиболее часто встречающихся букв yaroslav_bondarev Паскаль, Turbo Pascal, PascalABC.NET 3 16.12.2011 10:11
дан текст, написать код, нахождения 10 наиболее часто встречающихся букв yaroslav_bondarev Паскаль, Turbo Pascal, PascalABC.NET 9 14.12.2011 22:08
Получить массив из элементов, встречающихся в исходном массиве ровно один раз без повторений Shikarmo4000 Помощь студентам 0 25.05.2010 01:27
Найти (в процентах) частоту появления каждого из m наиболее часто встречающихся элементов sk1p Паскаль, Turbo Pascal, PascalABC.NET 2 26.09.2008 23:57