Select the top 10 largest numbers from N numbers [php version]

Select the top 10 largest numbers from N numbers [php version]_PHP tutorial

WBOY

Release： 2016-07-14 10:07:34

Original

1096 people have browsed it

Topic:

Select the top 10 largest numbers from N numbers and output them in order.

N may reach a maximum of 100 billion

The range of each number is 0 - 2147483647

author: goosman.lei

mail: lgg860911@yahoo.com.cn

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

php version test results:

Enter 1 million

Total [1000000] inputs

Total comparisons [2001653] times

Write memory [552] times in total

Total time taken [1.742764s]

php version solution:

[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, "%dn", $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, "%dn", $r);

fprintf($stderr, "%s", pack('l', $r));

}

function main($argc, $argv) {

global $stderr, $stdout, $stdin;

if ( $argc < 2 ) {

printf("usage: nt1. Generate test data: %s /* Standard error outputs test data in binary format, and standard output outputs test data in text format for script verification*/nt2. Execute Top 10 search: %s /* Output the first 10 largest data on standard output (reverse order), output statistical information on standard error when INFO is turned on, and output debugging information on standard error when DEBUG is turned on",

$argv[0], $argv[0]);

exit(0);

}

if ( strcmp($argv[1], "exec") != 0 ) {

/* Does not consider the error tolerance of digital input */

generate_test_data($argv[1]);

exit(0);

}

$sbuff = NULL;

$rbuff = PQueue::factory(-1, 10);

if ( DEBUG ) {

PQueue::dump($rbuff, 1);