排序 php从N个数中找出最大的10个数代码

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