Последние записи

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

5th
Июн

Оптимальный алгоритм — получить список из N наиболее часто встречающихся элементов

Posted by Chas under Исходники, Общалка

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

Если кто когда-то уже размышлял над проблемой указанной в заголовке выскажите какие-нибудь соображения по поводу решения задачи вроде следующей:

Цитата: есть здоровенный текстовый файл — из него можно так ли иначе получить длинный массив элементов .задача: получить N наиболее часто встречающихся элементов (подразумевается, что полученный массив при решении «в лоб» обрабатывается недопустимо долго)

Насколько я понимаю — если отбросить вопрос о методе получения данных, то задача делиться на следующие подзадачи:
1) Получения списка «уникальных » элементов из исходного списка
2) Определение «веса » каждого элемента при повторном просмотре исходного списка
3) Сортировка второго списка уникальных элементов с учётом веса

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

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

Аватар
Воспользовался его идеей и встроил сразу разборку fb2 текста и сортировку по частоте вхождения при добавлении нового слова. Прога на D7 без обработки исключений, путь к файлу в исходном тексте прошит. Эксперементировал на файле со сто тысячью слов. Основное время пошло на выделение слов из fb2. На 1-ой картинке время вместе с разборкой файла, на второй только на частотный анализ. Текст проги прилагается

Exper.zip (14.1 Кб)

Rififi
Ну, например, вот так:

#include
#include

#include

#include
#include
#include
#include
namespace mi = boost::multi_index;

#include
#include
namespace ipc = boost::interprocess;

#include
#include

struct Word
{
Word(const std::string& word) : word_(word), counter_(0) {}
std::string word_;
size_t counter_;
};

struct WordTag {};
struct CounterTag {};

typedef mi::multi_index_container< Word, mi::indexed_by< mi::hashed_unique< mi::tag,
BOOST_MULTI_INDEX_MEMBER(Word, std::string, word_)
>,
mi::ordered_non_unique< mi::tag,
BOOST_MULTI_INDEX_MEMBER(Word, size_t, counter_),
std::greater
> > > Dictionary;

struct inc
{
template
void operator()(T& v) const { ++v.counter_; }
};

int main()
{
std::locale::global(std::locale(""));
std::cout.imbue(std::locale());

const ipc::file_mapping mapping("tolstoi_l_n__voina_i_mir.txt", ipc::read_only);
const ipc::mapped_region region(mapping, ipc::read_only);

const char* begin = static_cast(region.get_address());

using namespace boost::xpressive;

Dictionary dict;
boost::timer t;

cregex_token_iterator it(begin, begin + region.get_size(), imbue(std::locale())(+_w));
const cregex_token_iterator end;
for (; it != end; ++it)
{
const Dictionary::iterator where = dict.insert(it->str()).first;
dict.modify(where, inc());
}

std::cout << "Parsed " << dict.size() << " unique words in " << t.elapsed() << " sec." << std::endl; size_t n = 0; typedef Dictionary::index::type Index;
const Index& idx = dict.get();

for (Index::const_iterator it = idx.cbegin(); it != idx.cend() && n < 10; it++, n++) { std::cout << it->word_ << " => " << it->counter_ << std::endl; } return 0; }[/code] Пример вывода: Parsed 55*862 unique words in 0,312 sec. и => 20*319
в => 10*223
не => 8*469
что => 7*850
на => 6*454
он => 5*986
с => 5*760
его => 3*866
как => 3*705
то => 3*635

тема на форуме