程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 從N個數中選取最大的前10個[C語言版]

從N個數中選取最大的前10個[C語言版]

編輯:關於C語言

題目: 從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;   }    

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved