从N个数中选取最大的前10个[php版]

题目:

从N个数中选取最大的前10个, 有序输出.

N最大可能达到1000亿

每个数范围是0 - 2147483647

author: goosman.lei

mail: [e-mail]

blog: http://blog.csdn.net/lgg201

php版测试结果:

输入100万条

总计[1000000]个输入

总计比较[2001653]次

总计写内存[552]次

总计耗时[1.742764s]

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

$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

$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

printf("usage: \n\t1. 生成测试数据: %s /* 标准错误以二进制方式输出测试数据, 标准输出以文本方式输出测试数据用于脚本校验 */\n\t2. 执行Top 10查找: %s /* 标准输出输出前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);