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