找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 3195|回复: 1

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

[复制链接]

7

主题

11

回帖

218

积分

用户组: 中·技术宅

UID
536
精华
1
威望
16 点
宅币
154 个
贡献
9 次
宅之契约
0 份
在线时间
3 小时
注册时间
2014-11-6
发表于 2017-3-3 09:49:09 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
技术博客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. using namespace std;

  8. std::unordered_map<std::string, int> mapStringFrequent;


  9. void SplitStrig(std::string& line, std::vector<std::string>& vecString) {
  10.     typedef std::string::size_type strSize;
  11.     strSize i = 0;
  12.     while (i != line.size()) {
  13.         while (i != line.size() && isspace(line[i]))
  14.             ++i;
  15.         strSize j = i;
  16.         while (j != line.size() && !isspace(line[j]))
  17.             ++j;
  18.         if (i != j) {
  19.             vecString.push_back(line.substr(i, j - i));
  20.             i = j;
  21.         }
  22.     }
  23. }

  24. bool CheckWord(std::string s) {
  25.     typedef std::string::size_type strSize;
  26.     strSize i = 0;
  27.     while (i != s.size()) {
  28.         if (isalpha(s[i])) {
  29.             i++;
  30.         }
  31.         else {
  32.             return false;
  33.         }
  34.     }
  35.     return true;
  36. }



  37. void VecInputMap(std::vector<std::string>& vecString, std::unordered_map<std::string, int>& mapStringFrequent) {
  38.     for (auto it : vecString) {
  39.         if (CheckWord(it)) {
  40.             transform(it.begin(), it.end(), it.begin(), ::tolower);
  41.             mapStringFrequent[it]++;
  42.         }
  43.     }
  44. }


  45. bool ReadFile(const string& fileName) {
  46.     bool ret = false;
  47.     std::ifstream in(fileName);
  48.     if (in.bad() || !in) {
  49.         return ret;
  50.     }
  51.     std::string line;
  52.     std::vector<std::string> vecString;
  53.     try {
  54.         while (getline(in, line))
  55.         {
  56.             //std::cout << line <<  std::endl;
  57.             SplitStrig(line, vecString);
  58.         }

  59.         VecInputMap(vecString, mapStringFrequent);
  60.     }
  61.     catch (std::exception& e) {
  62.         std::cout << line << std::endl;
  63.         in.close();
  64.         std::cerr << e.what() << std::endl;
  65.         return ret;
  66.     }

  67.     in.close();
  68.     ret = true;
  69.     return ret;
  70. }


  71. void WriteToFile(const string& fileName, std::vector<std::pair<int, std::string>>& vecWordFreq) {
  72.     std::ofstream out(fileName);
  73.     if (out.bad() || !out) {
  74.         return;
  75.     }

  76.     for (auto& it : vecWordFreq) {
  77.         out << it.second << '\t' << it.first << std::endl;
  78.     }
  79.     out.close();

  80. }
  81. //============================================================

  82. int main()
  83. {
  84.     bool ret = ReadFile("1.txt");
  85.     if (!ret)
  86.         return -1;

  87.     //ret = ReadFile("2.txt");
  88.     //if (!ret)
  89.     //  return -1;
  90.     //ret = ReadFile("3.txt");
  91.     //if (!ret)
  92.     //  return -1;
  93.     //ret = ReadFile("4.txt");
  94.     //if (!ret)
  95.     //  return -1;

  96.     //ret = ReadFile("5.txt");
  97.     //if (!ret)
  98.     //  return -1;

  99.     //ret = ReadFile("6.txt");
  100.     //if (!ret)
  101.     //  return -1;

  102.     //ret = ReadFile("7.txt");
  103.     //if (!ret)
  104.     //  return -1;

  105.     //ret = ReadFile("8.txt");
  106.     //if (!ret)
  107.     //  return -1;

  108.     //ret = ReadFile("9.txt");
  109.     //if (!ret)
  110.     //  return -1;

  111.     //ret = ReadFile("10.txt");
  112.     //if (!ret)
  113.     //  return -1;

  114.     std::vector<std::pair<int, std::string>> freq;
  115.     freq.reserve(mapStringFrequent.size());

  116.     for (auto& it : mapStringFrequent){
  117.         freq.push_back(make_pair(it.second, it.first));
  118.     }

  119.     std::sort(freq.begin(), freq.end(), [](const std::pair<int, std::string>& lhs,  // const auto& lhs in C++14
  120.             const std::pair<int, std::string>& rhs) {
  121.         return lhs.first > rhs.first;
  122.     });

  123.     //for (auto it : freq) {
  124.     //  std::cout << it.first << '\t' << it.second << '\n';
  125.     //}

  126.     WriteToFile("freqResult.txt", freq);
  127.     return 0;
  128. }
复制代码
第二个层次 就是文件较大 单词量较多 如果一次性读入并使用vector容器存放 以及使用hash容器进行统计频率 会出现内存等资源不足现象

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

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

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

这样我们就得到多个记录单词出现频率的文本 供后继步骤分析合并 但是一个单词的出现频率肯定只出现在一个记录文本中(因为相同的单词具有相同的hash值 对应同一个记录文本)
如图
1.png
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <unordered_map>
  4. #include <vector>
  5. #include <sstream>
  6. #include <fstream>

  7. using namespace std;

  8. #define BUCKET_NUM  10
  9. std::unordered_map<std::string, int> mapStringFrequent[BUCKET_NUM];
  10. std::ofstream out[BUCKET_NUM];


  11. #define MAX_WORD_SIZE   1024*1024


  12. void SplitStrig(std::string& line, std::vector<std::string>& vecString) {
  13.     typedef std::string::size_type strSize;
  14.     strSize i = 0;
  15.     while (i != line.size()) {
  16.         while (i != line.size() && isspace(line[i]))
  17.             ++i;
  18.         strSize j = i;
  19.         while (j != line.size() && !isspace(line[j]))
  20.             ++j;
  21.         if (i != j) {
  22.             vecString.push_back(line.substr(i, j - i));
  23.             i = j;
  24.         }
  25.     }
  26. }

  27. bool CheckWord(std::string s) {
  28.     typedef std::string::size_type strSize;
  29.     strSize i = 0;
  30.     while (i != s.size()) {
  31.         if (isalpha(s[i])) {
  32.             i++;
  33.         }
  34.         else {
  35.             return false;
  36.         }
  37.     }
  38.     return true;
  39. }

  40. void VecInputMap(std::vector<std::string>& vecString, std::unordered_map<std::string, int> mapStringFrequent[]) {
  41.     for (auto it : vecString) {
  42.         if (CheckWord(it)) {
  43.             transform(it.begin(), it.end(), it.begin(), ::tolower);
  44.             int idx = std::hash<string>()(it) % BUCKET_NUM;
  45.             mapStringFrequent[idx][it]++;
  46.             if (mapStringFrequent[idx].size() >= MAX_WORD_SIZE) {
  47.                 for (auto& it : mapStringFrequent[idx]) {
  48.                     out[idx] << it.second << '\t' << it.first << std::endl;
  49.                 }
  50.                 mapStringFrequent[idx].clear();
  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.             SplitStrig(line, vecString);
  67.             //std::cout << line << std::endl;
  68.             if (vecString.size() >= MAX_WORD_SIZE) {
  69.                 //std::cout << "too many words" << std::endl;
  70.                 VecInputMap(vecString, mapStringFrequent);
  71.                 vecString.clear();
  72.             }
  73.         }

  74.         for (int i = 0; i < BUCKET_NUM; i++) {
  75.             for (auto& it : mapStringFrequent[i]) {
  76.                 out[i] << it.second << '\t' << it.first << std::endl;
  77.             }
  78.             mapStringFrequent[i].clear();
  79.         }

  80.     }
  81.     catch (std::exception& e) {
  82.         in.close();
  83.         std::cerr << e.what() << std::endl;
  84.         return ret;
  85.     }

  86.     std::cout << vecString.size() << std::endl;
  87.     ret = true;
  88.     return ret;
  89. }

  90. int main()
  91. {
  92.     std::string fileName = "0bucket.txt";
  93.     for (int i = 0; i < BUCKET_NUM; i++) {
  94.         out[i].close();
  95.         out[i].open(fileName);
  96.         fileName[0]++;
  97.     }

  98.     ReadFile("LargeFile.txt");

  99.      
  100.     return 0;
  101. }
复制代码
运行效果如图

运行前

1.png

运行后

2.png
回复

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2017-3-8 22:16:00 | 显示全部楼层
我已编辑代码部分的帖子,用了代码上色。
discuz一个大坑就是[i]和[/i]是斜体,但C系代码中经常会出现用[i]引用数组元素的语法,导致莫名其妙的斜体……
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 05:56 , Processed in 0.045779 second(s), 35 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表