《程序员》第9期编程擂台，请高手指点如何写一个跑得快的。

2eye

昨晚看到这个题目，用C++写了一个，结果比人家java写的跑得还慢！请教高手如何很好的完成这个任务：

面对浩瀚的信息海洋，找到想要的资源有时真的是不容易。在大量文字中搜索高频词汇是信息搜索和数据压缩的共通课题。
　　这次智慧擂台请大家在一个比较庞大的英文文本中找出M个数量最多的短语（由N个单词组成）。统一处理相同的文本文件，该文本只包含英文单词、空格和回行符，比较谁的程序效率最高，这个文本近日发布。

　　程序输入：M，N，文本文件路径（M不超过20，N不超过8）
　　程序输出：高频短语及其数量清单
　　
　　擂台规则：提交符合以上要求的可执行程序，语言招式不限，点到为止；
　　　　　　　我们将在统一的环境下对每位选手的作品进行公平的测试，
　　　　　　　比较出综合用时最少的程序。

文本文件链接：
http://www.codechina.net/down//2 ... amp;spaces-5666.rar

[ 本帖最后由 2eye 于 2006-8-21 20:46 编辑 ]

yuxh

原帖由 2eye 于 2006-8-21 13:10 发表
昨晚看到这个题目，用C++写了一个，结果比人家java写的跑得还慢！请教高手如何很好的完成这个任务：

感觉关键就是hash函数

1. #include <cstddef>
   
2. #include <iostream>
   
3. #include <fstream>
   
4. #include <list>
   
5. #include <iterator>
   
6. #include <map>
   
7. 
   
8. using namespace std;
   
9. 
   
10. struct WordNode
    
11. {
    
12.     string word;
    
13.     WordNode *pre_word, *pre_match, *pre_node, *next_node;
    
14.     bool first_match;
    
15. 
    
16.     WordNode() : pre_word(NULL), pre_match(NULL), pre_node(NULL), next_node(NULL), first_match(true) { }
    
17.     ~WordNode() { }
    
18. };
    
19. 
    
20. bool MatchWord(const WordNode *first, const WordNode *second, int M)
    
21. {
    
22.     const WordNode *ptr = second;
    
23.     for(int i=0; i<M; i++) {
    
24.         if(first->word != second->word || first == ptr) return false;
    
25.         first = first->next_node;
    
26.         second = second->next_node;
    
27.     }
    
28.     return true;
    
29. }
    
30. 
    
31. int hashfunc(WordNode *node, int M)
    
32. {
    
33.     unsigned short v = 0;
    
34.     for(int i=0; i<M && node != NULL; i++) {
    
35.         for(int j=0; j<node->word.size(); j++)
    
36.             v = 5*v + node->word[j];
    
37.         node = node->next_node;
    
38.     }
    
39.     return int(v);
    
40. }
    
41. 
    
42. int main()
    
43. {
    
44.     ifstream inf("words.txt");
    
45.     if (!inf) {
    
46.         cerr << "Error open file words.txt" << endl;
    
47.         exit(-1);
    
48.     }
    
49. 
    
50.     WordNode *head, *node, *tail = NULL, *ptr, *match;
    
51.     int M, N, i=0, cnt;
    
52. 
    
53.     cin >> M >> N;
    
54.     WordNode **preM = new WordNode*[M];
    
55.     int index=0;
    
56.     memset(preM,  0, sizeof(WordNode*) * M);
    
57.     node = new WordNode;
    
58.     head = node;
    
59.     map<int, WordNode *> wordMap;
    
60.     map<int, WordNode *>::iterator map_itr;
    
61.     int hashval;
    
62.     while(inf >> node->word) {
    
63.         preM[index] = node;
    
64.         index = (index+1)%M;
    
65.         ptr = preM[index];
    
66.         hashval = hashfunc(ptr, M);
    
67.         if(hashval > 0) {
    
68.             if((map_itr = wordMap.find(hashval)) == wordMap.end()) {
    
69.                 wordMap[hashval] = node;
    
70.             }
    
71.             else {
    
72.                 node->pre_word = map_itr->second;
    
73.                 map_itr->second = node;
    
74.             }
    
75.         }
    
76.         if(ptr != NULL) {
    
77.             for(match=ptr->pre_word; match != NULL; match = match->pre_word) {
    
78.                 if(MatchWord(match, ptr, M)) {
    
79.                     ptr->pre_match = match;
    
80.                     match->first_match = false;
    
81.                     break;
    
82.                 }
    
83.             }
    
84.         }
    
85. 
    
86.         tail = node;
    
87.         node = new WordNode;
    
88.         tail->next_node = node;
    
89.         node->pre_node = tail;
    
90.     }
    
91.     list<pair<WordNode *, int> > toplist;
    
92.     list<pair<WordNode *, int> >::iterator itr;
    
93.     for(; ptr != NULL; ptr=ptr->pre_node) {
    
94.         if(ptr->first_match) {
    
95.             cnt = 1;
    
96.             for(match = ptr->pre_match; match != NULL; match = match->pre_match) cnt++;
    
97.             for(itr=toplist.begin(); itr!=toplist.end() && itr->second > cnt; ++itr);
    
98.             if(itr!=toplist.end()) {
    
99.                 toplist.insert(itr, make_pair(ptr, cnt));
    
100.                 if(toplist.size() > N)
     
101.                     toplist.pop_back();
     
102.             }
     
103.             else if(toplist.size() < N)
     
104.                 toplist.push_back(make_pair(ptr, cnt));
     
105.         }
     
106.     }
     
107.     for(itr=toplist.begin(), i=1; itr!=toplist.end(); ++itr, i++) {
     
108.         cout << "No." << i << ":";
     
109.         ptr = itr->first;
     
110.         for(int j=0; j<M; j++, ptr=ptr->next_node) {
     
111.             cout << ptr->word << " ";
     
112.         }
     
113.         cout << endl << "Count:" << itr->second << endl;
     
114.     }
     
115.     while(head != NULL) {
     
116.         ptr = head->next_node;
     
117.         delete head;
     
118.         head = ptr;
     
119.     }
     
120. }
     
121. 
     

复制代码

醉卧水云间

No.1:Following are
Count:711
No.2:are the
Count:619
No.3ec Xinhua
Count:514
No.4:BEIJING Dec
Count:486
No.5:Jan Xinhua
Count:394
No.6:BEIJING Jan
Count:382
No.7:US dollars
Count:355
No.8:US dollars
Count:350
No.9:United States
Count:350
No.10:matter II
Count:346


7，8是重复的，速度也不太快，不过我写不出更好的。