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

题目:

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

}  

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