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

[Utkin]

Как то проконтролировать всякий мусор в виде не читаемых символов и пр

Что их же мешает засунуть в Split?

[Rififi]

vedro-compota

… получить N наиболее часто встречающихся элементов …

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

#include <locale>
#include <iostream>

#include <string>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
namespace mi = boost::multi_index;

#include <boost/interprocess/file_mapping.hpp>
#include <boost/interprocess/mapped_region.hpp>
namespace ipc = boost::interprocess;

#include <boost/xpressive/xpressive.hpp>
#include <boost/timer.hpp>

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<WordTag>,
			BOOST_MULTI_INDEX_MEMBER(Word, std::string, word_)
		>,
		mi::ordered_non_unique<
			mi::tag<CounterTag>,
			BOOST_MULTI_INDEX_MEMBER(Word, size_t, counter_),
			std::greater<size_t>
	> > > Dictionary;

struct inc
{
	template <typename T>
	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<const char*>(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<CounterTag>::type Index;
	const Index& idx = dict.get<CounterTag>();

	for (Index::const_iterator it = idx.cbegin(); it != idx.cend() && n < 10; it++, n++)
	{
		std::cout << it->word_ << " => " << it->counter_ << std::endl;
	}

	return 0;
}

Пример вывода:

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

[Kostia]

Что их же мешает засунуть в Split?

Если заняться нечем, то абсолютно ничего, интересно сколько там всяких закорючек в UTF-8 и др. кодировках?
Да и в добавок если символы другого алфавита тоже являются мусором, т.е. вы заранее знаете что в тексте должна быть только латиница и кириллица + дополнительные символы присущие тематике текста, которые можно посчитать как значимые слова(мат символы например), а в др. ситуациях их нужно игнорить.

[Utkin]

А зачем utf? Человеку интересны алгоритмы. Но пусть даже и так - для Войны и мир ему все закорючки не нужны. Достаточно общеупотребительных.

[_-Re@l-_]

Rififi, как сложно.. Мой код - это чисто С++ с использованием STL, при том всё короче и проще

[Rififi]

_-Re@l-_

Мой код - это чисто С++ с использованием STL, при том всё короче и проще

"Короче и проще" не всегда означает "лучше", вот ведь какая штука получается oO :D

провел замер скрости: раскопировал войну и мир в себя до тех пор, пока размер результирующего файла не стал 195mb, запустил парсер:

Parsed 55*862 unique words of total 29*994*048 in 19,41 sec.
и => 1*300*416
в => 654*272
не => 542*016
что => 502*400
на => 413*056
он => 383*104
с => 368*640
его => 247*424
как => 237*120
то => 232*640

И где он кстати, твой короткий и простой код?

можно будет получить грант на них. (100 тыщ)

100тыщ - чё-то как-то кисло, тем более для Моськи, у меня велик дороже стоит :D

[_-Re@l-_]

И где он кстати, твой короткий и простой код?

Я не говорил, что он короткий, я сказал, что он короче.
И ещё , мне как бы интересно, почему вы заранее меня стараетесь принизить.

[Rififi]

_-Re@l-_

И ещё , мне как бы интересно, почему вы заранее меня стараетесь принизить.

В чего это вдруг?

Как я вижу, это вы ко мне обратились сначала с критическим комментом, а затем перевели стрелку на свое секретное решение (а вот у меня... да только C++ и STL... короче и проще ...)

Так что, боюсь, ваши БДСМ oO предположения о том, что кто-то хочет вас принизить - плод богатого воображения.

[_-Re@l-_]

Как я вижу, это вы ко мне обратились сначала с критическим комментом

Критическим? Пфф, ну вы блин даёте. Там никакой критики в помине не было.

[s-andriano]

Алгоритм решения этой задачи имеет сложность O(n*log(n)).
Естественно, таких алгоритмов несколько разных.
По опыту: миллиард слов обрабатывается порядка часа, а миллион - порядка секунды.