技术宅的结界

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

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 373|回复: 1
收起左侧

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

[复制链接]

7

主题

18

帖子

210

积分

用户组: 中·技术宅

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

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

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

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

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

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



第一个层次很简单 单机 一个小文件 读进来进行处理 然后对每个单词进行统计排序 记录每个单词出现频率
[C++] 纯文本查看 复制代码
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <sstream>
#include <fstream>
 
using namespace std;
 
std::unordered_map<std::string, int> mapStringFrequent;
 
 
void SplitStrig(std::string& line, std::vector<std::string>& vecString) {
    typedef std::string::size_type strSize;
    strSize i = 0;
    while (i != line.size()) {
        while (i != line.size() && isspace(line[i]))
            ++i;
        strSize j = i;
        while (j != line.size() && !isspace(line[j]))
            ++j;
        if (i != j) {
            vecString.push_back(line.substr(i, j - i));
            i = j;
        }
    }
}
 
bool CheckWord(std::string s) {
    typedef std::string::size_type strSize;
    strSize i = 0;
    while (i != s.size()) {
        if (isalpha(s[i])) {
            i++;
        }
        else {
            return false;
        }
    }
    return true;
}
 
 
 
void VecInputMap(std::vector<std::string>& vecString, std::unordered_map<std::string, int>& mapStringFrequent) {
    for (auto it : vecString) {
        if (CheckWord(it)) {
            transform(it.begin(), it.end(), it.begin(), ::tolower);
            mapStringFrequent[it]++;
        }
    }
}
 
 
bool ReadFile(const string& fileName) {
    bool ret = false;
    std::ifstream in(fileName);
    if (in.bad() || !in) {
        return ret;
    }
    std::string line;
    std::vector<std::string> vecString;
    try {
        while (getline(in, line))
        {
            //std::cout << line <<  std::endl;
            SplitStrig(line, vecString);
        }
 
        VecInputMap(vecString, mapStringFrequent);
    }
    catch (std::exception& e) {
        std::cout << line << std::endl;
        in.close();
        std::cerr << e.what() << std::endl;
        return ret;
    }
 
    in.close();
    ret = true;
    return ret;
}
 
 
void WriteToFile(const string& fileName, std::vector<std::pair<int, std::string>>& vecWordFreq) {
    std::ofstream out(fileName);
    if (out.bad() || !out) {
        return;
    }
 
    for (auto& it : vecWordFreq) {
        out << it.second << '\t' << it.first << std::endl;
    }
    out.close();
 
}
//============================================================
 
int main()
{
    bool ret = ReadFile("1.txt");
    if (!ret)
        return -1;
 
    //ret = ReadFile("2.txt");
    //if (!ret)
    //  return -1;
    //ret = ReadFile("3.txt");
    //if (!ret)
    //  return -1;
    //ret = ReadFile("4.txt");
    //if (!ret)
    //  return -1;
 
    //ret = ReadFile("5.txt");
    //if (!ret)
    //  return -1;
 
    //ret = ReadFile("6.txt");
    //if (!ret)
    //  return -1;
 
    //ret = ReadFile("7.txt");
    //if (!ret)
    //  return -1;
 
    //ret = ReadFile("8.txt");
    //if (!ret)
    //  return -1;
 
    //ret = ReadFile("9.txt");
    //if (!ret)
    //  return -1;
 
    //ret = ReadFile("10.txt");
    //if (!ret)
    //  return -1;
 
    std::vector<std::pair<int, std::string>> freq;
    freq.reserve(mapStringFrequent.size());
 
    for (auto& it : mapStringFrequent){
        freq.push_back(make_pair(it.second, it.first));
    }
 
    std::sort(freq.begin(), freq.end(), [](const std::pair<int, std::string>& lhs,  // const auto& lhs in C++14
            const std::pair<int, std::string>& rhs) {
        return lhs.first > rhs.first;
    });
 
    //for (auto it : freq) {
    //  std::cout << it.first << '\t' << it.second << '\n';
    //}
 
    WriteToFile("freqResult.txt", freq);
    return 0;
}
第二个层次 就是文件较大 单词量较多 如果一次性读入并使用vector容器存放 以及使用hash容器进行统计频率 会出现内存等资源不足现象

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

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

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

这样我们就得到多个记录单词出现频率的文本 供后继步骤分析合并 但是一个单词的出现频率肯定只出现在一个记录文本中(因为相同的单词具有相同的hash值 对应同一个记录文本)
如图
1.png
[C++] 纯文本查看 复制代码
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <sstream>
#include <fstream>
 
using namespace std;
 
#define BUCKET_NUM  10
std::unordered_map<std::string, int> mapStringFrequent[BUCKET_NUM];
std::ofstream out[BUCKET_NUM];
 
 
#define MAX_WORD_SIZE   1024*1024
 
 
void SplitStrig(std::string& line, std::vector<std::string>& vecString) {
    typedef std::string::size_type strSize;
    strSize i = 0;
    while (i != line.size()) {
        while (i != line.size() && isspace(line[i]))
            ++i;
        strSize j = i;
        while (j != line.size() && !isspace(line[j]))
            ++j;
        if (i != j) {
            vecString.push_back(line.substr(i, j - i));
            i = j;
        }
    }
}
 
bool CheckWord(std::string s) {
    typedef std::string::size_type strSize;
    strSize i = 0;
    while (i != s.size()) {
        if (isalpha(s[i])) {
            i++;
        }
        else {
            return false;
        }
    }
    return true;
}
 
void VecInputMap(std::vector<std::string>& vecString, std::unordered_map<std::string, int> mapStringFrequent[]) {
    for (auto it : vecString) {
        if (CheckWord(it)) {
            transform(it.begin(), it.end(), it.begin(), ::tolower);
            int idx = std::hash<string>()(it) % BUCKET_NUM;
            mapStringFrequent[idx][it]++;
            if (mapStringFrequent[idx].size() >= MAX_WORD_SIZE) {
                for (auto& it : mapStringFrequent[idx]) {
                    out[idx] << it.second << '\t' << it.first << std::endl;
                }
                mapStringFrequent[idx].clear();
            }
        }
    }
}
 
bool ReadFile(const string& fileName) {
    bool ret = false;
    std::ifstream in(fileName);
    if (in.bad() || !in) {
        return ret;
    }
    std::string line;
    std::vector<std::string> vecString;
 
    try {
        while (getline(in, line))
        {
            SplitStrig(line, vecString);
            //std::cout << line << std::endl;
            if (vecString.size() >= MAX_WORD_SIZE) {
                //std::cout << "too many words" << std::endl;
                VecInputMap(vecString, mapStringFrequent);
                vecString.clear();
            }
        }
 
        for (int i = 0; i < BUCKET_NUM; i++) {
            for (auto& it : mapStringFrequent[i]) {
                out[i] << it.second << '\t' << it.first << std::endl;
            }
            mapStringFrequent[i].clear();
        }
 
    }
    catch (std::exception& e) {
        in.close();
        std::cerr << e.what() << std::endl;
        return ret;
    }
 
    std::cout << vecString.size() << std::endl;
    ret = true;
    return ret;
}
 
int main()
{
    std::string fileName = "0bucket.txt";
    for (int i = 0; i < BUCKET_NUM; i++) {
        out[i].close();
        out[i].open(fileName);
        fileName[0]++;
    }
 
    ReadFile("LargeFile.txt");
 
     
    return 0;
}
运行效果如图

运行前

1.png

运行后

2.png

993

主题

2190

帖子

5万

积分

用户组: 管理员

一只技术宅

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

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2018-7-22 18:39 , Processed in 0.083453 second(s), 17 queries , Gzip On, Memcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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