Re: [PHP] unset in foreach breaks recrusion



Hey,

Can't use your example, as you check weather
$sorted is empty, if it is -> run the foreach and return,
but on next recursion when it's not empty - do nothing :)

Though I found how to cut a few seconds (on very big array),
removing the first if, and adding a $return=true to functions'
parameters, and in future calls set it to false:

function recur($array, &$sorted=array(), $pid=0, $level=0, $return=true)
{
foreach($array as $id=>$parent)
{
if($pid===$parent)
{
$sorted[$id]= $level;
unset($array[$id]);
if(in_array($id,$array)){
recur($array, &$sorted, $id, $level+1, false);
}
}
}
if($return){return $sorted;}
}


Well, I guess that's it, I'm sure I can think of
another way to cut execution time, but, well,
I don't have much time for it :)


Thanks all!

David.


On Mon, Jun 30, 2008 at 8:24 AM, Roberto Costumero Moreno
<rcostu@xxxxxxxxx> wrote:
Hi David,

That's good work ;-)

You are right that my example would only return one entry for each parent.
Didn't realized of that.

I know the local copies you create in the recursive calls is not the best
solution in efficiency, but lots of times it is better to have local copies
of the array (in time of execution of the foreach) that the reference to it,
and the loss is not so big.

I think i would not be able to improve that function a lot, but if I come up
a solution I will tell you.

One little advice, you can get the same functionality saving a little bit of
code, and having one variable less, so the function should look like this
(avoiding the use of $return variable and makes the code clearer for later
revisions):

/**
* Recursion
* @array as ( id => parent )
* return array as ( id => level ) maintaining arrays' initial order
*/
function recur($array, &$sorted=array(), $pid=0, $level=0)
{
if(empty($sorted)){
foreach($array as $id=>$parent)
{
if($pid===$parent)
{
$sorted[$id]= $level;
unset($array[$id]);
if(in_array($id,$array)){
recur($array, &$sorted, $id, $level+1);
}
}
}
return $sorted;
}
}

Note that return $sorted is inside the if so as to avoid returning an empty
array. If you don't mind returning an empty array put it down the bracket.

And thanks to you. I signed up to the mailing list only two days ago
(although I've been working with PHP for at least 3 years), and you are the
first person I help successfully (or almost). Don't ever regret of asking
problems in the mailing list and always wait about 24 hours for someone to
answer ;-)

There are lots of people from all over the world so if the one helping your
case is in the opposite part of the world and is asleep... it takes time ;-)

Cheers,

Roberto




On Mon, Jun 30, 2008 at 17:38, David Sky <espaiz@xxxxxxxxx> wrote:

Hey Robero,

Thanks for the answer, the none recursion function is a good idea,
although as provided in your example if would only return one
entry from each parent it can get to and it only can get to few,
depends on how the array is sorted.

Basically you can make it work if you would sort the array from
small to high by parent value, but in my case I will get this array
pre-sorted by date, so I can't change the order.

Now, about your other suggestion, yes, it will work without the reference.
I used the reference to avoid creating "local" copies of the array.

I solved the problem by removing the reference just as you said, but then
there would be to many recursions, so I ended up with this function:

/**
* Recursion
* @array as ( id => parent )
* return array as ( id => level ) maintaining arrays' initial order
*/
function recur($array, &$sorted=array(), $pid=0, $level=0)
{
if(empty($sorted)){$return=true;}else{$return=false;}
foreach($array as $id=>$parent)
{
if($pid===$parent)
{
$sorted[$id]= $level;
unset($array[$id]);
if(in_array($id,$array)){
recur($array, &$sorted, $id, $level+1);
}
}
}
if($return){return $sorted;}
}

Checking with in_array if parent exist in array to make
less runs and saving micro seconds on return... haha.

I couldn't make it any faster, but if anybody can,
please, let me know, I would be happy to know how to.


Thanks Robero, this is first time I'm looking for help in mailing list,
and I was starting to regret writing here, but your reply changed it :)

Thanks!

David.



On Mon, Jun 30, 2008 at 6:36 AM, Roberto Costumero Moreno
<rcostu@xxxxxxxxx> wrote:
That's not the problem. Look that the function is called with &$return,
so
there is a reference to the variable in which the function returns the
value
(if not there would not be an answer...).

Otherwise, i think the problem is in the recursive call inside the
function.
Once you make the unset, you make a recursive call to the function like:

recrusion(&$array, &$return, $id, $level+1);

while I think the problem will be solved if you make the call just like:

recrusion($array, &$return, $id, $level+1);


Notice that the $array variable has not & symbol, so is the variable
itself
and not a reference of it.

Although there is a better and simple solution for that problem (or I
think
something like this should work well):


<?php
function recrusion($array, $return, $pid=0, $level=0){
foreach($array as $id=>$parent){
if( $parent===$pid ){
$return[$id]= $level;
unset($array[$id]); /* remove this to get correct
results */

$level++;
$pid = $id;
}
}
}
$return= array();
$array= array(1=>0,2=>1,3=>2,4=>3,5=>2,6=>2,7=>6,8=>6,9=>0,10=>0);
recrusion($array, &$return);

var_dump( $return );
?>

So you don't make any recursive call, you don't lose too much efficiency
and
it should work well for the whole array.

Try the two solutions above and see whether if any is up to your
problem.


Cheers,

Roberto


On Mon, Jun 30, 2008 at 14:27, Jason Norwood-Young
<jason@xxxxxxxxxxxxxxxxxxx> wrote:

On Sun, 2008-06-29 at 18:25 -0800, David Sky wrote:
Hello everyone!

A couple of days ago I submitted a bug to PHP
http://bugs.php.net/bug.php?id=45385
But I was mistaken, apparently it's not a bug.
And I was "sent" here to get help.

I think you might be forgetting to return $return.

J


--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php





.



Relevant Pages

  • Re: [PHP] unset in foreach breaks recrusion
    ... Thanks for the answer, the none recursion function is a good idea, ... Basically you can make it work if you would sort the array from ... small to high by parent value, but in my case I will get this array ... Now, about your other suggestion, yes, it will work without the reference. ...
    (php.general)
  • Re: [PHP] unset in foreach breaks recrusion
    ... but on next recursion when it's not empty - do nothing:) ... Though I found how to cut a few seconds (on very big array), ... (although I've been working with PHP for at least 3 years), ... entry from each parent it can get to and it only can get to few, ...
    (php.general)
  • Re: counting subsets of S so that sum(S_n) = N
    ... and make my algorithm generate only unique subsets? ... and the array of boolean at one step of the algorithm is ... implementation without needing recursion. ... subsequence in W, process it and return. ...
    (comp.programming)
  • Re: How to arrange some numbers
    ... competently implemented sort. ... If the array is already sorted, ... but perhaps you've analyzed a different algorithm. ... assume for the recursion step? ...
    (comp.lang.c)
  • Re: [PHP] unset in foreach breaks recrusion
    ... You are right that my example would only return one entry for each parent. ... of the array that the reference to it, ... (although I've been working with PHP for at least 3 years), ... Thanks for the answer, the none recursion function is a good idea, ...
    (php.general)