搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
先统计所有查询的次数，所有查询有 300 万个，255 * 300 * 10000B = 765 MB，可以存入内存。这里使用 STL 中的 map。所得时间复杂度为 O(NlogM)，N 为所有的查询，包括重复的，M 为不重复的查询。更好的方法是用散列。
然后遍历 map，维护一个大小为 10 的集合，在遍历 map 时，比较当前查询的出现次数与集合中出现次数最小的查询的出现此时比较，如果大于，将当前查询替换到集合中。
这里的集合还是用的 map，时间复杂度为 O（MlogK），这里 K = 10。
总的时间复杂度为 O(NlogM) + O(MlogK)
也可以将这个过程合二为一。即每次在统计的过程中，查询大小为 K 的集合。如果符合条件，则将当前查询替换到集合中。但是还要考虑实时更新集合中的元素。
这种方法的时间复杂度为 O(N(logM + logK + K))。
由于第二种方法还得考虑实时更新。效率远没有第一种方案高。
实现：
1 #include <iostream>
2 #include <fstream>
3 #include <map>
4 #include <string>
5 using namespace std;
6
7 void statistics(map<string, int>& data, const string& query)
8 {
9 ++data[query];
10 }
11
12 void findTopK(multimap<int, string>& topK, int k, const map<string, int>& data)
13 {
14 topK.clear();
15 for (map<string, int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
16 {
17 if (topK.size() < k)
18 {
19 topK.insert(make_pair(cit->second, cit->first));
20 }
21 else
22 {
23 if (cit->second > topK.begin()->first)
24 {
25 topK.erase(topK.begin());
26 topK.insert(make_pair(cit->second, cit->first));
27 }
28 }
29 }
30 }
31
32 int main()
33 {
34 ifstream fin("queryfile.txt");
35 map<string, int> data;
36 multimap<int, string> top10;
37 string query;
38 while (getline(fin, query))
39 {
40 statistics(data, query);
41 }
42
43 //for (map<string, int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
44 //{
45 // cout << cit->first << '\t' << cit->second << endl;
46 //}
47
48 //cout << endl;
49 findTopK(top10, 10, data);
50
51 for (multimap<int, string>::const_reverse_iterator cit = top10.rbegin(); cit != top10.rend(); ++cit)
52 {
53 cout << cit->second << '\t' << cit->first << endl;
54 }
55
56 return 0;
57 }
http://blog.donews.com/jiji262/2011/03/baidu_top_k_interview/http://blog.redfox66.com/post/2010/09/23/top-k-algoriyhm-analysis.aspxhttp://blog.csdn.net/jasonblog/archive/2010/08/19/5825026.aspx
posted on 2011-04-30 18:06
unixfy 阅读(191)
评论(0) 编辑 收藏 引用