统计单词出现频率及排序 从单机到多机合作 图文示例

def

技术博客http://www.cnblogs.com/itdef/  http://blog.csdn.net/stecdeng 技术交流群 群号码：324164944 欢迎c c++ windows驱动爱好者 服务器程序员沟通交流
本文是学习 多线程服务端编程的练习

书籍作者陈硕的博客也有提到这个题目

http://blog.csdn.net/solstice/article/details/8497475



第一个层次很简单 单机 一个小文件 读进来进行处理 然后对每个单词进行统计排序 记录每个单词出现频率

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <unordered_map>
   
4. #include <vector>
   
5. #include <sstream>
   
6. #include <fstream>
   
7. 
   
8. using namespace std;
   
9. 
   
10. std::unordered_map<std::string, int> mapStringFrequent;
    
11. 
    
12. 
    
13. void SplitStrig(std::string& line, std::vector<std::string>& vecString) {
    
14.     typedef std::string::size_type strSize;
    
15.     strSize i = 0;
    
16.     while (i != line.size()) {
    
17.         while (i != line.size() && isspace(line[i]))
    
18.             ++i;
    
19.         strSize j = i;
    
20.         while (j != line.size() && !isspace(line[j]))
    
21.             ++j;
    
22.         if (i != j) {
    
23.             vecString.push_back(line.substr(i, j - i));
    
24.             i = j;
    
25.         }
    
26.     }
    
27. }
    
28. 
    
29. bool CheckWord(std::string s) {
    
30.     typedef std::string::size_type strSize;
    
31.     strSize i = 0;
    
32.     while (i != s.size()) {
    
33.         if (isalpha(s[i])) {
    
34.             i++;
    
35.         }
    
36.         else {
    
37.             return false;
    
38.         }
    
39.     }
    
40.     return true;
    
41. }
    
42. 
    
43. 
    
44. 
    
45. void VecInputMap(std::vector<std::string>& vecString, std::unordered_map<std::string, int>& mapStringFrequent) {
    
46.     for (auto it : vecString) {
    
47.         if (CheckWord(it)) {
    
48.             transform(it.begin(), it.end(), it.begin(), ::tolower);
    
49.             mapStringFrequent[it]++;
    
50.         }
    
51.     }
    
52. }
    
53. 
    
54. 
    
55. bool ReadFile(const string& fileName) {
    
56.     bool ret = false;
    
57.     std::ifstream in(fileName);
    
58.     if (in.bad() || !in) {
    
59.         return ret;
    
60.     }
    
61.     std::string line;
    
62.     std::vector<std::string> vecString;
    
63.     try {
    
64.         while (getline(in, line))
    
65.         {
    
66.             //std::cout << line <<  std::endl;
    
67.             SplitStrig(line, vecString);
    
68.         }
    
69. 
    
70.         VecInputMap(vecString, mapStringFrequent);
    
71.     }
    
72.     catch (std::exception& e) {
    
73.         std::cout << line << std::endl;
    
74.         in.close();
    
75.         std::cerr << e.what() << std::endl;
    
76.         return ret;
    
77.     }
    
78. 
    
79.     in.close();
    
80.     ret = true;
    
81.     return ret;
    
82. }
    
83. 
    
84. 
    
85. void WriteToFile(const string& fileName, std::vector<std::pair<int, std::string>>& vecWordFreq) {
    
86.     std::ofstream out(fileName);
    
87.     if (out.bad() || !out) {
    
88.         return;
    
89.     }
    
90. 
    
91.     for (auto& it : vecWordFreq) {
    
92.         out << it.second << '\t' << it.first << std::endl;
    
93.     }
    
94.     out.close();
    
95. 
    
96. }
    
97. //============================================================
    
98. 
    
99. int main()
    
100. {
     
101.     bool ret = ReadFile("1.txt");
     
102.     if (!ret)
     
103.         return -1;
     
104. 
     
105.     //ret = ReadFile("2.txt");
     
106.     //if (!ret)
     
107.     //  return -1;
     
108.     //ret = ReadFile("3.txt");
     
109.     //if (!ret)
     
110.     //  return -1;
     
111.     //ret = ReadFile("4.txt");
     
112.     //if (!ret)
     
113.     //  return -1;
     
114. 
     
115.     //ret = ReadFile("5.txt");
     
116.     //if (!ret)
     
117.     //  return -1;
     
118. 
     
119.     //ret = ReadFile("6.txt");
     
120.     //if (!ret)
     
121.     //  return -1;
     
122. 
     
123.     //ret = ReadFile("7.txt");
     
124.     //if (!ret)
     
125.     //  return -1;
     
126. 
     
127.     //ret = ReadFile("8.txt");
     
128.     //if (!ret)
     
129.     //  return -1;
     
130. 
     
131.     //ret = ReadFile("9.txt");
     
132.     //if (!ret)
     
133.     //  return -1;
     
134. 
     
135.     //ret = ReadFile("10.txt");
     
136.     //if (!ret)
     
137.     //  return -1;
     
138. 
     
139.     std::vector<std::pair<int, std::string>> freq;
     
140.     freq.reserve(mapStringFrequent.size());
     
141. 
     
142.     for (auto& it : mapStringFrequent){
     
143.         freq.push_back(make_pair(it.second, it.first));
     
144.     }
     
145. 
     
146.     std::sort(freq.begin(), freq.end(), [](const std::pair<int, std::string>& lhs,  // const auto& lhs in C++14
     
147.             const std::pair<int, std::string>& rhs) {
     
148.         return lhs.first > rhs.first;
     
149.     });
     
150. 
     
151.     //for (auto it : freq) {
     
152.     //  std::cout << it.first << '\t' << it.second << '\n';
     
153.     //}
     
154. 
     
155.     WriteToFile("freqResult.txt", freq);
     
156.     return 0;
     
157. }

复制代码

第二个层次 就是文件较大 单词量较多 如果一次性读入并使用vector容器存放 以及使用hash容器进行统计频率 会出现内存等资源不足现象

那么就依次读取进内存 将解析的单词存放进vector中，当vector中的容量到达一个阈值 将vector中的单词放进map容器中统计单词出现频率 vector容器清空

但是map容器有多个 各个单词存放进那个map容器根据hash函数决定  

当map容器的容量达到阈值后 写入文件 map容器清空

这样我们就得到多个记录单词出现频率的文本 供后继步骤分析合并 但是一个单词的出现频率肯定只出现在一个记录文本中(因为相同的单词具有相同的hash值 对应同一个记录文本)
如图

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <unordered_map>
   
4. #include <vector>
   
5. #include <sstream>
   
6. #include <fstream>
   
7. 
   
8. using namespace std;
   
9. 
   
10. #define BUCKET_NUM  10
    
11. std::unordered_map<std::string, int> mapStringFrequent[BUCKET_NUM];
    
12. std::ofstream out[BUCKET_NUM];
    
13. 
    
14. 
    
15. #define MAX_WORD_SIZE   1024*1024
    
16. 
    
17. 
    
18. void SplitStrig(std::string& line, std::vector<std::string>& vecString) {
    
19.     typedef std::string::size_type strSize;
    
20.     strSize i = 0;
    
21.     while (i != line.size()) {
    
22.         while (i != line.size() && isspace(line[i]))
    
23.             ++i;
    
24.         strSize j = i;
    
25.         while (j != line.size() && !isspace(line[j]))
    
26.             ++j;
    
27.         if (i != j) {
    
28.             vecString.push_back(line.substr(i, j - i));
    
29.             i = j;
    
30.         }
    
31.     }
    
32. }
    
33. 
    
34. bool CheckWord(std::string s) {
    
35.     typedef std::string::size_type strSize;
    
36.     strSize i = 0;
    
37.     while (i != s.size()) {
    
38.         if (isalpha(s[i])) {
    
39.             i++;
    
40.         }
    
41.         else {
    
42.             return false;
    
43.         }
    
44.     }
    
45.     return true;
    
46. }
    
47. 
    
48. void VecInputMap(std::vector<std::string>& vecString, std::unordered_map<std::string, int> mapStringFrequent[]) {
    
49.     for (auto it : vecString) {
    
50.         if (CheckWord(it)) {
    
51.             transform(it.begin(), it.end(), it.begin(), ::tolower);
    
52.             int idx = std::hash<string>()(it) % BUCKET_NUM;
    
53.             mapStringFrequent[idx][it]++;
    
54.             if (mapStringFrequent[idx].size() >= MAX_WORD_SIZE) {
    
55.                 for (auto& it : mapStringFrequent[idx]) {
    
56.                     out[idx] << it.second << '\t' << it.first << std::endl;
    
57.                 }
    
58.                 mapStringFrequent[idx].clear();
    
59.             }
    
60.         }
    
61.     }
    
62. }
    
63. 
    
64. bool ReadFile(const string& fileName) {
    
65.     bool ret = false;
    
66.     std::ifstream in(fileName);
    
67.     if (in.bad() || !in) {
    
68.         return ret;
    
69.     }
    
70.     std::string line;
    
71.     std::vector<std::string> vecString;
    
72. 
    
73.     try {
    
74.         while (getline(in, line))
    
75.         {
    
76.             SplitStrig(line, vecString);
    
77.             //std::cout << line << std::endl;
    
78.             if (vecString.size() >= MAX_WORD_SIZE) {
    
79.                 //std::cout << "too many words" << std::endl;
    
80.                 VecInputMap(vecString, mapStringFrequent);
    
81.                 vecString.clear();
    
82.             }
    
83.         }
    
84. 
    
85.         for (int i = 0; i < BUCKET_NUM; i++) {
    
86.             for (auto& it : mapStringFrequent[i]) {
    
87.                 out[i] << it.second << '\t' << it.first << std::endl;
    
88.             }
    
89.             mapStringFrequent[i].clear();
    
90.         }
    
91. 
    
92.     }
    
93.     catch (std::exception& e) {
    
94.         in.close();
    
95.         std::cerr << e.what() << std::endl;
    
96.         return ret;
    
97.     }
    
98. 
    
99.     std::cout << vecString.size() << std::endl;
    
100.     ret = true;
     
101.     return ret;
     
102. }
     
103. 
     
104. int main()
     
105. {
     
106.     std::string fileName = "0bucket.txt";
     
107.     for (int i = 0; i < BUCKET_NUM; i++) {
     
108.         out[i].close();
     
109.         out[i].open(fileName);
     
110.         fileName[0]++;
     
111.     }
     
112. 
     
113.     ReadFile("LargeFile.txt");
     
114. 
     
115.      
     
116.     return 0;
     
117. }

复制代码

运行效果如图

运行前



运行后

0xAA55

我已编辑代码部分的帖子，用了代码上色。
discuz一个大坑就是[i]和[/i]是斜体，但C系代码中经常会出现用[i]引用数组元素的语法，导致莫名其妙的斜体……