function to group data by parent branches

Question

I wrote this function to take database output like from PDO's fetchAll(PDO::FETCH_ASSOC) and turn it into a tree. For small datasets it works well. However, when I run it on an array of 54,000 elements, it takes around 65 seconds on an Intel 7700K. I was hoping it would take less than a second, though maybe that's unrealistic. I'm using PHP 8.1.8.

Why is this function so slow?

Is there a way to optimize this function?

<?php
function treeifyDbRows($inputArray, $branchRules)
{
    $output = [];
    if ($branchRules != [])
    {
        $ruleSet = $branchRules[0];
        $masterRule = $ruleSet[0];
        $branchParents = array_column($inputArray, $masterRule);
        $branchParents = array_unique($branchParents);
        foreach ($branchParents as $branchParent)
        {
            $branchRulesAgain = [];
            foreach ($branchRules as $ruleSetAgain)
            {
                if ($ruleSetAgain != $ruleSet)
                {
                    $branchRulesAgain[] = $ruleSetAgain;
                }
            }
            $branch = [];
            $branchChildren = array_filter($inputArray, function($e) use ($branchParent, $masterRule){return $e[$masterRule] == $branchParent;});
            $branchChildren = array_values($branchChildren);
            foreach ($ruleSet as $rule)
            {
                $branch[$rule] = $branchChildren[0][$rule];
            }
            $children = treeifyDbRows($branchChildren, $branchRulesAgain);
            if ($children != [])
            {
                $branch['children'] = $children;
            }
            $output[] = $branch;
        }
    }
    return $output;
}

$data =
[
    [
        "countryID" => 1,
        "countryName" => "USA",
        "regionID" => 10,
        "regionName" => "Indiana",
        "cityID" => 100,
        "cityName"=> "Indianapolis",
    ],
    [
        "countryID" => 1,
        "countryName" => "USA",
        "regionID" => 10,
        "regionName" => "Indiana",
        "cityID" => 101,
        "cityName"=> "Bloomington",
    ],
    [
        "countryID" => 1,
        "countryName" => "USA",
        "regionID" => 11,
        "regionName" => "Michigan",
        "cityID" => 102,
        "cityName"=> "Lansing",
    ],
    [
        "countryID" => 2,
        "countryName" => "Canada",
        "regionID" => 12,
        "regionName" => "Ontario",
        "cityID" => 103,
        "cityName"=> "Toronto",
    ],
    [
        "countryID" => 2,
        "countryName" => "Canada",
        "regionID" => 12,
        "regionName" => "Ontario",
        "cityID" => 104,
        "cityName"=> "Ottawa",
    ],
    [
        "countryID" => 2,
        "countryName" => "Canada",
        "regionID" => 12,
        "regionName" => "Ontario",
        "cityID" => 105,
        "cityName"=> "Windsor",
    ],
    [
        "countryID" => 2,
        "countryName" => "Canada",
        "regionID" => 25,
        "regionName" => "Quebec",
        "cityID" => 106,
        "cityName"=> "Montreal",
    ],
];

$rules =
[
    ["countryID", "countryName"],
    ["regionID", "regionName"],
    ["cityID", "cityName"],
];
$results = treeifyDbRows($data, $rules);
var_dump($results);

Answer 1

Initial review points

Before addressing the questions I have a few review thoughts:

• The code is readable and indentation seems consistent

• Type declarations can be added for the function arguments to ensure the data passed is in the expected format, and the return type for the function can also be added:

  function treeifyDbRows(array $inputArray, array $branchRules): array
  

• The one-line callback function passed to array_filter() can be simplified using the arrow function syntax, allowing for the elimination of the use statement.

• Using array_shift() to assign $ruleset from $branchRules by shifting it off the beginning of the array allows for the elimination of $branchRulesAgain and the loop to create it as the recursive call can then just use $branchRules

• It is a good habit to use strict equality operators - e.g. === instead of == - whenever possible, especially given the values that are juggled to be equal to false.

• While it may be common for idiomatic code in some languages to have opening braces on a new line for control expressions like if and for this is not the case with PHP. There are PHP Standards Recommendations followed by many PHP developers and PSR-12 section 5 covers Control Structures covers Control Structures:

  The general style rules for control structures are as follows:

  • There MUST be one space after the control structure keyword
  • There MUST NOT be a space after the opening parenthesis
  • There MUST NOT be a space before the closing parenthesis
  • There MUST be one space between the closing parenthesis and the opening brace
  • The structure body MUST be indented once
  • The body MUST be on the next line after the opening brace
  • The closing brace MUST be on the next line after the body

  The body of each structure MUST be enclosed by braces. This standardizes how the structures look and reduces the likelihood of introducing errors as new lines get added to the body.

• Because PHP converts values to Boolean automatically when necessary the conditions to check if an array has elements can be simplified - e.g. from if ($branchRules != []) to simply if ($branchRules). When converted to a bool an array with no elements is converted to false.

Addressing the Questions

Why is this function so slow?

Let’s look at what the function does- there is a foreach loop iterating over the rules, and inside that loop is a call to array_column() which iterates over the input array to get the "branch parents". Then there is a loop over the branch parents which inside contains a call to array_filter(), which again iterates over the input array. While it may be highly unlikely, it is possible that all branch parents are unique (in which case grouping may be superfluous) and in such a case for an input array with size \$n\$ it would require \$n^2\$ steps, which would be considered the worst case. In terms of time complexity this is considered to be of the order of \$O(n^2)\$. Additionally, the function recursively calls itself in order to add the child elements, which leads to even more looping!

When running the function with an array containing 54,000 elements there could be as many as 2,916,000,000 steps just to get the first level of output!

Is there a way to optimize this function?

Ideally the input data would be sorted (which is why I asked in a comment if this is possible) and there could be a single loop to:

• find branch parents
• add branch children to a filtered array that can then be used in the recursive call

If there is no guarantee that the data will be sorted then mapping the parents and children in an associative array may be necessary, which would increase the spacial complexity.

Also, the loop to add elements to $branchRulesAgain does not need to happen within the nested loop (over $branchParents) as it is not specific to the branch parent.

Proposed solution

The code below presumes the data is already sorted and only iterates over the inputArray once per rule/group level. It uses null coalescing to handle the case of the last element in the array - in that case there won’t be a next element so the ?? 0 makes 0 the fallback value. See a demo of it here on 3v4l.org.

<?php
function treeifyDbRows(array $inputArray, array $branchRules): array
{
    $output = [];
    if ($branchRules) {
        $ruleSet = array_shift($branchRules);
        $masterRule = $ruleSet[0];
        $branchChildren = [];
        foreach ($inputArray as $index => $element) {
            $branchChildren[] = $element;
            //coalesce null to 0
            if (($inputArray[$index + 1][$masterRule] ?? 0) !== $element[$masterRule]) {
                $branch = [];
                foreach ($ruleSet as $rule) {
                    $branch[$rule] = $branchChildren[0][$rule];
                }
                $children = treeifyDbRows($branchChildren, $branchRules);
                if ($children) {
                    $branch['children'] = $children;
                }
                $output[] = $branch;
                $branchChildren = [];
            }
            
        }
    }
    return $output;
}