java - 为给定场景定义更有效的逻辑

Question

得到了一些有趣的逻辑，我正在尝试以最有效和可读的方式对其进行编码。我将在下面布置场景(使用模拟/虚拟上下文)

我有一个银行及其柜员评论的数据存储(1-5 整数字段)。出纳员可以选择有一个客户选择获胜者 (CCW) 字段。我的要求如下，为给定银行选择最多 5 个出纳员以显示给用户:

1. 如果出纳员是 CCW，请选择它。如果多个出纳员都有 CCW，请使用出纳员评论打破平局
2. 当没有 CCW 时，选择出纳员评价最高的 4 级出纳员。

我必须为 5 家银行执行上述操作。我得到的逻辑是有一个 for 循环遍历 5 家银行，在每个循环中，遍历每家银行的所有出纳员 5 次(选择 5 名出纳员)。在我看来，这确实效率低下且不清楚。这就是我的意思:

foreach (Bank b : banks) {
    List<Tellers> tellers = b.getTellers();

    foreach (Teller t : tellers) {
        List<Reviews> reviews = t.getReviews();

        ...// get 4 reviews following the above logic.
    }
}

谁能帮我写出更清晰、更有效的方法？

谢谢!

Answer 1

最好的解决方案是对 List 进行排序

您必须通过实现 Comparable 接口(interface)为 Teller 对象定义一个比较函数。

这将使您可以在恒定时间内运行算法(O(25)，因为 5 家银行有 5 个出纳员，这实际上是 O(1))

以第一次排序为代价，这将是 O(nlogn)

您的 Teller 类的示例代码:

public class Teller implements Comparable
{

    private boolean ccw = false;
    private int rating;

    public boolean hasCCW() { return ccw; }
    public int getRating() { return rating; }

    //... your code

    @Override
    public int compareTo(Object o) 
    {
        Teller that = (Teller)o;
        //if this has ccw and that doesn't, this < that
        if(this.hasCCW() && !that.hasCCW()) 
        {
            return -1;
        }
        //else if this does not have ccw, and that does, this > that
        else if(!this.hasCCW() && that.hasCCW())
        {
            return 1;
        }
        //else they both have ccw, so compare ratings
        else
        {
            return Integer.compare(this.getRating(), that.getRating());
        }
    }

}

然后，您的算法只需要为每家银行抓取前 5 位出纳员。

例子:

//Sort the tellers:
//ideally, call this only once, and insert future Tellers in order (to maintain ordering)
for(Bank bank : banks)
{
    for(List<Teller> tellers : bank.getTellers())
    {
        Collections.sort(tellers);
    }
}

//then, to get your top tellers:
for(Bank bank : banks)
{
    Teller bestTeller = bank.getTeller(0);
    Teller secondBestTeller = bank.getTeller(1);
    //...
}