欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  php教程

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

程序员文章站 2022-05-11 10:24:10
...
题目:

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

N最大可能达到1000亿

每个数范围是0 - 2147483647

author: goosman.lei

mail: lgg860911@yahoo.com.cn

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);