300万输入信息中 最热门的前十条问题

搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算法（c语言），空间和时间复杂度

 

首先我们计算下看内存是不是够用,其实想都不用想如果够用的话,题中就不用说内存了^_^

 

 300*256w > 100000w

 

再说你的结构体,就算是链表也是

typedef struct  list

{

  char str[256];

  int frequency;

  struct  list* next;

}LIST;

当然也可以使用结构体数组...

typedef struct  array

{

  char str[256];

  int frequency;

}ARRAY;

 

1.假设内存够用,用数组吧

   ARRAY  array[300w];实际是<300w的有重复的....

  

  接下来的方法就是10亿个数中取大的10个数了,你可以二叉堆,也可以快排的思想.

 

2.这里内存不够用,就只有先把这些数丢在磁盘了。

  input.txt  //原始文件  输入信息(有重复)

  num.txt    //输入信息加次数(无重复)

 

  那么如何由input.txt到num.txt呢

 

  先从input.txt中读取记录,先hash_find如果没找到再hash_add

 

3.得到这个之后就是上面说的 二叉堆 or 快排只取一边的理论上的O(N)的做法了

当然这里内存也是不够快排思想的,我这里这是说说这种思路而已

 

 

最后

 1.先利用hash得到num.txt

//其实你真要算,这里还可以说是外排,不过外排太麻烦,也没什么效率,只是可行性

 2.再二叉堆

 

 第一次不上代码,直接这么分析,也不知道效果如何,每次都写代码太累了...就想还有人在我blog抱怨malloc的mem,  没有free!!!!

  oh my god!!!你爱看不看,分不清主次的人。多说不宜,显得我的愤青!!!什么时候网络的愚民们能不以批判的眼光看人,多些宽容,此真乃国家之幸也。