学步园

题目：100亿个整数，求最大的1万个数，并说出算法的时间复杂度

算法：如果把100亿个数全部读入内存，需要100 0000 0000 * 4B 大约40G的内存，这显然是不现实的。

我们可以在内存中维护一个大小为10000的最小堆，每次从文件读一个数，与最小堆的堆顶元素比较，若比堆顶元素大，

则替换掉堆顶元素，然后调整堆。最后剩下的堆内元素即为最大的1万个数，算法复杂度为O(NlogN)

实现：从文件读数据有讲究，如果每次只读一个数，效率太低，可以维护一个输入缓冲区，一次读取一大块数据到内存，

用完了又从文件接着读，这样效率高很多，缓冲区的大小也有讲究，一般要设为4KB的整数倍，因为磁盘的块大小一般

就是4KB

C代码  

1. /* 编译 gcc main.c 
2.  * 产生测试数据: dd if=/dev/urandom of=random.dat bs=1M count=1024 
3.  * 运行: ./a.out random.dat 100 
4.  */  
5. #include <fcntl.h>  
6. #include <stdio.h>  
7. #include <stdlib.h>  
8. #include <string.h>  
9. #include <unistd.h>  
10. #include <sys/time.h>  
11.   
12. static unsigned int BUF_PAGES;      /* 缓冲区有多少个page */  
13. static unsigned int PAGE_SIZE;      /* page的大小 */  
14. static unsigned int BUF_SIZE;       /* 缓冲区的大小, BUF_SIZE = BUF_PAGES*PAGE_SIZE */  
15.   
16. static int *buffer;                 /* 输入缓冲区 */  
17. static int *heap;                   /* 最小堆 */  
18.   
19. long get_time_usecs();  
20. void init_heap(int n);  
21. void adjust(int n, int i);  
22.   
23. int main(int argc, char **argv)  
24. {  
25.     unsigned int        K, idx, length;  
26.     int                 fd, i, bytes, element;  
27.   
28.     long start_usecs = get_time_usecs();  
29.   
30.     fd = open(argv[1], O_RDONLY);  
31.     if (fd < 0) {  
32.         printf("can't open file %s\n",argv[1]);  
33.         exit(0);  
34.     }  
35.   
36.     PAGE_SIZE = 4096;                           /* page = 4KB */  
37.     BUF_PAGES = 512;  
38.     BUF_SIZE = PAGE_SIZE*BUF_PAGES;             /* 4KB*512 = 2M */  
39.     buffer = (int *)malloc(BUF_SIZE);  
40.     if (buffer == NULL) exit(0);  
41.   
42.     K = atoi(argv[2]);  
43.     heap = (int *)malloc(sizeof(int)*(K+1));  
44.     if (heap == NULL) {  
45.         free(buffer);  
46.         exit(0);  
47.     }  
48.   
49.     bytes = read(fd, heap+1, K*sizeof(int));  
50.     if (bytes < K*sizeof(int)) {  
51.         printf("data size is too small\n");  
52.         exit(0);  
53.     }  
54.     init_heap(K);  
55.   
56.     idx = length = 0;  
57.     for (;;) {  
58.         if (idx == length) {    /* 输入缓冲区用完 */  
59.             bytes = read(fd, buffer, BUF_SIZE);  
60.             if (bytes == 0) break;  
61.             length = bytes/4;  
62.             idx = 0;  
63.         }  
64.         //从buffer取出一个数，若比最小堆堆顶元素大，则替换之  
65.         element = buffer[idx++];  
66.         if (element > heap[1]) {  
67.             heap[1] = element;  
68.             adjust(K, 1);  
69.         }  
70.     }  
71.   
72.     long end_usecs = get_time_usecs();  
73.   
74.     printf("the top %d numbers are: \n", K);  
75.     for (i = 1; i <= K; i++) {  
76.         printf("%d ", heap[i]);  
77.         if (i % 6 == 0) {  
78.             printf("\n");  
79.         }  
80.     }  
81.     printf("\n");  
82.   
83.     free(buffer);  
84.     free(heap);  
85.     close(fd);  
86.   
87.     double secs = (double)(end_usecs - start_usecs) / (double)1000000;  
88.     printf("program tooks %.02f seconds.\n", secs);  
89.   
90.     return 0;  
91. }  
92.   
93. void init_heap(int n)   
94. {  
95.     int     i;  
96.   
97.     for (i = n/2; i > 0; i--) {  
98.         adjust(n, i);  
99.     }  
100. }  
101.   
102. /* 节点i的左子树和右子树已是最小堆, 此函数的 
103.  * 作用是把以节点i为根的树调整为最小堆 */  
104. void adjust(int n, int i)  
105. {  
106.     heap[0] = heap[i];  
107.     i <<= 1;  
108.     while (i <= n) {  
109.         if (i < n && heap[i+1] < heap[i]) {  
110.             i++;  
111.         }  
112.         if (heap[i] >= heap[0]) {  
113.             break;  
114.         }  
115.         heap[i>>1] = heap[i];  
116.         i <<= 1;  
117.     }  
118.     heap[i>>1] = heap[0];  
119. }  
120.   
121. long get_time_usecs()  
122. {  
123.     struct timeval time;  
124.     struct timezone tz;  
125.     memset(&tz, '\0', sizeof(struct timezone));  
126.     gettimeofday(&time, &tz);  
127.     long usecs = time.tv_sec*1000000 + time.tv_usec;  
128.   
129.     return usecs;  
130. }  

测试和运行： 见代码的注释，主要是如何产生测试数据，

linux提供了一个产生测试数据的命令，直接调用就行了

dd if=/dev/urandom of=random.dat bs=1M count=1024

这样产生的测试数据是二进制的，我们把美4个字节当成1个整数来用。

http://kenby.iteye.com/blog/1028465