php合并多维数组子集的一个问题

Question

比如一个多维数组

$arr = array(
    '0'=>array('1','2'),
    '1'=>array('2','3'),
    '2'=>array('3','4'),
    '3'=>array('4','5'),
    '4'=>array('5','6'),
)

我要合并$arr的所有子集数组变成一个新的数组

$new_arr = array('1','2','2','3','3','4','4','5','5','6');

最快的方法是什么

Answer 1

array_walk版一号代码：

$res = array();
array_walk($arr, function($item, $key) use (&$res) {$res = array_merge($res, $item);});

array_walk_recursive版二号代码:

$res = array();
array_walk_recursive($arr, function($item, $key) use (&$res) {$res[] = $item;});

优美的写法需要PHP版本的支持，如果不支持的话就把匿名函数和use改成普通函数和global的形式就好了。

补充答案：

foreach循环普通版三号代码：

$res = array();
foreach($arr as $item) {$res = array_merge($res, $item);}

double foreach嵌套循环普通版四号代码：

见 @thbourlove 的答案。

既然题主强调了一下时间的话那我就认真做一个测评好了，为了增加可比性我又写了一个普通版用循环的第三版作为对比代码，通过测试得到四组代码在不同数组长度的情况下所消耗的时间的一个表：

	array_walk	array_walk_recursive	foreach	double foreach
500	0.12	0.003	0.067	0.003
100	0.45	0.006	0.331	0.003
1500	1.7	0.005	1.523	0.003
2000	3.38	0.005	2.092	0.003
2500	6.16	0.008	4.126	0.004
3000	10.15	0.010	6.258	0.005

*注1：表格左侧为数组的长度，默认算的是一级数组，例如题目中的数组长度为5。每个二级数组的长度统一为题目示例中的2。
*注2：表格中的数据默认单位为秒
*注3：本来其实测试数据为100000长度的数组的，结果array_walk花了204s，我就放弃那么长了。
*注4：double foreach的代码参见 @thbourlove 的答案，另外此算法的运算时间由于之前三者比较的数据已经不存在了，所以我重新找了一组规格相同的数据和第二种算法做了同期测试，并根据两组数据之间的关系得到了表格现在的数据。

通过以上数据可以得出，性能方面的话还是 @thbourlove 的嵌套循环是最高的，不过个人是代码美观控，所以还是比较偏爱第二种。

通过以上数据可以得出三种方法中array_walk_recursive方法无疑是最快的。

array_walk_recursive的低版本兼容写法我在这里补充一下：

$res = array();
function merge($item, $key) {
    global $res;
    $res[] = $item
}
array_walk_recursive($arr, 'merge');

至于修改后的代码的效率测试我就不在这里多做了，相比最终得到的结果应该也是一样的。

Answer 2

本来要踩一下 @怡红公子 的答案的，结果发现自己声望不够，好吧，只好默默的答题了。。

其实认真分析一下 @怡红公子 答案里的那个benchmark表就看出来了，明显1号方案和3号方案的算法复杂度是O(mn^2)，而2号方案的复杂度只有O(mn)。其中，m为哈希表内每个列表的长度，n为哈希表的长度。

是什么导致了这样的差距呢？再仔细看一眼代码，就会发现1号方案和3号方案同时出现了一个函数array_merge。这货到底做了什么呢？

其实每次array_merge操作都会把参数里的两个array合并，并且生成一个新的array并为其分配内存。这个操作的复杂度为O(mn)，而$res[] = $item这样一个往array里append的复杂度只有O(1)，累积起来只有O(m)。所以benchmark的结果就可以理解了。

最后大家可以试试下面这段代码：

$res = [];
foreach ($arr as $item) {
    foreach ($item as $value) {
        $res[] = $item;
    }
}

理论上是一定比array_walk_recursive，具体我没怎么测，你们可以试试。

PS:array_walk系列函数(包括array_walk array_map array_filter ……)我印象里都是比foreach要慢的，至少在php5.4.6上我实测如此。欢迎大家拍砖。

Answer 3

call_user_func_array('array_merge', $array);