A Problem in Recursion

[iwato]

Background: Consider the following progression:array_fill(0, 1, $fill);array_fill(0, 2, array_fill(0, 2, $fill));array_fill(0, 3, array_fill(0, 3, array_fill(0, 3, $fill)));...array_fill(0, $num_of_elements, ... array_fill(0, $num_of_elements, $fill)) ...);Problem: I am trying to create a function that will generate the last line of the above progression for some arbitrarily selected $num_of_elements. I have tried everything imaginable and am exhausted.Any suggestions?Roddy

[boen_robot]

Have you looked at call_user_func_array()? Seeing as arrays can be of arbitrary length and be filled gradually with further call_user_func_array() calls, this seems like the way to go.

[iwato]

Have you looked at call_user_func_array()? Seeing as arrays can be of arbitrary length and be filled gradually with further call_user_func_array() calls, this seems like the way to go.

Are you suggesting a double-entry of the array_fill() function: once as the call_user_func_array() function's callback function, and once as the call_user_func_array()'s function parameter? Surely not.Recall, I want to be able to enter the value of $num_of_elements only once and from this value generate an array with the same number of dimensions.By way of example, the following expression

<?php	  $a = array_fill(0, 2, array_fill(0, 2, array_fill(0, 2, 1)));	  print_r($a);?>

produces the following output

Array(	[0] => Array		(			[0] => Array				(					[0] => 1					[1] => 1				)			[1] => Array				(					[0] => 1					[1] => 1				)		)	[1] => Array		(			[0] => Array				(					[0] => 1					[1] => 1				)			[1] => Array				(					[0] => 1					[1] => 1				)		))

In order to change the number of dimensions in the above array from three to four, one must add still another array_fill() function in the series.Three Dimensions: array_fill(0, 2, array_fill(0, 2, array_fill(0, 2, 1)));Four Dimensions: array_fill(0, 2, array_fill(0, 2, array_fill(0, 2, array_fill(0, 2, 1))));The challenge is to control the number of times that the array_fill() function appears in the series by a single parameter value.Roddy

[ShadowMage]

What about create_function?You could assemble a string based on the number of dimensions required using a loop. The string would be the code to execute, ie 'array_fill(0, $num_el, array_fill(0, $num_el, $fill))'

[boen_robot]

Here's a way I came up with some trial&error:

function array_fill_recursive($n, $fill) {	$baseArray = array_fill(0, $n, $fill);	$subArray = $baseArray;	for ($i=0; $i<$n; $i++) {		array_walk($subArray, function(&$value) use ($baseArray) {			$value = $baseArray;		});		$baseArray = $subArray;	}	return $baseArray;}

To generate the above example, you'd do:

array_fill_recursive(2, 1);

The basic idea is to fill the outer most level, and then walk over the array $n times, in each iteration filling each member with the array from the previous iteration.

[ShadowMage]

Clever. :)Out of curiosity I ran a couple benchmark tests pitting your version against mine. I found the results interesting. My version, which uses create_function, runs considerably faster, however, it is a major memory hog.At 50,000 iterations, filling an 8 dimension array:Your version:Total Time: 19.85 secondsMemory used: 448232 bytes (437.7 KB)My version:Total Time: 5.09 secondsMemory used: 175997680 bytes (167.8 MB):)Here's the code for my version:

function multi_array($n, $z, $fill=0) {	$code = 'return array_fill(0, '.$n.', ';	for ($x=1; $x<$z; $x++) {		$code.='array_fill(0, '.$n.', ';	}	$code.=$fill.')';	for ($x=1; $x<$z; $x++) {		$code.=')';	}	$code.=';';	// echo $code;	$func = create_function('', $code);	return $func();}

[boen_robot]

I realized a closure isn't really needed... here's an improved version using for:

function multi_array_lowmem_improved($n, $fill) {	$subArray = $baseArray = array_fill(0, $n, $fill);	for ($i = 0; $i < $n; ++$i) {		for($j = 0; $j < $n; ++$j) {			$subArray[$j] = $baseArray;		}		$baseArray = $subArray;	}	return $baseArray;}

My tests show that it executes 50000 iterations with multi_array_lowmem_improved(8,1) for ~3.2s... but I'll be curious as to what your tests show too .[edit]Another slight improvement. No need for the count() either. Changes in time and code reflected.[/edit]

[ShadowMage]

My tests show that it executes 50000 iterations with multi_array_lowmem_improved(8,1) for ~4s... but I'll be curious as to what your tests show too .

My tests show:Total Time: 3.88 secondsMemory used: 394696 bytes (385.4 KB)This is a much better version. :)EDIT: In response to your edit, boen:Total Time: 2.85 secondsMemory used: 394432 bytes (385.2 KB)

[iwato]

My tests show:Total Time: 3.88 secondsMemory used: 394696 bytes (385.4 KB)This is a much better version. :)EDIT: In response to your edit, boen:Total Time: 2.85 secondsMemory used: 394432 bytes (385.2 KB)

What can I say? Both you and boen-robot have found a way to circumvent the problem that I posed -- namely, create dynamically a function with a series of nested arguments of user_defined length.array_fill(0, 1, $fill);array_fill(0, 2, array_fill(0, 2, $fill));array_fill(0, 3, array_fill(0, 3, array_fill(0, 3, $fill)));array_fill(0, 4, array_fill(0, 4, array_fill(0, 4, (array_fill(0, 4, $fill))));array_fill(0, 5, array_fill(0, 5, array_fill(0, 5, (array_fill(0, 5, array_fill(0, 5, $fill)))));...Roddy

[iwato]

I realized a closure isn't really needed.No need for the count() either.

In search of elegance and a general formula to handle the nested functions I was able to come up with the following. It produces the desired matrix, but fails to fill properly.

<?php	function array_fill_recursive($start, $dimension, $fill) {		for ($i = 0; $i<$dimension; $i++) {			$array = array_fill($start, $dimension, $array);		}		return $array;	}?>

The following run produces a 3-dimensional array, but fills the final elements with null.Roddy

<?php	var_dump(array_fill_recursive(0, 3, 1));?>

[ShadowMage]

The following run produces a 3-dimensional array, but fills the final elements with null.

<?php	var_dump(array_fill_recursive(0, 3, 1));?>

That's because you never use the $fill variable. And the first time you run that, it is trying to use the $array variable as the fill value, but $array is not yet set.Try something like this:

function array_fill_recursive($start, $dimension, $fill) {	$array = array_fill($start, $dimension, $fill);	for ($i = 1; $i<$dimension; $i++) {		$array = array_fill($start, $dimension, $array);	}	return $array;}

You lose a bit of "elegance" again, but I think that's a sacrifice you're going to have to make.EDIT:Interestingly, you've built the fastest version yet. (With my suggested change, that is) Here's my benchmark results:Total Time: 1.92 secondsMemory used: 397384 bytes (388.1 KB)

[iwato]

You lose a bit of "elegance" again, but I think that's a sacrifice you're going to have to make.

OK, OK. No more complaint.

Interestingly, you've built the fastest version yet. (With my suggested change, that is) Here's my benchmark results:Total Time: 1.92 secondsMemory used: 397384 bytes (388.1 KB)

Teamwork is where it is at!Thanks to both you and boen_robot, we now have a general formula that is easy to remember for a large number of nested functions. I am very, very, happy!Roddy