大数据处理 10M单词取最热前10

http://blog.csdn.net/zzran/article/details/8439367

2012

这个算法很霸气啊，用了100k的单词，居然在15ms就解决了。

考虑了一下，还是决定把思路写出来吧，题目要求，给定一定量大的单词，比如说1000万个，然后找出最热门的前10，也就是出现频数排名前十的单词。思路如下：

先统计出每个单词出现的次数，应用hash统计，这个方法很快。然后建立一个大小为10的小根堆，之后依次从文件中取出单词，并用单词的出现的次数和小根堆的堆顶元素的出现此处进行比较，如果大于堆顶元素出现的次数，则替换，然后调整小根堆。

[cpp] view plain copy

1. #include<iostream>  
2. #include<string>  
3. using namespace std;  
4. #define HASHLEN 2807303    
5. #define WORDLEN 30   
6.   
7. typedef struct node_has_space{  
8.     char word[WORDLEN];  
9.     int count;  
10.     struct node_has_space *next;  
11. }node_has_space, *p_node_has_space;  
12.   
13. typedef struct node_no_space{  
14.     char *word;  
15.     int count;  
16.     struct node_no_space *next;  
17. }node_no_space, *p_node_no_space;  
18.   
19. p_node_no_space bin[HASHLEN] = {NULL};  
20.   
21. void swap(int &a, int &b) {  
22.     int temp;  
23.     temp = a;  
24.     a = b;  
25.     b = temp;  
26. }  
27. unsigned int hash(char *p_word) {  
28.     unsigned int index = 0;  
29.     while(*p_word) {  
30.         index += index * 31 + *p_word;  
31.         p_word++;  
32.     }  
33.     return index % HASHLEN;  
34. }  
35.   
36. void trim_word(char *word) {  
37.     int n = strlen(word) - 1;  
38.     if(n <= 0)  
39.         return;  
40.     int i = 0;  
41.     while(word[n] < '0' || (word[n] > '9' && word[n] < 'A') || (word[n] > 'Z' && word[n] < 'a') || word[n] > 'z') {  
42.         word[n] = '\0';  
43.         --n;  
44.     }  
45.   
46.     while(word[i] < '0' || (word[i] > '9' && word[i] < 'A') || (word[i] > 'Z' && word[i] < 'a') || word[i] > 'z') {  
47.         ++i;  
48.     }  
49.     strcpy(word, word + i);  
50. }  
51.   
52. void insert_word(char *word) {  
53.     unsigned int index = hash(word);  
54.     node_no_space *p = bin[index];  
55.     while(p) {  
56.         if(strcmp(p->word, word) == 0) {  
57.             (p->count)++;  
58.             return;  
59.         }  
60.         p = p->next;  
61.     }  
62.   
63.     p = (node_no_space*)malloc(sizeof(node_no_space));  
64.     p->count = 1;  
65.     p->word = (char*)malloc(strlen(word) + 1);  
66.     strcpy(p->word, word);  
67.     p->next = bin[index];  
68.     bin[index] = p;  
69. }  
70.   
71. void write_to_file(char *file_path) {  
72.     FILE* fout = fopen(file_path, "w");  
73.     int i = 0;  
74.     node_no_space *p;  
75.     while(i < HASHLEN) {  
76.         for(p = bin[i]; p != NULL; p = p->next) {  
77.             fprintf(fout, "%s %d\n", p->word, p->count);  
78.         }  
79.         i++;  
80.     }  
81.     fclose(fout);  
82. }  
83.   
84. void min_heap(node_has_space heap[], int i, int len) {  
85.     int left = i * 2;  
86.     int right = i * 2 + 1;  
87.     int min_index;  
88.   
89.     if(left <= len && heap[left].count < heap[i].count) {  
90.         min_index = left;  
91.     } else {  
92.         min_index = i;  
93.     }  
94.   
95.     if(right <= len && heap[right].count < heap[min_index].count) {  
96.         min_index = right;  
97.     }  
98.     if(min_index != i) {  
99.         swap(heap[i].count, heap[min_index].count);  
100.         char buffer[WORDLEN];  
101.         strcpy(buffer, heap[min_index].word);  
102.         strcpy(heap[min_index].word, heap[i].word);  
103.         strcpy(heap[i].word, buffer);  
104.         min_heap(heap, min_index, len);  
105.     }  
106. }  
107.   
108. void build_min_heap(node_has_space heap[], int n) {  
109.     int index = n / 2;  
110.     int i;  
111.     for(i = index; i >= 1; i--) {  
112.         min_heap(heap, i, n);  
113.     }  
114. }  
115.   
116. void main() {  
117.     int i;  
118.     int _count;  
119.     int n = 10;  
120.     FILE *f_message, *fin;  
121.     char *_word = (char*)malloc(WORDLEN);  
122.     f_message = fopen("string.txt", "r");  
123.     if(!f_message)  
124.         return;  
125.     while(fscanf(f_message, "%s", _word) != EOF) {  
126.         if(strlen(_word)) {  
127.             trim_word(_word);  
128.             insert_word(_word);  
129.         }  
130.     }  
131.     fclose(f_message);  
132.   
133.     write_to_file("result.txt");  
134.   
135.     fin = fopen("result.txt", "r");  
136.     node_has_space *heap = (node_has_space*) malloc(sizeof(node_has_space) * (n + 1));  
137.     for(i = 1; i <= n; i++) {  
138.         fscanf(fin, "%s %d", _word, &_count);  
139.         heap[i].count = _count;  
140.         strcpy(heap[i].word, _word);  
141.     }  
142.     build_min_heap(heap, n);  
143.     while(fscanf(fin,"%s %d", _word, &_count) != EOF) {  
144.         if(_count > heap[1].count) {  
145.             heap[1].count = _count;  
146.             strcpy(heap[1].word, _word);  
147.             min_heap(heap, 1, n);  
148.         }  
149.     }  
150.   
151.     for(int k = 1; k <= n; k++) {  
152.         cout << heap[k].word << ":" << heap[k].count << endl;  
153.     }  
154. }