高效排名算法（PHP）

问题描述：

I have a PHP array (retrieved from a DB) of employees calculated data. There are about 10 columns per employee, 8 of them numerical (the other 2 are id and name). Here's a short sample:

David: 1024, 75,  22  
Mike:  500,  100, 25  
Jeff:  700,  82,  10

I can easily sort the array on any of the (numerical) fields to show who's at the top/bottom, but what I'd really like to show in the final table view is ranking by the value, so people won't have to sort and re-sort the table to get what they want. Here's an example of the table sorted by the first column, showing rankings in parentheses:

David: 1024 (#1), 75  (#3), 22 (#2)  
Jeff:  700  (#2), 82  (#2), 10 (#3)  
Mike:  500  (#3), 100 (#1), 25 (#1)

Now, I know the easiest approach is just to sort the table by column, use the row indexes as the ranking and repeat per every column. I just wondered if I could find a more efficient way.

I thought about using ordered queues (one per column that needs ranking), scanning the array once and pushing values into the queues. But:

PHP does not have any data structures other than arrays (unless you use external additions)
I'm not convinced this is more efficient.

Could anyone please suggest the best approach, and/or confirm I should just re-sort the array several times?

Thanks for your time!

我有一个员工计算数据的PHP数组（从数据库中检索）。每个员工大约有10列，其中8个是数字（另外2个是id和name）。这是一个简短的样本： p>

David：1024,75,22 Mike：500,100,25 Jeff：700,82,10 pre>

我可以轻松地在任何（数字）字段上对数组进行排序，以显示谁在顶部/底部，但我最想在最终表视图中显示的是按值排名，所以人们赢了' 我必须对表进行排序和重新排序以获得他们想要的东西。以下是按第一列排序的表格示例，显示括号中的排名： p>

David：1024（＃1），75（＃3），22（＃2） Jeff ：700（＃2），82（＃2），10（＃3）麦克：500（＃3），100（＃1），25（＃1） pre>

现在，我知道最简单的方法是按列对表进行排序，使用行索引作为排名，并按每列重复。我只是想知道我是否能找到更有效的方法。 p>

我考虑使用有序队列（每列需要排名一个），扫描一次数组并将值推入队列。但是： p>

PHP除了数组之外没有任何数据结构（除非你使用外部添加） li>
我不相信这个效率更高。 li> ol>
有人可以建议最好的方法，和/或确认我应该多次重新排序数组吗？ p>

感谢您的时间！ p> div>

答

Ok, after much deliberation, I decided to go the "sort every column" route. For future reference by anyone interested, here's the function I've added to my class - it's called once per every column I need ranked:

   private function calculateRankings(&$employees, $columnName) {
        $comparer = "return (\$a[$columnName][0] == \$b[$columnName][0]) ? 0 :  (\$a[$columnName][0] > \$b[$columnName][0] ? -1 : 1);";
        usort($employees, create_function('$a,$b', $comparer));
        foreach($employees as $key => &$employee) {
            $employee[$columnName][1] = $key + 1;
        }
    }

The +1 is due to the keys being zero-based.

You prepare for this function by turning each field you need ranked into a 2-element array: the first ([0]) contains the value, and the second ([1]) will contain the rank in the end.
I.e.: $employees['salary'] = array(1550, 0);. You then call the function like this:
$this->calculateRankings($employees, 'salary');.

I sincerely hope this helps someone, someday. Thanks to all responders/commenters!

UPDATE 4/9: The function I supplied before couldn't work - there's no way to pass a third parameter (in our case, the column name) into the comparer function. The only way to do it is to use a static class variable, or a create_function hack that I ended up with. Sorry for any confusion.

答

I'm afraid you would have to stick with the initial approach.

There is no escape from having to iterate through all the columns and compute the ranking information for each individual one.

What you could do is optimize the algorithm to accomplish that task more efficiently.

PS.: I don't think that the algorithm is unusual enough for you to worry about complexity, order of growth or running time, even though performance is always important.

高效排名算法（PHP）

相关推荐