这道题来源于IBM power8算法挑战赛第三期,以下是给出的比赛规则:
比赛规则
由CSDN提供30万篇文章浏览记录(总计1000万次),用户需要将曝光次数最多的T0P100文章输出。
参赛者可以使用任意基于Linux平台的开发语言完成挑战。
参赛者提交的文件 第一列是id,第二列是出现次数。列之间使用两个\t。按次数从高到底排列,取前111个(目的是便于验证)。
分析结果:
这是一道的数据不算大,不用采用分而治之的步骤,所以采用hash_map + 堆排序。
(1)先使用fread()将整个数据文件全部读入内存,然后将字符串转化为每个整数id。
const int MAXN = 10000000;int numbers[MAXN];const int MAXS = 73*1024*1024; //根据数据文件的大小,72.7MBchar buf[MAXS];void analyse(char *buf, int len = MAXS){ int i; numbers[i = 0] = 0; for(char *p = buf;*p && p - buf < len; p++) { if(*p == '\r') //每行数据以“\r\n”结尾,所以用‘\r’做判断,跳过‘\n’ { numbers[++i] = 0; p++; } else numbers[i] = numbers[i] * 10 + *p - '0'; } }void fread_analyse(){ freopen("id.txt", "rb", stdin); int len = fread(buf, 1, MAXS, stdin); fclose(stdin); buf[len] = '\0'; analyse(buf, len);}
(2) 使用hash_map对每个id进行次数统计。维护一个key和value类型都为int的hash_map<int, int>,每次读取一个id,如果该id不在hash_map中,就添加该id,并将value值设为1;如果该id在hash_map中,就将该id对应的value值加1。
unordered_mapidhmap; //hash_map不在标准函数库中,但是C++11中有了unordered_map实现了hash_map的功能void hashmap_count(){ int id; for(int i = 0;i (id, 1)); }}
(3)使用STL中的优先级队列priority_queue建立最小堆对统计后的hash_map进行堆排序。存储前100个(提交要求111个,所以测试代码中取前111个id)id和对应的统计次数,然后遍历hash_map,每次遍历都将该元素的统计次数和堆顶元素的统计次数进行比较,统计次数多于堆顶元素则将t堆顶元素出队,将新的元素入队。
priority_queue, cmp> pqueue;void heap_sort(){ unordered_map ::iterator it = idhmap.begin(); for(int i = 0; i <111; i++) //将hash_map的前11个元素入队 pqueue.push(Id(it->first, it++->second)); for(; it != idhmap.end(); it++) { if(it->second > pqueue.top().count) { pqueue.pop(); pqueue.push(Id(it->first, it->second)); } }}
(4)最后格式化输出到文本文件。
void print(){ freopen("out.txt", "w", stdout); vectorvec; while(!pqueue.empty()) //为了将111个元素按照统计次数从高到低输出,翻转队列到vector中 { vec.push_back(pqueue.top()); pqueue.pop(); } for(int i = vec.size() - 1; i >= 0; i--) printf("%d\t\t%d\n", vec[i].id, vec[i].count); fclose(stdout); }
题目数据下载: