搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。
假設(shè)目前有一千萬(wàn)個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢串的重復(fù)度越高，說(shuō)明查詢它的用戶越多，也就是越熱門。請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過(guò)1G。
先統(tǒng)計(jì)所有查詢的次數(shù)，所有查詢有 300 萬(wàn)個(gè)，255 * 300 * 10000B = 765 MB，可以存入內(nèi)存。這里使用 STL 中的 map。所得時(shí)間復(fù)雜度為 O(NlogM)，N 為所有的查詢，包括重復(fù)的，M 為不重復(fù)的查詢。更好的方法是用散列。
然后遍歷 map，維護(hù)一個(gè)大小為 10 的集合，在遍歷 map 時(shí)，比較當(dāng)前查詢的出現(xiàn)次數(shù)與集合中出現(xiàn)次數(shù)最小的查詢的出現(xiàn)此時(shí)比較，如果大于，將當(dāng)前查詢替換到集合中。
這里的集合還是用的 map，時(shí)間復(fù)雜度為 O（MlogK），這里 K = 10。
總的時(shí)間復(fù)雜度為 O(NlogM) + O(MlogK)
也可以將這個(gè)過(guò)程合二為一。即每次在統(tǒng)計(jì)的過(guò)程中，查詢大小為 K 的集合。如果符合條件，則將當(dāng)前查詢替換到集合中。但是還要考慮實(shí)時(shí)更新集合中的元素。
這種方法的時(shí)間復(fù)雜度為 O(N(logM + logK + K))。
由于第二種方法還得考慮實(shí)時(shí)更新。效率遠(yuǎn)沒有第一種方案高。
實(shí)現(xiàn)：
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 閱讀(196)
評(píng)論(0) 編輯 收藏 引用