从N个数中选取最大的前10个[php版]_PHP教程
程序员文章站
2022-06-08 08:27:51
...
题目:
![从N个数中选取最大的前10个[php版]_PHP教程](/default/index/img?u=L3N0YXRpYy9pbWFnZXMvdXNlcl9hdmF0YXIuanBn "从N个数中选取最大的前10个[php版]_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
![从N个数中选取最大的前10个[php版]_PHP教程](/default/index/img?u=aHR0cHM6Ly9pbWcucGhwLmNuL3VwbG9hZC9jb3Vyc2UvMDAwLzAwMC8wNzEvNjIwYzYwNGY3NTI1MTk5NS5wbmc= "从N个数中选取最大的前10个[php版]_PHP教程")
$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);
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
相关文章
相关视频
专题推荐
-
独孤九贱-php全栈开发教程
全栈 170W+
主讲：Peter-Zhu 轻松幽默、简短易学，非常适合PHP学习入门
-
玉女心经-web前端开发教程
入门 80W+
主讲：灭绝师太 由浅入深、明快简洁，非常适合前端学习入门
-
天龙八部-实战开发教程
实战 120W+
主讲：西门大官人 思路清晰、严谨规范，适合有一定web编程基础学习
作者信息
- 最新文章
- 热门排行
上一篇： ，困扰了小弟我很长时间的分页有关问题
下一篇： 一道面试题，求思路，求代码。高分解决方法
网友评论
文明上网理性发言，请遵守 新闻评论服务协议
我要评论