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

從N個數中選取最大的前10個[php版]

編輯:關於PHP編程

題目: 從N個數中選取最大的前10個, 有序輸出. N最大可能達到1000億 每個數范圍是0 - 2147483647   author: goosman.lei mail: [email protected] blog: http://blog.csdn.net/lgg201   php版測試結果: 輸入100萬條 總計[1000000]個輸入 總計比較[2001653]次 總計寫內存[552]次 總計耗時[1.742764s]   php版解決方案: [php]   <?php   define('DEBUG',                 FALSE);   define('INFO',                  TRUE);   $stderr = fopen('php://stderr', 'w+');   $stdout = fopen('php://stdout', 'w+');   $stdin  = fopen('php://stdin', 'r+');      class PQueue {       public  $data;       public  $next   = NULL;       public function __construct($data) {           $this->data  = $data;       }       public static function factory($data, $n) {           $i      = -1;           $head   = NULL;           $prev   = NULL;           while ( ++ $i < $n ) {               $node   = new PQueue($data);               if ( is_null($head) )                    $head       = $node;               if ( !is_null($prev) )                   $prev->next  = $node;               $prev   = $node;           }           return $head;       }       public static function dump($node, $n) {           global  $stderr, $stdout;           while ( !is_null($node) ) {               fprintf($n ? $stderr : $stdout, "%d\n", $node->data);               $node   = $node->next;           }           if ( $n ) fprintf($n ? $stderr : $stdout, "\n");       }   }      function generate_test_data($n) {       global  $stderr, $stdout;       srand(time());       for ( $i = 0; $i < $n; $i ++ ) {           $r  = rand(0, 2147483647);           fprintf($stdout, "%d\n", $r);           fprintf($stderr, "%s", pack('l', $r));       }   }      function main($argc, $argv) {       global  $stderr, $stdout, $stdin;       if ( $argc < 2 ) {           printf("usage: \n\t1. 生成測試數據: %s <number> /* 標准錯誤以二進制方式輸出測試數據, 標准輸出以文本方式輸出測試數據用於腳本校驗 */\n\t2. 執行Top 10查找: %s <exec> /* 標准輸出輸出前10個最大數據(倒序), 開啟INFO時在標准錯誤輸出統計信息, 開啟DEBUG時在標准錯誤輸出調試信息\n",                        $argv[0], $argv[0]);           exit(0);       }       if ( strcmp($argv[1], "exec") != 0 ) {           /* 不考慮數字輸入的容錯了 */           generate_test_data($argv[1]);           exit(0);       }          $sbuff  = NULL;       $rbuff  = PQueue::factory(-1, 10);      if ( DEBUG ) {       PQueue::dump($rbuff, 1);   }   if ( INFO ) {       $s_0    = 0;       $s_1    = 0;       $s_2    = 0;       $begin  = microtime(TRUE);   }       while ( FALSE != ($sbuff = fread($stdin, 1024 * 1024 * 4)) ) {           $sbuff  = unpack('l*', $sbuff);   if ( INFO ) {       $s_2    += count($sbuff);   }           foreach ( $sbuff as $d ) {   if ( INFO ) {       $s_0 ++;   }   if ( DEBUG )       fprintf($stderr, "processing %d\n", $d);               $tmp    = &$rbuff;               while ( $tmp != NULL && $d >= $tmp->data ) {                   $tmp    = &$tmp->next;   if ( INFO ) {       $s_0 += 2;   }               }   if ( INFO ) {       $s_0 ++;   }               if ( $tmp === $rbuff )                   continue;   if ( DEBUG )       fprintf($stderr, "tmp %d, rbuff %d\n", is_null($tmp) ? -1 : $tmp->data, $rbuff->data);   if ( INFO ) {       $s_0 ++;       $s_1 ++;   }               $rbuff->data = $d;               if ( $tmp != $rbuff->next ) {                   $t          = $rbuff;                   $rbuff      = $rbuff->next;                   $t->next = is_null($tmp) ? NULL : $tmp;                   $tmp        = $t;   if ( INFO ) {       $s_1 += 4;       $s_0 ++;   }               }           }   if ( DEBUG )        PQueue::dump($rbuff, 1);       }   if ( INFO ) {       $end    = microtime(TRUE);   }       PQueue::dump($rbuff, 0);   if ( INFO ) {       fprintf($stderr, "總計[%d]個輸入\n總計比較[%d]次\n總計寫內存[%d]次\n總計耗時[%0.6fs]\n",            $s_2, $s_0, $s_1, $end - $begin);   }   }   main($argc, $argv);    

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