A recursive walk-through over a 10000 element array in PHP: Maximum function nesting level reached [duplicate]

Question

This question already has answers here:

Group 2d array's row data by one column and sum another column within each group to produce a 2d array with potentially fewer rows (3 answers)

Closed 1 year ago.

I have a sorted array of 2-element arrays like the following:

array(
 array('id' => 1734, 'count' => 14),
 array('id' => 1734, 'count' => 7),
 array('id' => 9374, 'count' => 5),
 array('id' => 9374, 'count' => 253)
);

The array is sorted on the 'id' field of the inner arrays. The goal is to reduce it to the following:

array(
 array('id' => 1734, 'count' => 21),
 array('id' => 9374', 'count' => 258)
);

I.e. to aggregate/summ over the 'count' element for every unique 'id'.

I go though the array in a function myfunc(array $arr){...} which does array_shift($arr) and then calls myfunc($arr). It also has an appropriate check for the base case of the recursion (an empty array) and should terminate at this point.

The thing is that I have tens of thousands of the inner arrays and PHP throws "PHP Fatal error: Uncaught Error: Maximum function nesting level of '256' reached, aborting!".

After carefully examining the code and running a debug session I saw that the $arr does really reduce it's size from call to call, so I think the problem does lie only on the maximum function nesting setting. However it seems for me that it is impractical to change this setting to something like 1 million. So, what other solution could we have here?

• Éder Rocha: Is this data coming from a database? May be you can do the operations at origin.

Answer 1

Unless it's a requirement, recursion is probably not the way to go here.

<?php
$arr = array(
 array('id' => 1734, 'count' => 14),
 array('id' => 1734, 'count' => 7),
 array('id' => 9374, 'count' => 5),
 array('id' => 9374, 'count' => 253)
);
$agg = array();
foreach ($arr as $v){
 if (isset($agg[$v['id']])){$agg[$v['id']] += $v['count'];}
 else {$agg[$v['id']] = $v['count'];}
}

You have to look at each element in $arr at least once anyways, and hash lookups (aka isset($v['id'])) is an O(1) operation. As Oliver's solution points out, you don't actually need to check if the key exists, you can just blindly += to that key.

• parttimeturtle: @ÉderRochaBezerra Database was a good question, you could cut off a lot of this work there.
• bestprogrammerintheworld: This solution does not exactly give what OP wants (if you look at OP's goal)

Answer 2

Use an iterative algorithm instead of a recursive one:

// add up the count for each id
$counts = [];
foreach ($arr as $row) {
 $counts[$row['id']] += $row['count'];
}
// format the counts as an array of records
$answer = [];
foreach ($counts as $id => $count) {
 $answer[] = ['id' => $id, 'count' => $count];
}

Note that recursive algorithms tend to exceed the capacity of the stack when used with large data sets, unless they are written in such a way that tail call optimization is used and assuming the language supports tail call optimization, which PHP currently does not.

Answer 3

This solution is based on that youur array is called $arr:

$new_arr = [];
foreach($arr as $item) {
 $key = $item['id'];
 $new_arr[$key]['id'] = $item['id'];
 isset($new_arr[$key]['count']) ? 
 $new_arr[$key]['count'] += $item['count'] : 
 $new_arr[$key]['count'] = $item['count'];
}
//This code would output your expected result. Without array_values you will 
//get the key values equals to your values of id
echo '<pre>';
print_r(array_values($new_arr));
echo '</pre>';

Answer 4

Thank you for the answers. One thing that I have obviously failed to mention is that I want the solution to be in functional style.

I have equivalently (in the terms of result) rewrote the algorithm to use array_reduce(). This allows me to stay in functional style and have the thing done.

Answer 5

It is simple to use just a read loop and add and create the new array at the same time. And in the end use an array_values​​() to recreate the sequential order of the parent array's key.

$arr = [
 ['id' => 1734, 'count' => 14],
 ['id' => 9388, 'count' => 25],
 ['id' => 1734, 'count' => 7],
 ['id' => 9374, 'count' => 5],
 ['id' => 9374, 'count' => 253]
];
$counts = [];
 
foreach($arr as $row)
{
 if(isset($counts[$row['id']])){
 $sum = $counts[$row['id']]["count"] + $row['count']];
 $counts[$row['id']] = [
 "id" => $row['id'],
 "count" => $sum
 ];
 }else{
 $counts[$row['id']] = [
 "id" => $row['id'],
 "count" => $row['count']
 ];
 }
} 
var_dump(array_values($counts));