第一次个人作业
$( "#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;
}