弱小PHPerの憂鬱

前回の続き。

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_flatten1	0.08642秒	68228
array_flatten2	Maximum execution time of 30 seconds exceeded
array_flatten3	0.19846秒	68228
array_flatten4	0.32668秒	68228
array_flatten5	0.06959秒	68228
array_flatten6	0.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()より早くなりました。
クッソってほどではないのでなんか間違ってる気もしますが。