題目:
從N個數中選取最大的前10個, 有序輸出.
N最大可能達到1000億
每個數范圍是0 - 2147483647
堆排序版測試結果:
總計[1000000]個輸入
總計比較[4232804]次
總計寫內存[3849024]次
總計耗時[0.046478s]
/*
* author: goosman.lei
* mail:
[email protected]
* blog: http://blog.csdn.net/lgg201
*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>
#define BUFF_LEN (4096)
#define PARENT(i) ((i) / 2 - 1)
#define LEFT(i) ((i + 1) * 2 - 1)
#define RIGHT(i) ((i + 1) * 2)
/* #define DEBUG */
#define INFO
#ifdef INFO
int s_0, s_1, s_2;
struct timeval begin, end;
#endif
typedef struct queue_s queue_t;
struct queue_s {
int data;
queue_t *next;
};
static void generate_test_data(long n) {
long i;
int r;
int l;
l = sizeof(int);
srand(time(NULL));
for ( i = 0; i < n; i ++ ) {
r = rand();
fprintf(stdout, "%d\n", r);
write(STDERR_FILENO, &r, l);
}
}
static int read_input(int fd, void *buff, int buff_len) {
int i, ret;
for ( i = 0; i < buff_len; ) {
ret = read(fd, buff, BUFF_LEN);
if ( -1 == ret ) {
perror("read error\n");
exit(0);
} else if ( 0 == ret ) {
break;
} else {
buff += ret;
i += ret;
}
}
return i;
}
static void dump_link(queue_t *q, int n) {
for ( ; q != NULL; q = q->next )
fprintf(n ? stderr : stdout, "%d\n", q->data);
if ( n ) printf("\n");
}
void max_heapify(int *sbuff, int j) {
int i;
#ifdef INFO
s_0 += 3;
s_1 ++;
#endif
if ( sbuff[j] < sbuff[LEFT(j)] )
i = LEFT(j);
else
i = j;
if ( sbuff[i] < sbuff[RIGHT(j)] ) {
i = RIGHT(j);
#ifdef INFO
s_1 ++;
#endif
}
if ( i != j ) {
sbuff[i] ^= sbuff[j];
sbuff[j] ^= sbuff[i];
sbuff[i] ^= sbuff[j];
max_heapify(sbuff, i);
#ifdef INFO
s_1 += 3;
#endif
}
}
int main(int argc, char *argv[]) {
int *sbuff, *rbuff, *rbuff_t;
int i, j, n, rbuff_n;
if ( argc < 2 ) {
printf("usage: \n\t1. 生成測試數據: %s <number> /* 標准錯誤以二進制方式輸出測試數據, 標准輸出以文本方式輸出測試數據用於腳本校驗 */\n\t2. 執行Top 10查找: %s <exec> /* 標准輸出輸出前10個最大數據(倒序), 開啟INFO時在標准錯誤輸出統計信息, 開啟DEBUG時在標准錯誤輸出調試信息\n",
argv[0], argv[0]);
return (0);
}
if ( strcmp(argv[1], "exec") != 0 ) {
/* 不考慮數字輸入的容錯了 */
generate_test_data(atoi(argv[1]));
return 0;
}
sbuff = malloc(1024 * 1024 * 4 - 4);
rbuff = malloc(256 * 1024 * 10 * 4); /* 足夠10000億數據 */
rbuff_t = rbuff;
rbuff_n = 0;
#ifdef INFO
s_0 = 0;
s_1 = 0;
s_2 = 0;
gettimeofday(&begin, NULL);
#endif
while ( 0 != (n = read_input(STDIN_FILENO, sbuff, 1024 * 1024 * 4 - 4)) ) {
#ifdef INFO
s_2 += n / 4;
#endif
for ( j = (n / 4) / 2; j >= 0; j -- ) {
#ifdef INFO
s_0 ++;
#endif
max_heapify(sbuff, j);
}
for ( i = 0; i < 10; i ++ ) {
#ifdef INFO
s_0 ++;
s_1 += 4;
#endif
rbuff[rbuff_n] = sbuff[0];
sbuff[0] = sbuff[(n / 4) - 1 - i];
sbuff[(n / 4) - 1 - i] = -1;
max_heapify(sbuff, 0);
rbuff_n ++;
}
}
for ( j = rbuff_n / 2; j >= 0; j -- ) {
#ifdef INFO
s_0 ++;
#endif
max_heapify(rbuff, j);
}
for ( i = 0; i < 10; i ++ ) {
#ifdef INFO
s_0 ++;
s_1 += 4;
#endif
printf("%d\n", rbuff[0]);
rbuff[0] = rbuff[rbuff_n - i];
rbuff[rbuff_n - i] = -1;
max_heapify(rbuff, 0);
}
#ifdef INFO
gettimeofday(&end, NULL);
#endif
#ifdef INFO
fprintf(stderr, "總計[%d]個輸入\n總計比較[%d]次\n總計寫內存[%d]次\n總計耗時[%0.6fs]\n",
s_2, s_0, s_1, (end.tv_sec * 1000000 + end.tv_usec - begin.tv_sec * 1000000 - begin.tv_usec) / 1000000.0);
#endif
return 0;
}
