Частота слова программы — слишком большой ввод файла?
Я все еще работаю над проблемой, упомянутой в этом посте:
Сортировка вектора строк с ведущими числами
Первоначальная проблема заключается в следующем:
Напишите полную программу на C ++, которая выводит k наиболее часто используемых слов в файле input.txt, по одному на строку в порядке убывания частоты, где k — неотрицательное целое число, считываемое из ввода. Связи разрываются произвольно, и если в input.txt и u есть только разные слова < k, то на выходе есть только u записей.
Для этой проблемы вы не можете использовать любой класс или алгоритм STL, кроме вектора и строки. Слово — это максимальный блок символов, не являющихся пробелами, с удаленными знаками препинания. Каждая выходная строка состоит из слова, за которым следует его счетчик частоты. (даны входные данные и k-значения)
Благодаря тем, кто предложил использовать структуру, я получил немного более эффективное решение с меньшим количеством кода.
тем не мение, проблема в том, что для текстовых файлов, которые являются относительно большими (состоящими из> 400000 слов), моя программа может продолжать работать более 5 минут и не дает никакого результата. Программа отлично работает на небольших файловых входах. Я не уверен, что это из-за того, что файл был слишком большим или проблема с самим алгоритмом вызывает переполнение / повреждение памяти.
Вот мой код для программы:
struct word_freq {
int freq;
string word;
};
bool operator<(const word_freq& a, const word_freq& b) {
return a.freq < b.freq;
}
void word_frequencies(ifstream& inf, int k)
{
vector <string> input;
string w;
while (inf >> w)
{
remove_punc(w);
input.push_back(w);
}
sort(input.begin(), input.end());
// initialize frequency vector
vector <int> freq;
for (size_t i = 0; i < input.size(); ++i) freq.push_back(1);
// count actual frequencies
int count = 0;
for (size_t i = 0; i < input.size()-1; ++i)
{
if (input[i] == input[i+1])
{
++count;
} else
{
freq[i] += count;
count = 0;
}
}
// words+frequencies
vector <word_freq> wf;
for (int i = 0; i < freq.size(); ++i)
{
if (freq[i] > 1 || is_unique(input, input[i]))
{
word_freq st = {freq[i], input[i]};
wf.push_back(st);
}
}
// printing
sort(wf.begin(), wf.end());
if (wf.size() < k)
{
for (int i = wf.size()-1; i >= 0; --i)
{
cout << wf[i].word << " " << wf[i].freq << endl;
}
} else
{
for (int i = wf.size()-1; i >= wf.size()-1-k; --i)
{
cout << wf[i].word << " " << wf[i].freq << endl;
}
}
}
Если кто-то может указать на допущенные ошибки, это будет с благодарностью.
Решение
Вы делаете свою программу слишком подходящей по памяти и вычислениям. Сначала вы читаете все слова в память и сортируете их. Затем вы рассчитываете частоты и заполняете еще один вектор. У тебя должно быть std::vector<word_freq> во-первых, сохраняйте его отсортированным по слову (вставляя элементы в нужное место) и вставляйте новый элемент или увеличивайте счетчик на существующем. Затем прибегните к этому вектору по частотам и напечатайте.
Например, как вы можете переписать ваш цикл:
struct word_freq {
int freq;
std::string word;
word_freq( const std::string &w ) : word( w ), freq( 0 ) {}
};void addWord( std::vector<word_freq> &v, const std::string &word )
{
word_freq tmp( word );
auto p = std::equal_range( v.begin(), v.end(), tmp,
[]( const word_freq &w1, const word_freq &w2 ) {
return w1.word < w2.word;
} );
if( p.first == p.second ) // not found
p.first = v.insert( p.second, tmp ); // insert into proper place
p.first->freq++; // increase freq counter
}
// ......
std::vector<word_freq> words;
string w;
while (inf >> w)
{
remove_punc(w);
addWord( words, w );
}
// here your vector sorted by words, there are no dups and counters have proper value already
// just resort it by freq and print
Подробности о том, как сохранить вектор отсортирован, можно найти здесь как вставить значение в отсортированный вектор?
На другой стороне держите std::vector<word_freq> Сортировка потребует слишком совпадения вставок в середину или начало вектора, что может быть довольно дорогим и медленным. Так что, если вы реализуете описанную логику и заставляете ее работать на небольших примерах, и она все еще слишком медленная для вашего большого ввода — вы должны отсортировать вектор индексов вместо вектора word_freq сам. Это по-прежнему требует вставки в начало или в середину вектора целых чисел, но такая операция значительно дешевле и быстрее. Подробности о том, как сортировать индексы вместо самого вектора, можно найти здесь: сравнить функцию сортировки в c ++ для сортировки индекса
Другие решения
Если вы используете reserve(int) после распределения ваших векторов,
производительность будет намного лучше.
Возвращение к векторам постоянно вызывает фрагментацию памяти.
Причина в том, что векторы постоянно выходят за пределы своих выделенных границ и часто перераспределяются. Перераспределение небольших объектов часто обходится дорого и напрямую влияет на производительность.
Первоначальный вызов резерва с достаточно большим фрагментом памяти и повторный вызов, когда размер вектора соответствует его емкости, помогает избежать этой проблемы.
Больше здесь:
Что такое фрагментация памяти?
И здесь:
Стоит ли беспокоиться о фрагментации памяти с помощью std :: vector?
Небольшая демонстрация с измерениями производительности:
#include <chrono>
#include <vector>
#include <iostream>
int main()
{
std::vector<std::string> slow;
std::string d = "divide and conquer";
std::chrono::time_point<std::chrono::system_clock> start, end;
start = std::chrono::system_clock::now();
// I get reallocated all the time
for ( int i=0; i < 100000; i++ )
{
slow.push_back(d);
}
end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::time_t end_time = std::chrono::system_clock::to_time_t(end);
std::cout << "elapsed time v1: " << elapsed_seconds.count() << "s\n";
start = std::chrono::system_clock::now();
//I don't move around
slow.reserve(100000);
slow.clear();
for ( int i=0; i < 100000; i++ )
{
slow.push_back(d);
}
end = std::chrono::system_clock::now();
elapsed_seconds = end-start;
end_time = std::chrono::system_clock::to_time_t(end);
std::cout << "elapsed time v2: " << elapsed_seconds.count() << "s\n";
return 0;
}
Выход:
elapsed time v1: 0.014085s
elapsed time v2: 0.004597s