• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

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

PHP 水墨上仙 1801次浏览 0个评论

php从N个数中找出最大的10个数代码
题目:
从N个数中选取最大的前10个, 有序输出.
N最大可能达到1000亿
每个数范围是0 – 2147483647
author: goosman.lei
mail: lgg860911@yahoo.com.cn
blog: php” target=”_blank”>http://blog.csdn.net/lgg201
php版测试结果:
输入100万条
总计[1000000]个输入
总计比较[2001653]次
总计写内存[552]次
总计耗时[1.742764s]
来源:
http://blog.csdn.net/lgg201/article/details/8449322

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


喜欢 (0)

您必须 登录 才能发表评论!

加载中……