Подсчитайте вхождения и напечатайте top K, используя C / STL
У меня большой текстовый файл с токенами в каждой строке. Я хочу посчитать количество вхождений каждого токена и отсортировать его. Как мне сделать это эффективно в C ++, предпочтительно используя встроенные функции и самое короткое кодирование (и, конечно, самое эффективное)? Я знаю, как сделать это в Python, но не уверен, как это сделать, используя unordered_map в STL.
Решение
Я бы пошел с подходом unordered_map. Для выбора наиболее частых k токенов, предполагая, что k меньше, чем общее количество токенов, следует взглянуть на станд :: partial_sort.
Кстати, ++frequency_map[token] (где частота_карта, скажем, std::unordered_map<std::string, long>) вполне приемлемо в C ++, хотя я думаю, что эквивалент в Python взорвется на недавно увиденных токенах.
Хорошо, вот и вы:
void most_frequent_k_tokens(istream& in, ostream& out, long k = 1) {
using mapT = std::unordered_map<string, long>;
using pairT = typename mapT::value_type;
mapT freq;
for (std::string token; in >> token; ) ++freq[token];
std::vector<pairT*> tmp;
for (auto& p : freq) tmp.push_back(&p);
auto lim = tmp.begin() + std::min<long>(k, tmp.size());
std::partial_sort(tmp.begin(), lim, tmp.end(),
[](pairT* a, pairT* b)->bool {
return a->second > b->second
|| (a->second == b->second && a->first < b->first);
});
for (auto it = tmp.begin(); it != lim; ++it)
out << (*it)->second << ' ' << (*it)->first << std::endl;
}
Другие решения
Предполагая, что вы знаете, как читать строки из файла в C ++, это должно быть толчком в правильном направлении
std::string token = "token read from file";
std::unordered_map<std::string,int> map_of_tokens;
map_of_tokens[token] = map_of_tokens[token] + 1;
Затем вы можете распечатать их как таковые (для теста):
for ( auto i = map_of_tokens.begin(); i != map_of_tokens.end(); ++i ) {
std::cout << i->first << " : " << i->second << "\n";
}