php从N个数中找出最大的10个数代码
题目:
从N个数中选取最大的前10个, 有序输出.
N最大可能达到1000亿
每个数范围是0 – 2147483647
author: goosman.lei
mail: lgg860911@yahoo.com.cn
blog: php” target=”_blank”>http://blog.csdn.net/lgg201
php版测试结果:
输入100万条
总计[1000000]个输入
总计比较[2001653]次
总计写内存[552]次
总计耗时[1.742764s]
来源:http://blog.csdn.net/lgg201/article/details/8449322
<?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);