Last updated on 8 months ago
排序问题虽然有了解，很多只是基于理论上，实践比较少，刚好最近遇到个问题：
这个以前遇到过类似的问题， 假如 你有一个20GB的文件，对文件的内容排序，内存限制在 1G，你要怎么排序
以前有做过总结，就是分割文件，逐个文件先排好序，最后然后再合并，说起来很简单，但做起来就。。。。
这次题目有 分割文件，我下载了这个压缩包，解压 看有1000个 20M的文件
思路： 将这个一 千个文件，文件名读取出来，按照条件逐个抽出来，并且排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void read_lryic(char *path)
{
DIR *dir = opendir(path);
cout << path << endl;
struct dirent *entry;
int i = 0;
while ((entry = readdir(dir)) != 0)
{
if (strstr(entry->d_name, ".txt"))
{
filename.push_back(entry->d_name);
printf(" %d %s\n", i++, entry->d_name);
}
}
}
|
现在文件名有了，进行筛选排序，这里用map来存放临时的数据，key 为时间戳，value 为对应的数据，为什么用map，map是会自动自动排序，根据key的值，而这里的没条数据都是 json，用了一个jsoncpp 库（如果用 go 估计已经写完了），原本想直接解析字符串，发现有点麻烦，还是用库吧， 提取出 时间戳，作为key，提取完一个文件后，重新写入到新的文件里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| void sortfile(){
Json::Reader reader;
Json::Value obj;
read_lryic("/home/hrp/Cpp/recore/");
string file;
for (auto str : filename){
file = "/home/hrp/Cpp/recore/" + str;
std::ifstream fIn(file);
int i = 0;
if (fIn)
{
std::string str;
while (std::getline(fIn, str))
{
if(str.find("张三") != string::npos){
reader.parse(str, obj);
long timestamp = obj["timestamp"].asInt64();
ret[timestamp] = str;
}
}
cout << file << endl;
}
else
{
std::cout << "Open file faild." << std::endl;
}
ofstream out1(file);
for(auto i=ret.begin();i!=ret.end();i++){
out1 << i->second ;
out1 << "\n" ;
}
ret.clear();
out1.close();
}
}
|
现在完成 按照条件 完成每个文件的排序了
接下来就是 归并，如何归并呢，现在有1000个文件，逐个遍历这1000个文件，每次都提取一行来，一次遍历 提取了1000行数据，此时可以用大顶堆的特性，就是1000个数据放进这个大顶堆，堆顶肯定是最大数，按照这个特性，先读取一千条，放在大顶堆了，每次 pop出堆顶的（肯定最大），然后要 补上一个，读哪个文件的呢，肯定是pop出去哪条数据所在的文件，所以现在就是要去那个文件里再读一条数据，以此类推，说是这样说 ，但是这题还有其他附加条件（根据时间分类写）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| clock_t start,end;
start = clock();
Json::Reader reader;
Json::Value obj;
map<string,ifstream*> filesmap;
map<string,ofstream*> outfile;
sortfile();
time_t tt;
struct tm *ttime;
for(auto file: filename){
auto temp = file;
file = "/home/hrp/Cpp/recore/" + temp;
filesmap.emplace(file, new ifstream(file));
}
priority_queue<pair<long, string>> topTime;
map<long,string> Temp;
string data;
for(auto iter = filesmap.begin(); iter != filesmap.end(); iter++) {
std::getline(*iter->second, data);
reader.parse(data, obj);
long timestamp = obj["timestamp"].asInt64();
pair<long,string> b(timestamp,iter->first);
topTime.push(b);
Temp[timestamp] = data;
}
while (!topTime.empty()){
struct tm *ttime;
tt = topTime.top().first/1000;
ttime = localtime(&tt);
char formatime[64];
strftime(formatime, 64, "%Y-%m-%d", ttime);
string strtime(formatime);
if(outfile.count(strtime) == 0){
outfile.emplace(strtime,new ofstream(strtime));
if (!outfile[strtime]->is_open())
cout << strtime << "error" << endl;
*outfile[strtime] << Temp[topTime.top().first]+ "\n";
Temp.erase(topTime.top().first);
}else{
*outfile[strtime] << Temp[topTime.top().first] + "\n";
Temp.erase(topTime.top().first);
}
auto TopTemp = topTime.top();
topTime.pop();
if(std::getline(*filesmap[TopTemp.second], data)){
reader.parse(data, obj);
long timestamp = obj["timestamp"].asInt64();
pair<long,string> b(timestamp,TopTemp.second);
Temp[timestamp] = data;
topTime.push(b);
}
}
for(auto iter = outfile.begin(); iter != outfile.end(); iter++) {
iter->second->close();
}
end = clock();
cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
|
运行的机器是： 腾讯云服务器 4核 4g
总结：
- 认清了 知道 和 做到的差距！！！！！
- 有些api 日常少使用， 很不收悉，都是在查查查
- 要先有整体思路 然后细化问题，逐个解决
代码整体设计 不是很好，后续在改进， 用多线程 多路归并？