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

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

}  

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

 

http://www.bkjia.com/PHPjc/477840.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/477840.htmlTechArticle题目: 从N个数中选取最大的前10个, 有序输出. N最大可能达到1000亿 每个数范围是0 - 2147483647 author: goosman.lei mail: lgg860911@yahoo.com.cn blog: http:/...