dongle7882 2013-10-17 19:38
浏览 43
已采纳

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

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
...

  • 写回答

1条回答 默认 最新

  • dousong5161 2013-10-17 21:21
    关注

    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.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥35 平滑拟合曲线该如何生成
  • ¥100 c语言,请帮蒟蒻写一个题的范例作参考
  • ¥15 名为“Product”的列已属于此 DataTable
  • ¥15 安卓adb backup备份应用数据失败
  • ¥15 eclipse运行项目时遇到的问题
  • ¥15 关于#c##的问题:最近需要用CAT工具Trados进行一些开发
  • ¥15 南大pa1 小游戏没有界面,并且报了如下错误,尝试过换显卡驱动,但是好像不行
  • ¥15 自己瞎改改,结果现在又运行不了了
  • ¥15 链式存储应该如何解决
  • ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站