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

发布时间：2015-05-27 19:30:33作者：知识屋

题目:

从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]

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