http://qiita.com/Nabetani/items/0a711729fdea28b1c30b
http://nabetani.sakura.ne.jp/hena/ord19sanwa/
・3つの数がある
・重複ありで1～3個選んで合計値を出す
・合計値の部分集合があるとき、元の3数を求めよ
・解がない場合は'none'、一意にならなければ'many'
どうやって解くんだこれ?
全探索しかないかな?
PHPにもcombination欲しいですね。
標準関数でなんでも揃うPHPなのに何故これはないんだろう。
しかし実は深刻なのはアドホックな例外対策のほうです。
今回は無理矢理'1,2,3'だけ除外していますが、他にも'1,2,4'や'1,2,5'など、最大数を使わないで作れる数について不正解になります。
あるいはもっと単純に'1'だけでも間違ってしまいます。
しかし今回はテストケース動くからまあいいや的な。
実装は2時間かかりました。
$i$j$kのあたりで大混乱。
なお実行にかかる時間は3秒程度。
PHPはやい。
http://nabetani.sakura.ne.jp/hena/ord19sanwa/
・3つの数がある
・重複ありで1～3個選んで合計値を出す
・合計値の部分集合があるとき、元の3数を求めよ
・解がない場合は'none'、一意にならなければ'many'
どうやって解くんだこれ?
全探索しかないかな?
<?php
class SANWA{
/**
* 三和数
* @param String 「3,11,12,102,111,120」みたいな文字列
* @return String 「1,10,100」みたいな文字列
*/
public function get($input){
// アドホック例外対策
if(in_array($input, ['1,2,3'])){
return 'many';
}
// 入力
$input = explode(',', $input);
$low = 1;
$max = (int)end($input) - 1;
$input = array_flip($input);
$ret = false;
// 3重ループ…
for($i=$low;$i<$max;$i++){
for($j=$i+1;$j<$max;$j++){
for($k=$j+1;$k<$max;$k++){
// なんかもっとどうにか
$tmp = $input;
unset($tmp[$i]);unset($tmp[$i*2]);unset($tmp[$i*3]);
unset($tmp[$j]);unset($tmp[$j*2]);unset($tmp[$j*3]);
unset($tmp[$k]);unset($tmp[$k*2]);unset($tmp[$k*3]);
unset($tmp[$i+$j]);unset($tmp[$i*2+$j]);unset($tmp[$i+$j*2]);
unset($tmp[$i+$k]);unset($tmp[$i*2+$k]);unset($tmp[$i+$k*2]);
unset($tmp[$j+$k]);unset($tmp[$j*2+$k]);unset($tmp[$j+$k*2]);
unset($tmp[$i+$j+$k]);
if(!$tmp){
if($ret){
return 'many';
}
$ret = $i.','.$j.','.$k;
}
}
}
}
return $ret ?: 'none';
}
}
// 以下はテスト
$test = [
['3,11,12,102,111,120', '1,10,100'],
['10,20,30,35,70', 'many'],
['1,5,20,80', 'none'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14', 'many'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14,15', '1,4,5'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14,17', 'none'],
['1,2,3,4,5,6,7,8,9,10,11,12,13,14,18', '1,4,6'],
['5,6,7,8,9,10,11,12,13,14,15,16', '2,5,6'],
['9,10,11,12,13,14,15,16,17,18,19', '4,5,7'],
['11,36,37,45,55,70,71', '1,10,35'],
['92,93,94,95,96,97,98,99', '30,32,33'],
['95,96,97,98,99,100', 'many'],
['27,30,34,37,43,44,46,51,57', '10,17,23'],
['6,10,13,17,65,73,76,80', 'none'],
['12,19,21,29,85', 'none'],
['1,2,8,10,14,23,58,62,64', 'none'],
['4,22,25,31,44,50,58,69,71,72,73,77', 'none'],
['8,16,26,27,42,53,65,69,81,83,88,99', 'none'],
['9,10,23,24,28,33,38,39,58,68,84', 'none'],
['11,16,24,26,88', 'none'],
['24,33,47,56,63,66,75,78,89,93', 'none'],
['7,26,72,77', 'many'],
['69,88,95,97', 'many'],
['9,14,48,89', 'many'],
['69,76,77,83', 'many'],
['11,14,24', 'many'],
['8,25,75,93', 'many'],
['11,55,93,98,99', 'many'],
['71,83,87', 'many'],
['22,76,77,92', '7,15,62'],
['33,61,66,83,95', '17,33,61'],
['6,16,49,55,72', '6,16,33'],
['62,85,97,98', '12,25,73'],
['54,60,67,70,72', '20,25,27'],
['54,61,68,84,87', '27,30,34'],
['65,67,69,75,79,89,99', '21,23,33'],
['69,72,80,81,89', '23,24,33'],
['1,2,3', 'many'],
];
$sanwa = new SANWA();
foreach($test as $key=>$data){
$answer = $sanwa->get($data[0]);
if($answer !== $data[1]){
print('えらー');
}
}
いやあunsetのあたりがなんともはや。PHPにもcombination欲しいですね。
標準関数でなんでも揃うPHPなのに何故これはないんだろう。
しかし実は深刻なのはアドホックな例外対策のほうです。
今回は無理矢理'1,2,3'だけ除外していますが、他にも'1,2,4'や'1,2,5'など、最大数を使わないで作れる数について不正解になります。
あるいはもっと単純に'1'だけでも間違ってしまいます。
しかし今回はテストケース動くからまあいいや的な。
実装は2時間かかりました。
$i$j$kのあたりで大混乱。
なお実行にかかる時間は3秒程度。
PHPはやい。
PR
LinuxにPHP5.6入れてる人ってのは既にいっぱいいますが、Windowsでやってる人はいないだろうから備忘録。
XAMPPはWindows上に一括でPHP環境を設置できてとても便利ですが、欠点としては最初からPHPバージョンが決まっているところです。
PHP5.6.0のα版を試したいんだよ、とか思ってもα版なんて普通は用意しません。
なので人力で入れてみましょう。
実はXAMPPはApacheとかPHPとかその他関連ソフトウェアをまとめてインストールしてくれるというだけなので、PHPを最新版にしたければ単にPHPを差し替えればいいです。
まずWindows版PHP公式から、欲しいバージョンのPHPを拾ってきます。
今回は5.6が試したかったので「PHP 5.6 (5.6.0alpha2) VC11 x86 Thread Safe」です。
XAMPPディレクトリにあるphpディレクトリの名前を適当に変えます。
解凍したPHPを今まであったphpディレクトリの場所に持ってきます。
これでPHPの入れ替え完了です。
Apacheを起動してphpinfo()を試してみましょう。
簡単ですね。
しかしデフォルトのPHPは本当に最低限のものしか入ってない状態です。
XAMPPがよしなにやってくれていたPHPの設定はありません。
なにしろmb_convert_encoding()すら無いので実用に耐えません。
というかphp.iniがありません。
php.iniを作りましょう。
まず「php.ini-development」をコピーして「php.ini」に改名します。
その後でXAMPPに入っていたphp.iniの項目をコピーしていくとよいでしょう。
不要な項目が多々あるので、まるごと上書きはやめときましょう。
最低限設定すべきところは
include_path
extension_dir
error_log
upload_tmp_dir
date.timezone
session.save_path
mbstring.**
あたりでしょうか。
あとはextensionから、必要なモジュールを有効にしましょう。
php_mbstring、php_pdo_mysql、php_mysqli、php_curlあたりは最低限で、それ以外は必要に応じてというかんじでしょう。
あとはApacheを再起動すれば終了。
これでPHP5.6.0が使えるようになりました。
XAMPPはWindows上に一括でPHP環境を設置できてとても便利ですが、欠点としては最初からPHPバージョンが決まっているところです。
PHP5.6.0のα版を試したいんだよ、とか思ってもα版なんて普通は用意しません。
なので人力で入れてみましょう。
実はXAMPPはApacheとかPHPとかその他関連ソフトウェアをまとめてインストールしてくれるというだけなので、PHPを最新版にしたければ単にPHPを差し替えればいいです。
まずWindows版PHP公式から、欲しいバージョンのPHPを拾ってきます。
今回は5.6が試したかったので「PHP 5.6 (5.6.0alpha2) VC11 x86 Thread Safe」です。
XAMPPディレクトリにあるphpディレクトリの名前を適当に変えます。
解凍したPHPを今まであったphpディレクトリの場所に持ってきます。
これでPHPの入れ替え完了です。
Apacheを起動してphpinfo()を試してみましょう。
簡単ですね。
しかしデフォルトのPHPは本当に最低限のものしか入ってない状態です。
XAMPPがよしなにやってくれていたPHPの設定はありません。
なにしろmb_convert_encoding()すら無いので実用に耐えません。
というかphp.iniがありません。
php.iniを作りましょう。
まず「php.ini-development」をコピーして「php.ini」に改名します。
その後でXAMPPに入っていたphp.iniの項目をコピーしていくとよいでしょう。
不要な項目が多々あるので、まるごと上書きはやめときましょう。
最低限設定すべきところは
include_path
extension_dir
error_log
upload_tmp_dir
date.timezone
session.save_path
mbstring.**
あたりでしょうか。
あとはextensionから、必要なモジュールを有効にしましょう。
php_mbstring、php_pdo_mysql、php_mysqli、php_curlあたりは最低限で、それ以外は必要に応じてというかんじでしょう。
あとはApacheを再起動すれば終了。
これでPHP5.6.0が使えるようになりました。
http://nabetani.sakura.ne.jp/hena/ord18notfork/
http://qiita.com/Nabetani/items/ad47666c2f2f44ada1e7
レジに並ぶ問題。
出遅れたので、せっかくだから無駄に頑張った実装をしてみる。
これでも1時間半で終わったので、普通に書けばもっと簡単だと思われます。
http://qiita.com/Nabetani/items/ad47666c2f2f44ada1e7
レジに並ぶ問題。
出遅れたので、せっかくだから無駄に頑張った実装をしてみる。
<?php
class NOTFORK{
/**
* スーパーのレジ
* @param String 「42873x.3.」みたいな文字列
* @return String 「0,4,2,0,0」みたいな文字列
*/
public function get($input){
// 処理できる人数
$a = array(2, 7, 3, 5, 2);
// 処理実行
$registerList = new RegisterList($a);
for($i=0;$i<strlen($input);$i++){
if($input[$i] === '.'){
// .はレジ処理
$registerList->pop();
}elseif($input[$i] === 'x'){
// xは困ったちゃん
$registerList->pushLocked();
}else{
// その他は数値
$registerList->push((int)$input[$i]);
}
}
// 返却
return implode(',', $registerList->countCustomers());
}
}
class RegisterList{
// レジのリスト
private $registers = array();
/**
* コンストラクタ
* @param array 処理できる人数の配列
*/
public function __construct($numbers){
foreach($numbers as $key=>$val){
$this->registers[] = new Register($val);
}
}
/**
* レジに並ぶ
* @param int 人数
*/
public function push($count){
$this->registers[$this->getLowestRegister()]->push($count);
}
/**
* 終わらない人が並ぶ
*/
public function pushLocked(){
$this->registers[$this->getLowestRegister()]->pushLocked();
}
/**
* 全レジを処理する
*/
public function pop(){
foreach($this->registers as $key=>$val){
$val->pop();
}
}
/**
* 並んでいる人が一番少ないレジを取得
* 同人数の場合は若いレジ
* @return int 少ないレジのキー
*/
private function getLowestRegister(){
$nowCount = $this->registers[0]->countCustomers();
$lowest = 0;
foreach($this->registers as $key=>$val){
if($nowCount > $val->countCustomers()){
$nowCount = $val->countCustomers();
$lowest = $key;
}
}
return $lowest;
}
/**
* 全レジの人数を取得
* @return array 人数の配列
*/
public function countCustomers(){
$ret = [];
foreach($this->registers as $key=>$val){
$ret[] = $val->countCustomers();
}
return $ret;
}
}
class Register{
// 終わらない人が一番手前に並んでる
private $isLocked = false;
// 一回のレジで処理できる人数
private $number = 1;
// 並んでる人のリスト
private $customers = [];
/**
* コンストラクタ
* @param int 一回で処理できる人数
*/
public function __construct($number){
$this->number = $number;
}
/**
* ロック状態か
* @return ロックされていればtrue
*/
private function isLocked(){
return $this->isLocked;
}
/**
* 並んでいる人数を取得
* @return 並んでいる人数
*/
public function countCustomers(){
return count($this->customers);
}
/**
* 並ぶ
* @param int 並ぶ人数
*/
public function push($count = 1){
for($i=0;$i<$count;$i++){
$this->customers[] = new Customer();
}
}
/**
* 終わらない人が並ぶ
*/
public function pushLocked(){
$this->customers[] = new LockedCustomer();
}
/**
* レジを処理する
*/
public function pop(){
if($this->isLocked()){ return false; }
for($i=0;$i<$this->number;$i++){
if($this->countCustomers() > 0){
if($this->customers[0]->isLocked()){
$this->isLocked = true;
return;
}else{
array_shift($this->customers);
}
}
}
}
}
class Customer{
const isLocked = false;
public function isLocked(){
return static::isLocked;
}
}
class LockedCustomer extends Customer{
const isLocked = true;
}
// 以下はテスト
$test = [
['42873x.3.', '0,4,2,0,0'],
['1', '1,0,0,0,0'],
['.', '0,0,0,0,0'],
['x', '1,0,0,0,0'],
['31.', '1,0,0,0,0'],
['3x.', '1,1,0,0,0'],
['99569x', '9,9,6,6,9'],
['99569x33', '9,9,9,9,9'],
['99569x33.', '7,2,6,4,7'],
['99569x33..', '5,0,4,0,5'],
['12345x3333.', '4,0,3,2,3'],
['54321x3333.', '3,0,3,0,4'],
['51423x3333.', '3,4,4,0,4'],
['12x34x.', '1,0,1,0,2'],
['987x654x.32', '7,6,4,10,5'],
['99999999999x99999999.......9.', '20,10,12,5,20'],
['997', '9,9,7,0,0'],
['.3.9', '1,9,0,0,0'],
['832.6', '6,6,0,0,0'],
['.5.568', '3,5,6,8,0'],
['475..48', '4,8,0,0,0'],
['7.2..469', '1,4,6,9,0'],
['574x315.3', '3,3,1,7,1'],
['5.2893.x98', '10,9,5,4,1'],
['279.6xxx..4', '2,1,4,1,1'],
['1.1.39..93.x', '7,1,0,0,0'],
['7677749325927', '16,12,17,18,12'],
['x6235.87.56.9.', '7,2,0,0,0'],
['4.1168.6.197.6.', '0,0,3,0,0'],
['2.8.547.25..19.6', '6,2,0,0,0'],
['.5.3x82x32.1829..', '5,0,5,0,7'],
['x.1816..36.24.429.', '1,0,0,0,7'],
['79.2.6.81x..26x31.1', '1,0,2,1,1'],
['574296x6538984..5974', '14,13,10,15,14'],
['99.6244.4376636..72.6', '5,6,0,0,3'],
['1659.486x5637168278123', '17,16,16,18,17'],
['.5.17797.x626x5x9457.3.', '14,0,3,5,8'],
['..58624.85623..4.7..23.x', '1,1,0,0,0'],
['716.463.9.x.8..4.15.738x4', '7,3,5,8,1'],
['22xx.191.96469472.7232377.', '10,11,18,12,9'],
['24..4...343......4.41.6...2', '2,0,0,0,0'],
['32732.474x153.866..4x29.2573', '7,5,7,8,5'],
['786.1267x9937.17.15448.1x33.4', '4,4,8,4,10'],
['671714849.149.686852.178.895x3', '13,16,13,10,12'],
['86x.47.517..29621.61x937..xx935', '7,11,8,8,10'],
['.2233.78x.94.x59511.5.86x3.x714.', '4,6,10,8,8'],
['.793...218.687x415x13.1...x58576x', '8,11,8,6,9'],
['6.6x37.3x51x932.72x4x33.9363.x7761', '15,13,15,12,15'],
['6..4.x187..681.2x.2.713276.669x.252', '6,7,8,6,5'],
['.6.xx64..5146x897231.x.21265392x9775', '19,17,19,20,17'],
['334.85413.263314.x.6293921x3.6357647x', '14,14,12,16,10'],
['4.1..9..513.266..5999769852.2.38x79.x7', '12,10,13,6,10'],
];
$notfork = new NOTFORK();
foreach($test as $key=>$data){
$answer = $notfork->get($data[0]);
if($answer !== $data[1]){
print('えらー');
}
}
使い回す予定があるならともかく、書き捨てるプログラムでこんなことやっても意味はないのですが。これでも1時間半で終わったので、普通に書けばもっと簡単だと思われます。
https://bugs.php.net/bug.php?id=65502
え？
http://www.php.net/ChangeLog-5.php#5.5.5
PHP5.5.5で修正されたそうです。
https://bugs.php.net/bug.php?id=65548
え？
http://www.php.net/manual/ja/datetime.diff.php
> PHP 5.2.2 以降では、DateTime オブジェクトを 比較演算子 で比較できるようになりました。
http://www.php.net/ChangeLog-5.php#5.5.5
PHP5.5.5で修正されたそうです。
http://bugs.php.net/65768
え？
http://jp2.php.net/manual/ja/datetime.diff.php
> public DateInterval DateTimeImmutable::diff ( DateTimeInterface $datetime2 [, bool $absolute = false ] )
http://www.php.net/ChangeLog-5.php#5.5.8
PHP5.5.8で修正されたそうです。
DateTimeImmutableクラスはPHP5.5で追加されたクラスで、最初に設定した日時を変更することができないDateTimeです。
変えられない日付(イベントの日時など)を設定しておいて、それからの差分を求めたりなんかしたい場合に便利です。
が、しかしこうもバグがあると使うのが躊躇われますね。
PHP5.5からDateTimeInterfaceインターフェイスが追加され、DateTimeとDateTimeImmutableはDateTimeInterfaceをimplementsするようになりました。
しかしIntlDateFormatter::formatなど、元々DateTimeを要求していたところが未だそのままになっていたりするなど、周囲の変更が追いついていないようです。
え？
<?php
$today = DateTimeImmutable::createFromFormat('Y-m-d H:i:s', '2014-01-01 00:00:00');
var_dump($today);
object(DateTime)#3 (3) {
["date"]=>
string(19) "2014-01-01 00:00:00"
["timezone_type"]=>
int(3)
["timezone"]=>
string(10) "Asia/Tokyo"
}
これはひどい。http://www.php.net/ChangeLog-5.php#5.5.5
PHP5.5.5で修正されたそうです。
https://bugs.php.net/bug.php?id=65548
え？
http://www.php.net/manual/ja/datetime.diff.php
> PHP 5.2.2 以降では、DateTime オブジェクトを 比較演算子 で比較できるようになりました。
<?php
$today = new DateTimeImmutable('2014/01/01 00:00:00');
$tomorrow = new DateTimeImmutable('2014/01/02 00:00:00');
var_dump($today < $tomorrow , $today > $tomorrow, $today == $tomorrow);
bool(false)
bool(false)
bool(false)
これはひどい。http://www.php.net/ChangeLog-5.php#5.5.5
PHP5.5.5で修正されたそうです。
http://bugs.php.net/65768
え？
http://jp2.php.net/manual/ja/datetime.diff.php
> public DateInterval DateTimeImmutable::diff ( DateTimeInterface $datetime2 [, bool $absolute = false ] )
<?php
$now = new DateTimeImmutable('now');
$hour = new DateTimeImmutable('+1 hour');
var_dump($now->diff($hour));
DateTime::diff() must be derived from DateTimeImmutable::diff
これはひどい。http://www.php.net/ChangeLog-5.php#5.5.8
PHP5.5.8で修正されたそうです。
DateTimeImmutableクラスはPHP5.5で追加されたクラスで、最初に設定した日時を変更することができないDateTimeです。
<?php
$today = new DateTimeImmutable('2014/01/01 00:00:00');
$tomorrow = $today->modify('+1 day');
print($tomorrow->format('Y-m-d H:i:s')); // 2014-01-02 00:00:00
print($today->format('Y-m-d H:i:s')); // 2014-01-01 00:00:00のまま
DateTime::modify()は自分自身を変更しますが、DateTimeImmutable::modify()は自分は変えずに変更後の値を返すという挙動になります。変えられない日付(イベントの日時など)を設定しておいて、それからの差分を求めたりなんかしたい場合に便利です。
が、しかしこうもバグがあると使うのが躊躇われますね。
PHP5.5からDateTimeInterfaceインターフェイスが追加され、DateTimeとDateTimeImmutableはDateTimeInterfaceをimplementsするようになりました。
しかしIntlDateFormatter::formatなど、元々DateTimeを要求していたところが未だそのままになっていたりするなど、周囲の変更が追いついていないようです。
素数出力プログラミング大会
http://person-link.co.jp/blog/detail/32
1時間でやるならまだしも、一週間も期間があるのに誰もエラトステネスの篩書いてないとかどういうことだよ。
計測方法は2回計った平均値というかなり意味のない値なので、オーダー程度に見てください。
2番目と3番目ひどいな。
10000件の時点で既に他と100倍～1000倍の差があります。
毎回echoしているせいかと最後にまとめて出力してみたのですが変わりませんでした。
何故ここまで違うんだろう。
篩のほうは値が大きくなるほど処理対象が少なくなるため、10000件程度ではtanaka_sosu.phpとあまりかわりませんが、1000000件まで行くと相対的に処理時間が減っていきます。
はじめ何も考えずにArrayIteratorで書いたのですが、最初に50万件のArrayIteratorをががっと作ってしまうので、使用メモリがえらいことになってます。
1000万件を処理しようとしたら死にます。
あまりに残念だったので書き直してみたのがstr_repeat()を使う方。
メモリ使用量が激減したのは想定通りですが、実行時間まで半分以下になるとは正直思ってなかった。
やってることは単純に、最初に'1111111111'という文字列を作り、篩に当たったところを0にしていくだけです。
ちなみに偶数の素数は2だけなので、予め処理対象から外しておいて計算量を減らしています。
まあ対照実験やってないので本当に減ってるかどうかは不明ですが。
ググってみた限りでは、PHPでエラトステネスの篩を使うソースは全て配列での実装を行っており、文字列の実装をしている人は見当たりませんでした。
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でエラトステネスの篩を使うソースは全て配列での実装を行っており、文字列の実装をしている人は見当たりませんでした。
前回SplTypeを使って厳密なSplInt型を作りました。
が、用意されているのはint、stringといったスカラー型だけでした。
自作のクラスに対応するためにSplTypeが用意されています。
SplTypeはabstractなクラスです。
何故インターフェイスじゃないんだ。
PHPは型付けが～とか言ってる人はいっぱいいるけど、これを紹介してる人がただの一人もいないってのはどういうことですかね。
せっかくなので、runkitで全クラスに強制的にSplTypeを継承させてしまいましょう。
調べてみたらrunkit_class_adoptは一見親クラスを付け替えているように見えますが、実際は本当に変更しているわけではなくエミュレーション的なことをしているみたいです。
自作クラスでも一部情報が飛んでしまい、SplTypeのような特殊なクラスではその特殊性が失われます。
ということで全自動強い型付け言語PHPの夢は破れてしまいました。
型付けとかは開発時にしか必要のない機能なので、php.iniあたりでSplType強制を設定できるようになってくれれば、とても便利だと思うのですがどうでしょう >開発者
SplTypeを使いこなせば、開発に非常に強力な武器となってくれるでしょう。
あと強い型付け言語使いから大きな顔をされることもなくなるでしょう。
が、用意されているのはint、stringといったスカラー型だけでした。
自作のクラスに対応するためにSplTypeが用意されています。
SplTypeはabstractなクラスです。
何故インターフェイスじゃないんだ。
<?php
class HOGE extends SplType{}
$hoge = new HOGE();
$hoge = 1; // Uncaught exception 'UnexpectedValueException'
あれ、これ全クラスをextends SplTypeってしとけば強い型付け言語PHPの誕生じゃね？PHPは型付けが～とか言ってる人はいっぱいいるけど、これを紹介してる人がただの一人もいないってのはどういうことですかね。
せっかくなので、runkitで全クラスに強制的にSplTypeを継承させてしまいましょう。
<?php
class HOGE{}
$classes = get_declared_classes();
class SplTypeTmp extends SplType{}
$tmp = error_reporting(0);
foreach(get_declared_classes() as $key=>$val){
if(!get_parent_class($val)){
runkit_class_adopt($val, 'SplTypeTmp');
}
}
error_reporting($tmp);
$x = new HOGE();
$x = 1; // 普通に入った
あれ？調べてみたらrunkit_class_adoptは一見親クラスを付け替えているように見えますが、実際は本当に変更しているわけではなくエミュレーション的なことをしているみたいです。
自作クラスでも一部情報が飛んでしまい、SplTypeのような特殊なクラスではその特殊性が失われます。
ということで全自動強い型付け言語PHPの夢は破れてしまいました。
型付けとかは開発時にしか必要のない機能なので、php.iniあたりでSplType強制を設定できるようになってくれれば、とても便利だと思うのですがどうでしょう >開発者
SplTypeを使いこなせば、開発に非常に強力な武器となってくれるでしょう。
あと強い型付け言語使いから大きな顔をされることもなくなるでしょう。
<?php $object = new stdClass(); $object = '1' + 1; $boolean = ( '1' == 1 );$objectはint型の2、$booleanはtrueになり、Java出身者が憤死します。
PHPの型の挙動には色々と論がある人も多いですが、PHPの特徴だと思って諦めましょう。
まあ私はこういうの嫌いではないですが、推移律が成り立たないのはさすがにどうかと思う。
しかし時には、どうしても厳密に型を適用したいんだよ、という場合があるかもしれません。
そんなときのためにSplTypeです。
今のところデフォルトでは入ってないのでPECLから持ってきましょう。
Windows版のDLLも存在します。
<?php
$int = new SplInt(1);
$int = 2; // 2
$int++; // 3
$int = 1.0; // Fatal error: Uncaught exception 'UnexpectedValueException'
$int = 'a'; // Fatal error: Uncaught exception 'UnexpectedValueException'
$a = $int + 10; // 13
for($i=1; $i<$int; $i++){} // 問題なく動作
PHPがあたかもRubyのような強い型付けに！$intは、intもしくはSplInt以外を代入しようとするとUnexpectedValueExceptionを発生します。
これで$intの型一意性が保証されることになりました。
逆に$intを演算に使う場合は、ただの整数と同じように扱えます。
型付けの対象としては、int以外にfloat、boolean、stringの各スカラー型、そしてEnum型が用意されています。
ところで、
http://www.php.net/manual/ja/intro.spl-types.php
> スカラー型のタイプヒンティングの代替手段として使用できます。
って書いてあるのですが、あくまで代替のようで完全なタイプヒンティングとしては使えませんでした。
<?php
class HOGE{
private $int;
// setSplIntは呼び出し側でキャストしないといけない
public function setSplInt(SplInt $int){
$this->int = $int;
}
// setIntは概ね想定した動作だがタイプヒンティングではない
public function setInt($int){
$this->int = new SplInt($int);
}
}
$hoge = new HOGE();
$hoge->setSplInt(new SplInt(1));
$hoge->setSplInt(1); // Argument 1 must be an instance of SplInt, integer given
$hoge->setInt(2);
$hoge->setInt(2.0); // Uncaught exception 'UnexpectedValueException'
まあ後者で作っておけば実質的には困らないと思います。
前回の続き。
runkitにはクラスに対しても色々やっちゃうことが可能です。
ここでは前やったprivateな__construct()呼び出しを、runkitを使ってやってみます。
いいのかそれ。
なお、最近のPHP関数は引数にクロージャを受け付けてくれるものが多いですが、runkit_method_add()等は文字列しか駄目なようです。
runkitはあまりに強力すぎるため、実環境で使うことはまず無いでしょう。
こんな風に遊んでみるくらいならともかく、仕事でこんなことをやられたらたまったものではありません。
runkitにはクラスに対しても色々やっちゃうことが可能です。
<?php
// クラス
class A{ public static function getName(){print('A');} }
class B{ public static function getName(){print('B');} }
class C extends A{}
print(C::getName()); // A
runkit_constant_add('C::hoge', 1);
print(C::hoge); // 1
runkit_class_emancipate('C');
print(C::getName()); // Fatal error: Call to undefined method C::getName()
runkit_class_adopt('C', 'B');
print(C::getName()); // B
クラス定数やメソッドの追加削除に留まらず、親クラス入れ替えなんて芸当もできてしまいます。ここでは前やったprivateな__construct()呼び出しを、runkitを使ってやってみます。
<?php
class HOGE{
public $value = 0;
private function __construct(){
$this->value = 1;
}
}
runkit_method_rename('HOGE', '__construct', 'construct');
runkit_method_add('HOGE', '__construct', '', '$this->construct();', RUNKIT_ACC_PUBLIC);
$hoge = new HOGE();
print $hoge->value; // 1
クラスを書き換えた結果、最終的にはこういう形になっていると思われます。<?php
class HOGE{
public $value = 0;
public function __construct(){
$this->construct();
}
private function construct(){
$this->value = 1;
}
}
これならごく自然にnewできますね。いいのかそれ。
なお、最近のPHP関数は引数にクロージャを受け付けてくれるものが多いですが、runkit_method_add()等は文字列しか駄目なようです。
runkitはあまりに強力すぎるため、実環境で使うことはまず無いでしょう。
こんな風に遊んでみるくらいならともかく、仕事でこんなことをやられたらたまったものではありません。
PHP界きっての反則技、runkit。
昔はXAMPPにデフォルトで入っていたのですが、いつのまにか消えていました。
もはやPECLがメンテナンスされてないんですよね。
Windows版runkitをメンテしてる人を見つけたので試してみます。
試したバージョンは「php_runkit-1.0.4-5e179e978a-5.5-vc11.dll」。
TSのほうです。
ダウンロードしたファイルをxampp/php/ext内に入れて、php.iniに
phpinfo()でrunkitの項目が追加されていることを確認しましょう。
runkitを使うと、通常では絶対に有り得ないコーディングが可能になります。
見てのとおり、定数も関数も制限？何それってレベルで上書きできてしまいます。
runkit.internal_overrideは組み込み関数のオーバーライドを制御するディレクティブです。
デフォルトはfalseで、ユーザ定義関数しか上書きできません。
trueにすると上記のようにphpinfo()等も上書きできるようになります。
さすがにechoのような言語構造は上書きできません。
runkit.superglobalは、「スーパーグローバル変数として扱う変数を追加する」というこれまた反則なディレクティブです。
今回は"_FOO"を追加しているので、$_FOOが$_REQUEST等と同格のスーパーグローバル変数になります。
runkit_superglobals()は、現在のスーパーグローバル変数一覧を取得します。
$GLOBALS、$_REQUEST、$_SESSIONといった見慣れた変数と一緒に$_FOOが入っているのが確認できます。
runkit_return_value_used()は他と毛色の違う関数で、関数呼び出しが、その返り値を使っているかを確認できるという、どういうときに使うのかよくわからない機能です。
いやほんとこれどういうときに使うんだ？
あとrunkit_lint()でコードチェックとかも可能なはずなのですが、手元環境ではapache毎落ちてしまって確認できませんでした。
理由はよくわかりません。
昔はXAMPPにデフォルトで入っていたのですが、いつのまにか消えていました。
もはやPECLがメンテナンスされてないんですよね。
Windows版runkitをメンテしてる人を見つけたので試してみます。
試したバージョンは「php_runkit-1.0.4-5e179e978a-5.5-vc11.dll」。
TSのほうです。
ダウンロードしたファイルをxampp/php/ext内に入れて、php.iniに
extension=php_runkit.dll runkit.internal_override = true runkit.superglobal = _FOOと書いておきます。
phpinfo()でrunkitの項目が追加されていることを確認しましょう。
runkitを使うと、通常では絶対に有り得ないコーディングが可能になります。
<?php
// 定数
define('HOGE', 1);
print(HOGE); // 1
runkit_constant_redefine('HOGE', 2);
print(HOGE); // 2
runkit_constant_remove('HOGE');
print(HOGE); // Notice: Use of undefined constant HOGE
// 関数
runkit_function_redefine('phpinfo', null, 'print("a");');
phpinfo(); // "a"と表示される
runkit_function_remove('phpinfo');
phpinfo(); // Call to undefined function phpinfo()
// 返り値を利用しているか確認
function foo() {
var_dump(runkit_return_value_used());
}
foo(); // false
$a = foo(); // true
// スーパーグローバル
$_FOO = 'foo';
$_BAR = 'bar';
function test(){
print($_FOO); // foo
print($_BAR); // Notice: Undefined variable: _BAR
}
test();
var_dump(runkit_superglobals());
掟破りにも程があるだろ。見てのとおり、定数も関数も制限？何それってレベルで上書きできてしまいます。
runkit.internal_overrideは組み込み関数のオーバーライドを制御するディレクティブです。
デフォルトはfalseで、ユーザ定義関数しか上書きできません。
trueにすると上記のようにphpinfo()等も上書きできるようになります。
さすがにechoのような言語構造は上書きできません。
runkit.superglobalは、「スーパーグローバル変数として扱う変数を追加する」というこれまた反則なディレクティブです。
今回は"_FOO"を追加しているので、$_FOOが$_REQUEST等と同格のスーパーグローバル変数になります。
runkit_superglobals()は、現在のスーパーグローバル変数一覧を取得します。
$GLOBALS、$_REQUEST、$_SESSIONといった見慣れた変数と一緒に$_FOOが入っているのが確認できます。
runkit_return_value_used()は他と毛色の違う関数で、関数呼び出しが、その返り値を使っているかを確認できるという、どういうときに使うのかよくわからない機能です。
いやほんとこれどういうときに使うんだ？
あとrunkit_lint()でコードチェックとかも可能なはずなのですが、手元環境ではapache毎落ちてしまって確認できませんでした。
理由はよくわかりません。
PHPはソースが平文です。
シェアウェアのMovableTypeや、はてまた糞高いSitePublisですら、ソースさえ手に入れてしまえばどうとでもできてしまいます。
ということでソースを暗号化してしまいましょう。
BlencというBLowfishライブラリを見つけましたが、日本語情報がマニュアルのコピペサイト以外一切ありません。
どうなってんだ。
PECLなのでLinuxであれば適当にpecl installとかしてください。
Windowsはdllが用意されているので拾ってきてphp.iniにextensionを書けばOKです。
デフォルトは'/usr/local/etc/blenckeys'になっているので、Windowsでは変更必須です。
ini_set()で変更してもいいです。
中を見てみると、全く読むことができない状態になっているのがわかります。
そしてこのhoge.encrypt.php、直接PHPファイルとして取り扱い可能です。
Fatal error: blenc_compile: Module php_blenc was expired. Please buy a new license key or disable the module. in Unknown on line 0
おうふ。
expiredってなんだよ。
Blencのソースを見てみる。
http://svn.php.net/viewvc/pecl/blenc/trunk/blenc.c?view=markup
ということでソースからコンパイルできる人続きを頼んだ。
シェアウェアのMovableTypeや、はてまた糞高いSitePublisですら、ソースさえ手に入れてしまえばどうとでもできてしまいます。
ということでソースを暗号化してしまいましょう。
BlencというBLowfishライブラリを見つけましたが、日本語情報がマニュアルのコピペサイト以外一切ありません。
どうなってんだ。
PECLなのでLinuxであれば適当にpecl installとかしてください。
Windowsはdllが用意されているので拾ってきてphp.iniにextensionを書けばOKです。
extension=php_blenc.dll blenc.key_file = C:\xampp\blenc.key_fileblenc.key_fileは暗号化キーを保存する場所の設定です。
デフォルトは'/usr/local/etc/blenckeys'になっているので、Windowsでは変更必須です。
ini_set()で変更してもいいです。
<?php
// 暗号化するソース
$source = file_get_contents('path/to/hoge.php');
// 暗号化して書き込み。返り値は暗号化キー
$key = blenc_encrypt($source, 'path/to/hoge.encrypt.php');
// 暗号化キーも保存
file_put_contents($ini_get('blenc.key_file'), $key, FILE_APPEND);
hoge.phpをBlowfishで暗号化した結果がhoge.encrypt.phpとして保存されました。中を見てみると、全く読むことができない状態になっているのがわかります。
そしてこのhoge.encrypt.php、直接PHPファイルとして取り扱い可能です。
Fatal error: blenc_compile: Module php_blenc was expired. Please buy a new license key or disable the module. in Unknown on line 0
おうふ。
expiredってなんだよ。
Blencのソースを見てみる。
http://svn.php.net/viewvc/pecl/blenc/trunk/blenc.c?view=markup
// エラーはここで発生
if(BL_G(expired)) {
zend_error(E_ERROR, "blenc_compile: Module php_blenc was expired. Please buy a new license key or disable the module.");
return NULL;
}
// BL_Gはexpire_charと比較してる
BL_G(expire_date) = pemalloc(sizeof(expire_char), TRUE);
// expire_charはBLENC_PROTECT_EXPIRE
char expire_char[] = BLENC_PROTECT_EXPIRE;
http://svn.php.net/viewvc/pecl/blenc/trunk/blenc_protect.h?view=markup// BLENC_PROTECT_EXPIREは2013年4月30日 #define BLENC_PROTECT_EXPIRE "30-04-2013"なんだこれ。
ということでソースからコンパイルできる人続きを頼んだ。
