N 個の数値から上位 10 個の最大数値を選択する [php 版]_PHP チュートリアル

トピック：

N個の数値の中から最大上位10個を選択し、順番に出力します。

Nは最大1,000億に達する可能性があります

各数値の範囲は0〜2147483647です

作者: goosman.lei

メール: lgg860911@yahoo.com.cn

ブログ: http://blog.csdn.net/lgg201

phpバージョンのテスト結果:

100万アイテムを入力してください

合計 [1000000] 入力

合計比較 [2001653] 回

メモリへの書き込みは合計 [552] 回

合計所要時間 [1.742764秒]

phpバージョンの解決策:

[php]

define('DEBUG', FALSE);

define('INFO', TRUE);

$stderr = fopen('php://stderr', 'w+');

$stdout = fopen('php://stdout', 'w+');

$stdin = fopen('php://stdin', 'r+');

クラス PQueue {

公開 $data

パブリック $next = NULL

;

パブリック関数 __construct($data) {

$this->data = $data;

}

パブリック静的関数ファクトリー($data, $n) {

$i = -1;

$head = NULL;

$prev = NULL

while ( ++ $i < $n ) {

$ ノード = 新しい pqueue ($ データ);

if ( is_null($head) )

$ head

if ( !is_null($prev) )

$prev->next = $node;

$prev = $node;

}

$head;

}

パブリック静的関数 dump($node, $n) {

グローバル $stderr、$stdout

while ( !is_null($node) ) {

fprintf($n ? $stderr : $stdout, "%dn", $node->data);

$node = $node->next;

}

if ( $n ) fprintf($n ? $stderr : $stdout, "n");

}

}

関数generate_test_data($n) {

グローバル $stderr、$stdout

スランド(時間());

for ( $i = 0; $i $r = ランド(0, 2147483647);

fprintf($stdout, "%dn", $r);

fprintf($stderr, "%s", Pack('l', $r));

}

}

関数 main($argc, $argv) {

グローバル $stderr、$stdout、$stdin;

if ( $argc

テストデータを生成します: %s /* 標準エラーはテストデータをバイナリ形式で出力し、標準出力はテストデータをテキスト形式で出力します。スクリプトの検証 */nt2。トップ 10 検索を実行します: %s < ;exec> /* 最初の 10 個の最大データを標準出力に出力します (逆順)。 INFO がオンの場合、統計情報が標準エラーに出力されます。 DEBUG がオンの場合、デバッグ情報が標準エラーに出力されます。

$argv[0], $argv[0]);

終了(0)

}

if ( strcmp($argv[1], "exec") != 0 ) {

/* デジタル入力の許容誤差は考慮しません */

Generate_test_data($argv[1]);

終了(0)

}

$sbuff = NULL

$rbuff = PQueue::factory(-1, 10);  

if (デバッグ) {

PQueue::dump($rbuff, 1);  

}

if (情報) {

$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 (情報) {

$s_2 += count($sbuff);  

}

foreach ( $sbuff as $d ) {

if (情報) {

$s_0 ++;  

}

if (デバッグ)

fprintf($stderr, "%dn を処理中", $d);  

$tmp = &$rbuff;  

while ( $tmp != NULL && $d >= $tmp->data ) {

$tmp = &$tmp->next;  

if (情報) {

$s_0 += 2;  

}

}

if (情報) {

$s_0 ++;  

}

if ( $tmp === $rbuff )

続けます。  

if (デバッグ)

fprintf($stderr, "tmp %d, rbuff %dn", is_null($tmp) ? -1 : $tmp->data, $rbuff->data);  

if (情報) {

$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 (情報) {

$s_1 += 4;  

$s_0 ++;  

}

}

}

if (デバッグ)

PQueue::dump($rbuff, 1);  

}

if (情報) {

$end = microtime(TRUE);  

}

PQueue::dump($rbuff, 0);  

if (情報) {

fprintf($stderr, "总计[%d]个输入n总计比较[%d]次n总计写内存[%d]次n总计消費時間[%0.6fs]n",

$s_2、$s_0、$s_1、$end - $begin);  

}

}

main($argc, $argv);  

http://www.bkjia.com/PHPjc/477840.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/477840.html技術記事题目: 从N個中選択最大の上位10個、有順出力。 N最大可能性は1000亿每数范围是0 - 2147483647 著者: goosman.lei メール: lgg860911@yahoo.com.cn ブログ: http://...

このウェブサイトの声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。