忍者ブログ
[PR]
×

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



2017/03/23 17:17 |
PHP5.4.7 PHPでarray_flatten関数のパフォーマンス測定
前回の続き。

http://bloggdgd.blog28.fc2.com/blog-entry-272.html
> 「Recursive」って入ってるけど

なんてこった、Recursiveは再帰って発想はなかった。
いや、皮肉とかじゃなくて素で気付いてなかった。

さて、せっかくなので色々見つけたarray_flatten関数のパフォーマンスを測定してみます。
<?php
	// by NurseAngel
	// http://yuubiseiharukana.blog.shinobi.jp/Entry/1155/
	function array_flatten1($arr) {
		 return iterator_to_array(new RecursiveIteratorIterator(new RecursiveArrayIterator($arr)), false);
	}
	
	// by CertaiN
	// http://bloggdgd.blog28.fc2.com/blog-entry-272.html
	function array_flatten2($arr) {
		$arr = array_values($arr);
		while (list($k,$v)=each($arr)) {
			if (is_array($v)) {
				array_splice($arr,$k,1,$v);
				next($arr);
			}
		}
		return $arr;
	}
	
	// by Happy Programming
	// http://blog.beanz-net.jp/happy_programming/2008/11/phparray-flatten.html
	function array_flatten3($array) {
		$tmp = array();
		while (($val = array_shift($array)) !== null) {
			if (is_array($val)) $array = array_merge($val, $array);
			else $tmp[] = $val;
		}
		return $tmp;
	}
	
	// by wellandpower at hotmail.com
	// http://www.php.net/manual/en/function.array-values.php#77542
	function array_flatten4($array) {
		$flat = array();
		foreach ($array as $value) {
			if (is_array($value)) $flat = array_merge($flat, array_flatten4($value));
			else $flat[] = $value;
		}
		return $flat;
	}
	
	// by might
	// http://might1976.doorblog.jp/archives/51164023.html#more
	function array_flatten5($array){
		$result = array();
		array_walk_recursive($array, function($v) use (&$result){
			$result[] = $v;
		});
		return $result;
	}
	
	// by crashrox at gmail dot com
	// http://www.php.net/manual/ja/class.recursiveiteratoriterator.php#87757
	function array_flatten6($array) {
		if($array) {
			$flat = array();
			foreach(new RecursiveIteratorIterator(new RecursiveArrayIterator($array), RecursiveIteratorIterator::SELF_FIRST) as $key=>$value) {
				if(!is_array($value)) {
					$flat[] = $value;
				}
			}
			return $flat;
		} else {
			return false;
		}
	}

似てるっぽいのは除いて、6種類を適当に試してみました。

array_flatten1()は前回作ったやつで、自力では一切何もせずSPLに任せっきりです。

array_flatten2()はCertaiN氏の「再帰を使わないものでは最も美しい」関数です。
array_splice()なんて初めて見たよ。

array_flatten3()も再帰を使わないパターンですが、array_flatten2()よりは平易に書かれています。
まあループ中で自分自身を更新しててややこしいのはかわらないのですが。

array_flatten4()は、典型的な再帰パターンです。
私が何も参考にせず一から書いたらこうなっていたと思います。

array_flatten5()は再帰にarray_walk_recursive()を用いたパターン。
正直array_walk_recursive()難しいです。

array_flatten6()はおまけです。
中身はarray_flatten1()とほぼ同じで、一番外側のiterator_to_array()だけを手動でやってるわけですが、ビルトイン関数とどちらが早いでしょうか。

関数処理時間展開後の個数
array_flatten10.08642秒68228
array_flatten2Maximum execution time of 30 seconds exceeded
array_flatten30.19846秒68228
array_flatten40.32668秒68228
array_flatten50.06959秒68228
array_flatten60.11780秒68228

展開後の個数は動作確認用です。
最大10階層のランダム構造、変数の個数の合計は見てのとおり68228個の多重配列を1次元に展開しています。
一発取りなので多少の誤差はありますが、何回かやっても時間が逆転するほどの違いはありませんでした。

1位はarray_flatten5。
array_walk_recursive()ちょっぱや!

2位はarray_flatten1。
簡潔で美しい上に速度も速い。
素晴らしい。

--0.1秒の壁--

3位はarray_flatten6。
foreachを手動で回したぶんだけ遅くなっているのでしょうか。
こーゆーのはビルトイン使っとけば基本問題無いんですよ。

4位はarray_flatten3。
array_flatten2とあまり変わらないように見えるのですが早いですね。
やはりarray_shift()やarray_merge()のようなよく使われる関数は最適化も進んでいるのでしょうか

--0.2秒の壁--

5位はarray_flatten4。
再帰はやはり何度も関数呼び出しが入るぶん遅くなってしまうのでしょうか。
やってることはそんなに変わらないはずのarray_walk_recursive()に比べて4倍近い時間がかかっていますね。

--0.4秒の壁--

残念ながらarray_flatten2は問題外という結果になりました。
幾ら美しくても実用に耐えなくては役に立ちません。


ちなみに計測に用いた配列は以下で生成しました。
function mkarray($depth = 0, $stop = 0){
	if($depth <= 0 || $stop !== 0){
		return mt_rand(1, 10);
	}else{
		$ret = array_fill(0, mt_rand(1, 10), '1');
		foreach($ret as $key=>$val){
			$ret[$key] = mkarray(($depth-1), mt_rand(0, 2));
		}
		return $ret;
	}
}
$arr = mkarray(10);
何度かvar_export()して、大きめの配列が生成されたときにそれを保存して使用しました。

2013/05/29追記
http://bloggdgd.blog28.fc2.com/blog-entry-278.html
CertaiN氏の検証によりますと、array_merge()とarray_splice()そのものについてはarray_splice()のほうが早いようです。
Cのソース読めないので本当はどういう実装になっているのかは知らないのですが、マニュアルのコメント欄などでも「array_splice()の方がはえーよ」との声が多いようです。
http://php.net/manual/ja/function.array-splice.php
http://php.net/manual/ja/function.array-merge.php
従ってarray_flatten2()がタイムアウトでarray_flatten4()がそれなりに早い理由は、それ以外の部分(おそらくforeachとwhile)にあるであろうということです。

2013/05/30追記
http://yuubiseiharukana.blog.shinobi.jp/Entry/1174/
array_flatten3()にarray_splice()やったらarray_flatten3()より早くなりました。
クッソってほどではないのでなんか間違ってる気もしますが。

PR


2013/05/02 23:59 | Comments(3) | PHP

コメント

納得した点と疑問に感じた点をまとめたのでご覧いただければ幸いです。
http://bloggdgd.blog28.fc2.com/blog-entry-278.html
posted by CertaiN at 2013/05/28 14:08 [ コメントを修正する ]
array_merge()とarray_splice()について追記しました。
最適化云々のあたりはこちらの間違い(というかそんなに深く考えてなかった)ですので削除しました。

ただ「array_splice()なんて初めて見たよ」に突っ込まれるのは、その、なんだ、困る。
まあ初めて見たってのはさすがに言いすぎですが、能動的に使ったことはないです。
私は再帰使うのに全く抵抗が無いので、技巧を凝らすより普通に自分を呼び出しちゃいますので。

あとでarray_flatten3()にarray_splice()やった結果も追加しときます。
posted by NurseAngel URL at 2013/05/29 00:52 [ コメントを修正する ]
何気ない言葉を偏向的に受け取ってしまってすみません。

OKWaveで質問してみたら素晴らしい回答が得られたので報告させていただきます。
http://okwave.jp/qa/q8109749.html

先頭要素を操作したときに内部ポインタの予期していなかった挙動により、そこからnext関数がバグを引き起こし、遅いとかそれ以前の問題だったようです・・・(目から鱗)
(遅さの根本的な原因は依然として確定的には分かりませんが…)

バグのあるコードを記載し続けるわけにはいかない(というか私自身も許せない)ので、その旨記事を訂正しておきます。


今回の件ではいろいろお騒がせしました。
自分自身の勉強のためにもなったので非常に価値ある経験になりそうです。

今後また機会がありましたらよろしくお願いします。
posted by CertaiN URL at 2013/05/29 19:03 [ コメントを修正する ]

コメントを投稿する






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



<<Zend Framework2.1.4 Zend\Stdlib\SplPriorityQueue | HOME | PHP5.4.7 PHPでarray_flatten関数>>
忍者ブログ[PR]