第一次个人作业

$( "#cnblogs_post_body" ).catalog()

要求

对源文件（.txt,.cpp,.h,.cs,.html,.js,.java,.py,*.php等，文件夹内的所有文件）统计字符数、单词数、行数、词频，统计结果以指定格式输出到默认文件中，以及其他扩展功能，并能够快速地处理多个文件。
使用性能测试工具进行分析，找到性能的瓶颈并改进。
对代码进行质量分析，消除所有警告。
设计10个测试样例用于测试，确保程序正常运行（例如：空文件，只包含一个词的文件，只有一行的文件，典型文件等等）。
使用Github进行代码管理。
撰写博客。

基本功能

统计文件的字符数（只需要统计Ascii码，汉字不用考虑）。
统计文件的单词总数。
统计文件的总行数（任何字符构成的行，都需要统计）。
统计文件中各单词的出现次数，输出频率最高的10个。
对给定文件夹及其递归子文件夹下的所有文件进行统计。
统计两个单词（词组）在一起的频率，输出频率最高的前10个。
在Linux系统下，进行性能分析，过程写到blog中

PSP表格

Process Stages	Time(Estimate)	Time(Real)
需求分析	0.5 h	0.5 h
设计	1 h	1 h
编码
· 文件操作	1 h	2 h
· 字符数、行数、词数	3 h	3 h
· 单词短语频率	2 h	4 h
· 测试	2 h	2 h
· 写报告	1 h	1.5 h

整体设计

文件处理
使用正则表达式判断文件与路径
使用ifstream ofstream读写文件
行数：使用ifstream getline函数，读一行则行数 +1
字符数：略
单词数
逐个字符读入文件的每一行，符合条件的字符放入一个string
遇到分隔符，则判断已有的 string 是否符合单词规范，若符合则放入一个 vector容器，并清空string
vector 的大小就是单词数
词频统计
使用 pair 容器，存放每个种类的单词出现的次数，以及对应的字典顺序最小的单词
使用 unordered_map 作为现成的 hash_table，unordered_map<string, pair<string, int> >
- 单词 stirng 作为 unordered_map 的键值（key）
- pair<string, int> 作为 value
词组统计
使用pair容器存放词组，只存储词组出现的次数
使用 unordered_map 作为现成的 hash table，unordered_map<pair<string, string>, int>
- 词组 pair<string, string> 作为key
- 频数 int 作为 value
- hash_function 取两个 string 的哈希值的异或

测试

自己设计了几个小的测试样本（考虑了空文件、重复单词、奇奇怪怪的字符组合等情况，但都没有保留下来）
助教的测试文件

代码质量分析

代码中用了很多c++11的STL标准库中的东西，相对比较安全
使用类封装了很多内部函数，也保证了安全
函数名与变量名都取了易读的名字，按着自己的变量与函数命名习惯统一风格，清晰易懂
unordered_map保证了每次访问单词频率时都是O(1)的时间复杂度
后期也优化了一下代码，增加一些判断以减少不必要的计算。也在循环中简化计算以节省时间。

性能分析

macOS系统没法在Windows下测试，就只好只在Linux下试试了

使用gprof分析性能（表格前几行）：

再多说一句，gprof使用方法大概是在编译时使用-pg选项，然后就可以在编译路径下使用gprof相关的命令了。

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 12.78      3.43     3.43 212228030     0.00     0.00  std::__detail::_Hash_code_base
 12.67      6.83     3.40 18088561     0.00     0.00  std::_Hashtable
  6.86      8.67     1.84     1323     0.00     0.02  FileWordCounter::procFile
  6.04     10.29     1.62 16732233     0.00     0.00  std::_Hashtable
  5.68     11.82     1.53 224669806     0.00     0.00  std::__detail::_Equal_helper
  4.12     12.92     1.11 256026965     0.00     0.00  std::__detail::_Mod_range_hashing::operator
  3.15     13.77     0.85 436013693     0.00     0.00  std::__detail::_Hash_node
  3.02     14.58     0.81 25383831     0.00     0.00  std::__detail::_Equal_helper
  2.61     15.28     0.70 224669806     0.00     0.00  std::__detail::_Hashtable_base
  2.53     15.96     0.68 249864549     0.00     0.00  __gnu_cxx::__enable_if
  2.35     16.59     0.63        1     0.63     0.85  FileWordCounter::selectDouW
  1.57     17.01     0.42     1278     0.00     0.00  void std::__cxx11::basic_string
  1.42     17.39     0.38 16650656     0.00     0.00  FileWordCounter::normStr
  1.38     17.76     0.37  8978102     0.00     0.00  std::__detail::_Hash_code_base
  1.27     18.10     0.34 230316611     0.00     0.00  std::__detail::_Hash_code_base
  1.19     18.42     0.32 210146189     0.00     0.00  std::_Hashtable
  1.14     18.72     0.31 218085323     0.00     0.00  std::__detail::_Hash_node_value_base
  1.12     19.02     0.30 218085303     0.00     0.00  std::equal_to
  1.04     19.30     0.28 266397591     0.00     0.00  __gnu_cxx::__aligned_buffer

这里大多数的函数都是stl库函数，函数名过长，所以做了删减。

可以看见，hash_table的操作和string的操作占用了几乎所有的资源时间。如果需要优化，那两个思路：

自己写hash_table，用字符数组代替字符串
减少这些操作

我没时间自己写hash_table和更改字符串的处理方式（其实是自己写怕不会比STL库好），但之后我在代码中增加了一些判断，以减少某些不必要的操作

在 macOS 系统下程序运行时间，以助教给的测试集为标准，不使用 -O2 优化选项，运行时间约60s，开启优化后约20s，每次运行时间均有上下浮动（应该是cache的原因）

小结

本次实验我熟练了c++容器的一些操作

了解了c++处理文件的方式

学会了使用GitHub管理代码

学会了debug的一些小技巧，linux下的性能分析

多说一句

ddl前我无聊翻了一下别人的代码，发现比我的要快好多（将近快一倍了），一对比才知道出现的问题在哪里（也就是说之前说了那么多性能分析都是废话，没找到问题关键所在。

我的undered_map定义的太花哨了，一个把value设置成了pair类，一个把key设置成了pair类，直接导致了哈希表那儿运算时间大幅增加（可以看见花费的时间都在hash上），不如老老实实定义俩unordered_map，或者把两个string合并起来，这样也许会少很多不必要的运算。

但我发现这个问题的时候已经只剩1小时了（早知道我早点去参考参考，哭）也懒得参考了。

最后附上我丑陋的代码

/**
 * Count character numbers, line numbers, words(specially defined) numbers.
 * Count word frequency and double word phrase frequency.
 * Process a file or directory and write result in ./result.txt.
 * Created by Xiuyuan Chen on 29 Mar. 2018.
 * Copyright © 2018 Xiuyuan Chen. All rights reserved.
 * Just a joke, please feel free to copy and write.
 */

#include <string>
#include <vector>
#include <iostream>
#include <regex>
#include <fstream>
#include <unordered_map>
#include <dirent.h>
using namespace std;
//Hash function for a pair<a,b>
struct pairhash {
public:
    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U> &x) const
    {
        return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
    }
};


class FileWordCounter{
private:
    char path[512];
    unsigned long charNum;//total character number
    unsigned long lineNum;//total line number
    unsigned long wordNum;//total word number
    unordered_map<string, pair<string, int> > singleWordFreq;//stores (standard word, <word for display, word frequency>)
    unordered_map<pair<string, string>, int, pairhash> doubleWordFreq;//stores (<standard word1, word2>, phrase frequency)

    void procFile(char p[]);
    void procDir(char path[]);
    void addWord(vector<string> &result, string src);
    void calFreq(vector<string> &result);
    string normStr(string a);

    void writeSinW();
    void writeDouW();
public:
    FileWordCounter(const char p[]){
        strcpy(path,p);
        charNum = 0;
        lineNum = 0;
        wordNum = 0;
    }
    void read();
    void write();
};

//use regex to judge path a file or a directory
void FileWordCounter::read() {
    regex reg1("^[\\.]{0,2}(\\/[\\w-]+)*\\/([\\w-]+\\.)+[\\w-]+$");
    regex reg2("^[\\.]{0,2}(\\/[\\w-]+)*\\/?$");
    cmatch cm;
    if(regex_match(path, cm, reg1)){
        procFile(path);
        //cout << "File" << endl;
    }
    else if(regex_match(path, cm, reg2)) {
        procDir(path);
        //cout << "Folder" << endl;
    }
    else{
        cout << "ERROR: No such file or directory" << endl;
    }
}

//write file
void FileWordCounter::write(){
    ofstream outf("result.txt");
    outf << "char_number: " << charNum << endl;
    outf << "line_number: " << lineNum << endl;
    outf << "word_number: " << wordNum << endl;
    outf.close();
    writeSinW();//write top 10 words
    writeDouW();//write top 10 phrases
}

//traverse directory in recursion
void FileWordCounter::procDir(char p[]){
    DIR* pDir;
    struct dirent* ent;
    char childpath[512];
    pDir=opendir(p);
    memset(childpath,0,sizeof(childpath));
    while((ent=readdir(pDir)) != nullptr) {
        if (ent->d_type & DT_DIR) {
            if (strcmp(ent->d_name, ".") == 0 || strcmp(ent->d_name, "..") == 0)
                continue;
            sprintf(childpath, "%s/%s", p, ent->d_name);//combine together
            //printf("path:%s\n", childpath);
            procDir(childpath);
        }
        else{
            sprintf(childpath, "%s/%s", p, ent->d_name);//combine together
            //printf("path:%s\n", childpath);
            procFile(childpath);
        }
        memset(childpath,0,sizeof(childpath));
    }
}

//process a single file
void FileWordCounter::procFile(char p[]){
    ifstream input;
    input.open(p);
    if (!input.is_open()) {
        cout << "Cannot open file " << p << endl;
        return;
    }

    string line, temp;
    unsigned long length = 0;
    vector<string> result;//result stores all words in this file
    int key;
    while(!input.eof()){
        getline(input, line);//read line by line
        lineNum++;//line_number + 1
        key = 0;
        length = line.size();
        for(int i = 0; i < length; i++){
            if(line[i] >= 32 && line[i] <=126){//char_number + 1
                charNum++;
            }
            if(isdigit(line[i]) || isalpha(line[i])){//to judge whether it is a word element
                temp += line[i];
                key = 1;
            }
            else{
                if(temp.size() > 3){
                    addWord(result, temp);//judge whether temp is a word and add it to vector(result)
                }
                temp = "";
                key = 0;
            }
        }
        if(key == 1){//to deal with the last word in a line
            if(temp.size() > 3){
                addWord(result, temp);
            }
            temp = "";
        }
    }//use getline so we don't have to do line_number++ at the end of a file
    wordNum += result.size();

    calFreq(result);
}

//judge whether src is a word and add it to vector(result)
void FileWordCounter::addWord(vector<string> &result, string src){
    int length = src.size();
    for(int i = 0; i < length - 3;){
        if(!isalpha(src[i])){
            i = i + 1;
            continue;
        }
        if(!isalpha(src[i+1])){
            i = i + 2;
            continue;
        }
        if(!isalpha(src[i+2])){
            i = i + 3;
            continue;
        }
        if(!isalpha(src[i+3])){
            i = i + 4;
            continue;
        }
        result.push_back(src.substr(i, length));
        return;
    }
}

//process all words in a file
void FileWordCounter::calFreq(vector<string> &result){
    string srcStr2, norStr1, norStr2;//norStr2 means normalized string for string_2
    unsigned long wordNumt = result.size();
    unordered_map<string, pair<string, int> >::iterator its, prev;
    unordered_map<pair<string, string>, int, pairhash>::iterator itd;
    //process the first word
    if(wordNumt != 0){
        srcStr2 = result[0];
        norStr2 = normStr(srcStr2);//normalize string_2
        its = singleWordFreq.find(norStr2);
        if(its == singleWordFreq.end()){//if the word is not stored
            singleWordFreq[norStr2] = make_pair(srcStr2, 1);//store it
        }
        else{//update word frequency and word for display
            its->second.second++;
            if(its->second.first > srcStr2){
                its->second.first = srcStr2;
            }
        }
    }
    //process the following word
    for(int i = 1; i < wordNumt; i++){
        norStr1 = norStr2;//copy string_2 to string_1
        srcStr2 = result[i];
        norStr2 = normStr(srcStr2);
        //same as above
        its = singleWordFreq.find(norStr2);
        if(its == singleWordFreq.end()){
            singleWordFreq[norStr2] = make_pair(srcStr2, 1);
        }
        else{
            its->second.second++;
            if(its->second.first > srcStr2){
                its->second.first = srcStr2;
            }
        }
        //process phrase(norStr1, norStr2), similar as above
        itd = doubleWordFreq.find(make_pair(norStr1, norStr2));
        if(itd == doubleWordFreq.end()){
            doubleWordFreq[make_pair(norStr1, norStr2)] = 1;
        }
        else{
            itd->second++;
        }
    }
}

//normalize a string, to delete the digits at the end and make all letters capitals
string FileWordCounter::normStr(string a){
    string str = a;
    while(isdigit(str.back())){
        str.erase(str.end() - 1);
    }
    unsigned long length = str.size();
    for(int i = 0; i < length; i++){
        if(str[i] >= 'a'){
            str[i] -= 32;
        }
    }
    return str;
}

//write top 10 words
void FileWordCounter::writeSinW(){
    int size = int(singleWordFreq.size());
    int length = min(10, size);
    unordered_map<string, pair<string, int> > temp;//to store top 10 words
    ofstream outf("result.txt",ios::app);
    outf << endl << "the top ten frequency of word: " << endl;
    for(int i = 0; i < length; i++){//select top 10
        auto key = singleWordFreq.begin();
        for (auto iter = singleWordFreq.begin(); iter != singleWordFreq.end(); iter++){
            if(key->second.second < iter->second.second){
                key = iter;
            }
        }
        outf << key->second.first << "\t\t" << key->second.second << endl;//write in file
        temp.insert(*key);//copy in temp
        singleWordFreq.erase(key);//and then delete(for select use)
    }
    for (auto iter = temp.begin(); iter != temp.end(); iter++){
        singleWordFreq.insert(*iter);//insert top 10 words back
    }
    outf.close();
}

//write top 10 phrases, similar as above
void FileWordCounter::writeDouW(){
    int size = int(doubleWordFreq.size());
    int length = min(10, size);
    ofstream outf("result.txt",ios::app);
    outf << endl << "the top ten frequency of phrase: " << endl;
    for(int i = 0; i < length; i++){
        auto key = doubleWordFreq.begin();
        for (auto iter = doubleWordFreq.begin(); iter != doubleWordFreq.end(); iter++){
            if(key->second < iter->second){
                key = iter;
            }
        }
        outf << singleWordFreq[key->first.first].first << ' ' << singleWordFreq[key->first.second].first << "\t\t" << key->second << endl;
        doubleWordFreq.erase(key);
    }
}


int main(int argc,char* argv[]) {
    if(argc <= 1){
        cout << "ERROR: No such file or directory" << endl;
        return -1;
    }
    FileWordCounter path(argv[1]);
    path.read();
    path.write();
    return 0;
}

秒客网

第一次个人作业

第一次个人作业

要求

基本功能

PSP表格

整体设计

测试

代码质量分析

性能分析

小结

多说一句

相关文章