文章点击量排行TOP100

lonhy

　　这道题来源于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.7MB
　　
char 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 = numbers * 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，每次读取一个id，如果该id不在hash_map中，就添加该id，并将value值设为1；如果该id在hash_map中，就将该id对应的value值加1。
　　

unordered_map>
void hashmap_count()　　
{

　　int>
　　for(int i = 0;i 　　idhmap[id]++;
　　else
　　idhmap.insert(pair(id, 1));
　　}
　　
}
　　

　　（3）使用STL中的优先级队列priority_queue建立最小堆对统计后的hash_map进行堆排序。存储前100个（提交要求111个，所以测试代码中取前111个id）id和对应的统计次数，然后遍历hash_map，每次遍历都将该元素的统计次数和堆顶元素的统计次数进行比较，统计次数多于堆顶元素则将t堆顶元素出队，将新的元素入队。
　　

priority_queue pqueue;　　
void heap_sort()
　　
{

　　unordered_map::iterator it =>　　for(int i = 0; i first, it++->second));
　　


　　for(; it !=>　　{
　　if(it->second > pqueue.top().count)
　　{
　　pqueue.pop();
　　pqueue.push(Id(it->first, it->second));
　　}
　　}
　　
}
　　

　　（4）最后格式化输出到文本文件。
　　

void print()　　
{
　　freopen("out.txt", "w", stdout);
　　vector vec;
　　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.id, vec.count);
　　fclose(stdout);
　　}
　　

　　题目数据下载：http://pan.baidu.com/s/1gd08g3D