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

题目:
从N个数中选取最大的前10个, 有序输出.
N最大可能达到1000亿
每个数范围是0 - 2147483647
 
author: goosman.lei
mail:
 
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); 
} 
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);