从N个数中选取最大的前10个[php版]_PHP教程-php教程-PHP中文网

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

WBOY

发布： 2016-07-14 10:07:34

原创

1096 人浏览过

题目:

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