忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/07/21 17:55 |
PHP5.5.3 エラトステネスの篩で素数を求める
素数出力プログラミング大会
http://person-link.co.jp/blog/detail/32

1時間でやるならまだしも、一週間も期間があるのに誰もエラトステネスの篩書いてないとかどういうことだよ。
<?php
	// ArrayIteratorを使ったエラトステネスの篩

	// 初期値
	$max = 1000000;
	$arr = new ArrayIterator(array_flip(range(3, $max, 2)));
	$loopmax = ceil(sqrt($max));

	// 篩
	foreach($arr as $key=>$val){
		if($key > $loopmax ){ break; }
		if(!isset($arr[$key])){ continue; }
		$loop=2;
		$now = $key*2;
		while($now <= $max){
			if(isset($arr[$now])){unset($arr[$now]);}
			$loop++;
			$now = $key*$loop;
		}
	}

	// 出力
	echo 2, PHP_EOL, implode(PHP_EOL, array_keys($arr->getArrayCopy())) , PHP_EOL;
<?php
	// 文字列を使ったエラトステネスの篩
	
	// 初期値
	$max = 1000000;
	$str = str_repeat('01', $max/2+1);
	$loopmax = ceil(sqrt($max));

	// 篩
	for($key=3; $key<=$loopmax; $key+=2){
		if($str[$key] === '0'){continue;}
		$loop=2;
		$now = $key*2;
		while($now <= $max){
			$str[$now] = '0';
			$loop++;
			$now = $key*$loop;
		}
	}

	// 出力
	$sosuu = '2'.PHP_EOL;
	for($key=3; $key<=$max; $key+=2){
		if($str[$key]==='1'){
			$sosuu .= $key.PHP_EOL;
		}
	}
	echo $sosuu;
10000まで、および1000000までの素数を求めるのにかかった時間とメモリ使用量です。
計測方法は2回計った平均値というかなり意味のない値なので、オーダー程度に見てください。

ファイル名10000件時間(秒)1000件メモリ(kb)1000000件時間(秒)1000000件メモリ(kb)
katsurayama_sosu.php 0.00400043 134.38 1.78117800 1362.41
maeda_sosu.php 0.30502999 991.88 Maximum execution time of 180 seconds exceeded
sosu_sample.php 2.81178141 992.17 Maximum execution time of 180 seconds exceeded
tanaka_sosu.php 0.00449991 248.15 0.99830055 8166.82
NurseAngel ArrayIterator 0.00450063 993.30 0.48954952 84322.09
NurseAngel str_repeat 0.00250053 145.05 0.19101894 2363.26

2番目と3番目ひどいな。
10000件の時点で既に他と100倍~1000倍の差があります。
毎回echoしているせいかと最後にまとめて出力してみたのですが変わりませんでした。
何故ここまで違うんだろう。

篩のほうは値が大きくなるほど処理対象が少なくなるため、10000件程度ではtanaka_sosu.phpとあまりかわりませんが、1000000件まで行くと相対的に処理時間が減っていきます。

はじめ何も考えずにArrayIteratorで書いたのですが、最初に50万件のArrayIteratorをががっと作ってしまうので、使用メモリがえらいことになってます。
1000万件を処理しようとしたら死にます。
あまりに残念だったので書き直してみたのがstr_repeat()を使う方。
メモリ使用量が激減したのは想定通りですが、実行時間まで半分以下になるとは正直思ってなかった。
やってることは単純に、最初に'1111111111'という文字列を作り、篩に当たったところを0にしていくだけです。

ちなみに偶数の素数は2だけなので、予め処理対象から外しておいて計算量を減らしています。
まあ対照実験やってないので本当に減ってるかどうかは不明ですが。

ググってみた限りでは、PHPでエラトステネスの篩を使うソースは全て配列での実装を行っており、文字列の実装をしている人は見当たりませんでした。
PR


2014/01/17 22:04 | Comments(2) | PHP

コメント

来週日曜日までネット環境が無くなるため、
更新を休みます。

…誰か見てるんだろうか。
posted by NurseAngel URL at 2014/01/17 22:32 [ コメントを修正する ]
ネット復旧日が未定になりました。
こまったね
posted by NurseAngel at 2014/01/25 21:30 [ コメントを修正する ]

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<買ったものリスト 2014/02/02 | HOME | PHP5.5.3 PHPでオブジェクトの強い型付け>>
忍者ブログ[PR]