題目: 從N個數中選取最大的前10個, 有序輸出. N最大可能達到1000億 每個數范圍是0 - 2147483647 C語言版測試結果: 輸入100萬條 總計[1000000]個輸入 總計比較[2001654]次 總計寫內存[552]次 總計耗時[0.014687s] C語言版本解決方案 [cpp] #include <stdio.h> #include <time.h> #include <stdlib.h> #include <unistd.h> #include <strings.h> /* * author: goosman.lei * mail: [email protected] * blog: http://blog.csdn.net/lgg201 */ #define BUFF_LEN (4096) /* #define DEBUG */ #define INFO 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"); } int main(int argc, char *argv[]) { int *sbuff; int i, j, n; queue_t *rbuff, **tmp, *t; #ifdef INFO int s_0, s_1, s_2; struct timeval begin, end; #endif 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); rbuff = malloc(sizeof(queue_t) * 10); /* 緩沖區初始化 */ bzero(rbuff, sizeof(queue_t) * 10); for ( i = 0; i < 9; i ++ ) { (rbuff + i)->next = (rbuff + i + 1); (rbuff + i)->data = -1; } (rbuff + 9)->data = -1; (rbuff + 9)->next = NULL; #ifdef DEBUG dump_link(rbuff, 1); #endif #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)) ) { #ifdef INFO s_0 ++; #endif j = n / 4; #ifdef INFO s_2 += j; #endif for ( i = 0; i < j; i ++ ) { #ifdef INFO s_0 ++; #endif #ifdef DEBUG fprintf(stderr, "processing %d\n", *(sbuff + i)); #endif for ( tmp = &rbuff; *tmp != NULL && *(sbuff + i) >= (*tmp)->data; ) { tmp = &((*tmp)->next); #ifdef INFO s_0 += 2; #endif } #ifdef INFO s_0 ++; #endif if ( *tmp == rbuff ) { continue; } #ifdef DEBUG fprintf(stderr, "tmp %d %p, rbuff %d %p\n", (*tmp) == NULL ? -1 : (*tmp)->data, *tmp, rbuff->data, rbuff); #endif rbuff->data = *(sbuff + i); #ifdef INFO s_1 ++; s_0 ++; #endif if ( *tmp != rbuff->next ) { t = rbuff; rbuff = rbuff->next; t->next = NULL == *tmp ? NULL : *tmp; *tmp = t; #ifdef INFO s_1 += 4; s_0 ++; #endif } #ifdef DEBUG dump_link(rbuff, 1); #endif } } #ifdef INFO gettimeofday(&end, NULL); #endif dump_link(rbuff, 0); #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; }
