简介
还是强调一下，本人菜鸡一枚，但是对于顶级coder也是很向往的，今年因为个人的原因可能不能走的很远。但是还是想多学习一下。以下代码来自 --大学 同学，杨菲菲
提升思路
加速 IO
多线程
减少内存的申请和释放
更新算法
code
/*
* @Author: your name
* @Date: 2020-04-17 10:43:11
* @LastEditTime: 2020-04-17 10:43:42
* @LastEditors: Please set LastEditors
* @Description: In User Settings Edit
* @FilePath: codelesson_1.cpp
*/
#define _LINUX
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <thread>
#include <cstring>
#include <time.h>
#ifdef _LINUX
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#endif
#define _CRT_SECURE_NO_WARNINGS // 防止 fopen 和 fscanf 报错
static bool vis[600000];
static int Gout[600000][100]; // 记录出边, Gout[i][j]表示结点i第j条出边所连接的结点
static int Gin[600000][500]; // 记录入边, Gin[i][j]表示结点i第j条入边所连接的结点
static int pOut[600000]; // 每个结点出边索引j
static int pIn[600000]; // 每个结点入边索引
struct Path {
// ID最小的第一个输出；
// 总体按照循环转账路径长度升序排序；
// 同一级别的路径长度下循环转账账号ID序列，按照字典序（ID转为无符号整数后）升序排序
int length;
std::vector<unsigned int> path;
Path(int length, const std::vector<unsigned int> &path) : length(length), path(path) {}
bool operator<(const Path&rhs)const
{ //在排序的时候有用
if (length != rhs.length) return length < rhs.length; // length 从小到大
for (int i = 0; i < length; i++) {
if (path[i] != rhs.path[i]) // 字典序
return path[i] < rhs.path[i];
}
}
};
class Solution {
public:
std::unordered_map<unsigned int, int> idHash; // sorted id to 0...n
std::vector<unsigned int> ids; // 0...n to sorted id
std::vector<unsigned int> inputs; // u-v pairs
std::vector<int> path;
std::vector<Path> ans;
int nodeCnt;
#ifdef _LINUX
void parseInput(std::string &testFile)
{
int fd = open(testFile.c_str(), O_RDONLY);
int len = lseek(fd, 0, SEEK_END);
char *mbuf = (char *)mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
if(fd != -1) {
close(fd);
}
unsigned int offset = 0, cnt = 0;;
unsigned int u, v, c;
for(int i = 0; i < len; i++) {
if(mbuf[i] == '
') {
mbuf[i] = ' ';
sscanf(mbuf + offset, "%u,%u,%u", &u, &v, &c);
offset = i + 2; // 跳过 /r/n
inputs.push_back(u);
inputs.push_back(v);
++cnt;
}
}
munmap(mbuf, len);
}
#else
void parseInput(std::string &testFile)
{
FILE* file = fopen(testFile.c_str(), "r");
unsigned int u, v, c;
int cnt = 0;
while (fscanf(file, "%u,%u,%u", &u, &v, &c) != EOF) {
inputs.push_back(u);
inputs.push_back(v);
++cnt;
}
if(file != NULL) {
fclose(file);
}
#ifdef TEST
printf("%d Records in Total
", cnt); // 输出总共存储了多少条数据
#endif
}
#endif
void constructGraph()
{
std::vector<unsigned int> tmp = inputs;
sort(tmp.begin(), tmp.end()); // 对所有id进行排序
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); // 独一无二的tmp了
ids = tmp;
nodeCnt = 0;
for(int i = 0; i < tmp.size(); i++) {
idHash[tmp[i]] = nodeCnt++;
}
#ifdef TEST
printf("%d Nodes in Total
", nodeCnt);
#endif
int sz = inputs.size();
memset(pOut, 0, sizeof(pOut));
memset(pIn, 0, sizeof(pIn));
for (int i = 0; i < sz; i += 2) {
int u = idHash[inputs[i]], v = idHash[inputs[i + 1]];
Gout[u][pOut[u]++] = v;
Gin[v][pIn[v]++] = u;
}
}
void dfs(int head, int cur, int depth)
{
vis[cur] = true; // 当前节点已经访问过
path.push_back(cur); // 路径中存入当前节点
for(int i = 0; i < pOut[cur]; i++) {
int v = Gout[cur][i];
if (v == head && depth >= 3 && depth <= 7) { // 如果当前节点的一个出度是头结点，那么就是一个答案
std::vector<unsigned int> tmp;
for(int j = 0; j < path.size(); j++)
tmp.push_back(ids[path[j]]);
ans.emplace_back(Path(depth, tmp)); // 等于push_back 不会触发 不需要触发拷贝构造和转移构造
}
if (depth < 7 && !vis[v] && v > head) {
dfs(head, v, depth + 1);
}
}
vis[cur] = false;
path.pop_back();
}
// search from 0...n
// 由于要求id最小的在前，因此搜索的全过程中不考虑比起点id更小的节点
void solve()
{
for (int i = 0; i < nodeCnt; i++) {
if (pOut[i] && pIn[i]) { // 如果节点i对应的节点 有出度的话开启这个节点的dfs
dfs(i, i, 1);
}
}
sort(ans.begin(), ans.end());
}
void save(std::string &outputFile)
{
std::ostringstream os;
os << ans.size() << std::endl;
for(int k = 0; k < ans.size(); k++) {
std::vector<unsigned int> path = ans[k].path;
int sz = path.size();
os << path[0];
for (int i = 1; i < sz; i++) {
os << "," << path[i];
}
os << std::endl;
}
FILE * fp = fopen(outputFile.c_str(), "w" );
fwrite(os.str().c_str(), os.str().length(), 1, fp);
fclose(fp);
}
};
int main()
{
std::string testFile = "/data/test_data.txt";
std::string outputFile = "/projects/student/result.txt";
#ifdef TEST
std::string answerFile = "C:/Users/lee/Desktop/code/华为软件精英挑战赛/初赛/初赛赛题/result.txt";
#endif
Solution solution; // 构建一个解决方案类
solution.parseInput(testFile); // 读取数据将 id1,id2,money id1和id2 存储在 std::vector<unsigned int> inputs;
solution.constructGraph(); // 构建图
//solution.topoSort();
solution.solve(); //解决它
solution.save(outputFile);
return 0;
}
分数
5.5
结论
内存的申请和释放占据了大量时间。读取数据和写入数据 采用的mmap可以加速数据的读取和写入