词频程序——文件输入太大？

Question

我仍在努力解决post中提到的问题：

原题如下：

编写一个完整的 C++ 程序，输出文件 input.txt 中最常用的 k 个单词，每行一个，按频率降序排列，其中 k 是从输入中读取的非负整数。关系被任意打破，如果 input.txt 中只有 u 个不同的词并且 u < k，那么输出只有 u 个条目。对于这个问题，除了vector 和string，你不能使用任何STL class 或算法。一个单词是去除标点符号的非白色 space 字符的最大块。每条输出行都包含一个词，后面跟着它的频率计数。（给出输入和 k 值）

感谢那些建议使用结构的人，我最终用更少的代码得到了一个更有效的解决方案。

但是，问题是，对于比较大的文本文件（由>400000字组成），我的程序可以保持运行超过5分钟并没有给出任何结果。该程序在小文件输入上完美运行。不知道是因为文件太大，还是算法本身有问题导致内存overflow/corruption.

这是我的程序代码：

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;
    }
}
}

如果有人能指出所犯的错误，将不胜感激。

Answer 1

如果在分配向量后使用 reserve(int)，性能会好很多。

不断推回向量会导致内存碎片。

原因是向量不断地超出其分配的边界，并且经常被重新分配。重新分配小对象通常很昂贵，并且会直接影响性能。

最初使用足够大的内存块调用 reserve，并在向量的大小与其容量匹配时再次调用它，有助于避免此问题。

更多信息：

What is memory fragmentation?

这里：

Should I worry about memory fragmentation with 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

Answer 2

你让你的程序通过记忆和计算来做的太匹配了。首先，您将所有单词读入内存并对其进行排序。然后计算频率并填充另一个向量。你应该把 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

可以在此处找到有关如何保持向量排序的详细信息how do you insert the value in a sorted vector?

另一方面，保持 std::vector<word_freq> 排序将需要太匹配插入向量的中间或开头，这可能非常昂贵且缓慢。因此，如果您实现了所描述的逻辑并使其适用于小示例，并且对于您的大输入来说它仍然太慢 - 您应该对索引向量而不是 word_freq 本身的向量进行排序。这仍然需要插入到整数向量的开头或中间，但这样的操作要便宜得多，也更快。有关如何排序索引而不是向量本身的详细信息，请参见此处：compare function of sort in c++ for index sort

词频程序——文件输入太大？

Word frequency program - file input too large?

c++

file-io

fstream

text-files

word-frequency