从PHP数组递归计算值的方法？

Question

This question is somewhat related to hierarchial data but I already have a stored procedure from my database which is returning the data mentioned below. I am not trying to find out how to build a hierarchy (done), I am trying to figure the best way to calculate numbers based on that hierarchy with PHP (perhaps recursive arrays?).

Using a custom stored procedure, I am able to pull a list of sales representatives for our company, the products they sold and the "earn" percentage for each one of those products on new rows and their subsequent sales reps (if in a tree).

An Example of the data returned can be as follows:

Repnum | Name | productID | sales | earn | depth | parentRep
------------------------------------------------------------
1      |   A  |   1       | 5000  | 0.50 |  1    | 0
1      |   A  |   2       | 10000 | 0.35 |  1    | 0  
2      |   B  |   1       | 400   | 0.40 |  2    | 1
2      |   B  |   2       | 1000  | 0.30 |  2    | 1
7      |   E  |   1       | 30000 | 0.35 |  3    | 2
3      |   C  |   1       | 5000  | 0.33 |  2    | 1

It is safe to assume that the order of the data returned is already formatted and sorted appropriately based on the depth and information not presented here. In a Tree view, the data above would look like this:

1-A-1-5000-0.50-1-0
1-A-2-10000-0.35-1-0
   2-B-1-400-0.40-2-1
   2-B-2-1000-0.30-2-1
      7-E-1-30000-0.35-3-2
   3-C-1-5000-0.33-2-1

In my while(results) loop, I am trying to calculate the following for EACH repnum returned:

• The total of that rep num's sales multipled by the earn % for each product (their total sales and earn amounts)
• The total amount of sales for each downline tree multiplied by the difference between the current rep and the level below it

To show the math for how this would work:

Rep 1 Earnings:

Rep 1 total sales = 5000 + 10000 = 15,000
Rep 1 earn on self = (5000 * 0.50) + (10000 * 0.35) = 6,000 hello!

Rep 2 total sales = 400 + 1000 = 1400
Rep 1 earn on rep 2 sales = (400 * (0.50-0.40) + (1000 * (.35-0.30)) = 90

Rep 7 total sales = 30000
Rep 1 earn on rep 7 sales = (30000 * (0.50-0.40)) = 3000*
(* the reason the earn is calculated at rep 1 earn - rep 2 earn is because in any tree, the "parent" can only ever earn the difference of his/her earn and the direct depth below him/her)

Rep 3 total sales = 5000
Rep 1 earn on rep 3 sales = (5000 * (0.50-0.33)) = 850

**Rep 1 TOTAL earn = 6,000 + 90 + 3000 + 850 = 9,940**

---

Rep 2 Earnings:

Rep 2 total sales = 400 + 1000 = 1400
Rep 2 total earn on self = (400 * 0.40) + (1000 * 0.30) = 460

Rep 7 total sales = 30000
Rep 2 total earn on rep 7 sales = (30000 * (0.40-0.35)) = 1500*
(* here, rep 2 earns the difference between him/her and rep 7 because he is in the depth right above it / his/her parent)

**Rep 2 TOTAL earn = 460 + 1500 = 1,960**

... and so on

---

I could have built the script to use HEAVY mysql recursion and simply done a hefty number of while() loops for each depth but found it unnecessary and taxing on a system given the stored procedure I use to go ahead and pre-calculate the hierarchy and depth and sort the data appropriately. Calculating the top level rep is simple enough but to then go back from the 2nd person on the list (and so on) and start again is where I am struggling some.

I would like to be able to return an output similar to the following based on the sample data above:

num | Name | earnAmount
------------------------
1   |  A   | 9940
2   |  B   | 1960
7   |  E   | 10500
3   |  C   | 1650

Thank you ahead of time for any help!

Notes on questions that have been asked:

Q: How are earn % calculated?

A: They aren't calculated, they are determined by the rep the particular productID that rep is selling.

---

Q: How are you determining "levels" or parent/child relationships?

A: I am not in this example. This piece of the equation is taken care of through a MySQL stored procedure and in a lot of ways not relevant (I could also display the parent repnum for each rep but since the array is built from the top down, it likely is not too helpful). The depth and sort order of the example data in the first table is already formatted and laid out in a way such that each tree could be printed by a simple print(results_array) statement in PHP.

---

Q: What is the relevance of productID in the first table?

A: Each rep can sell any product available in our system (hundreds), classified by a productID. Each rep also earns a percentage of each sell for that specific product. The earn % is completely unrelated to a specific product type (though there are max and min earns for each product) or a particular depth (though a rep on a higher depth never has a lower earn % for a specific productID than his downline tree).

---

Q: How is your data sorted in the first table?

A: Somewhat irrelevant (just trust me) but behind the scenes I create a breadcrumb column which takes the current repnum, then appends children and sorts based on a combination of it and the depth of the tree at that point. Example as given:

0 (invisible parent which selects ALL sales reps)
  0-1
    0-1-2
      0-1-2-7
    0-1-3
...

---

Answer 1

Here is my approach.
I assumed that the array can be one-dimensional. depth is just enough to let us determine if a Rep has "children". So the array looks like that:

$reps = array(
    array("rep" => "1", "name" => "A", "productId" => "1", "sales" => 5000, "earn" => 0.50, "depth" => "1"),
    array("rep" => "1", "name" => "A", "productId" => "2", "sales" => 10000, "earn" => 0.35, "depth" => "1"),
    array("rep" => "2", "name" => "B", "productId" => "1", "sales" => 400, "earn" => 0.40, "depth" => "2"),
    array("rep" => "2", "name" => "B", "productId" => "2", "sales" => 1000, "earn" => 0.30, "depth" => "2"),
    array("rep" => "7", "name" => "E", "productId" => "1", "sales" => 30000, "earn" => 0.35, "depth" => "3"),
    array("rep" => "3", "name" => "C", "productId" => "1", "sales" => 5000, "earn" => 0.33, "depth" => "2")
);

I decided to take a recursive approach. We loop through the array in the earn() function, advancing the array pointer after each iteration. Inside the function we iterate again in a for loop starting from the current + 1 array element to the end to find the Rep's "children". The code looks like that:

function earn() {
    global $reps, $earns;
    $rep = current($reps);
    $key = key($reps);
    $immediateChildEarn = null;

    //basic Rep's earnings
    $earn = $rep['sales'] * $rep['earn'];

    //loop to find children with the same productId
    for ($i = $key + 1; $i < count($reps); $i++) {
        $child = $reps[$i];

        //we're only interested in Reps with the same product and deeper position
        if ($rep['productId'] !== $child['productId'] || $rep['depth'] >= $child['depth']) {
            continue;
        }

        //collect the earn of the immediate child
        if (null === $immediateChildEarn) {
            $immediateChildEarn = $child['earn'];
        }

        //the earn difference can't be greater than the difference between Rep and its first immediate child Rep
        if ($immediateChildEarn > $child['earn'] && $rep['depth'] + 1 < $child['depth']) {
            $child['earn'] = $immediateChildEarn;
        }

        //calculate the earnings gained from this child
        $earn += $child['sales'] * ($rep['earn'] - $child['earn']);
    }

    //just a quick fix to prevent throwing Notices - not significant for the algorithm itself
    if (!isset($earns[$rep['rep']])) {
        $earns[$rep['rep']] = 0;
    }

    $earns[$rep['rep']] += $earn;

    $finish = next($reps);
    if (false !== $finish) {
        earn();
    }
}

$earns = array();
reset($reps);
earn();

The results of var_dump($earns) will be:

Array
(
    [1] => 9940
    [2] => 1960
    [7] => 10500
    [3] => 1650
)

Please, feel free to comment my answer. I'll try to repair any mistakes and improve the code the best I can.

Complexity:
I'm not good at calculating complexity of an algorithm but in my solution the complexity would be I think:

1. time complexity
   • worst-case O(n logn)
   • best-case O(2n)
2. memory complexity (not including input array)
   • worst-case O(n)
   • best-case O(1)

If I'm wrong, please feel free to correct me.