比较器工作方式的效率 [英] Efficiency of the way comparator works

查看:101
本文介绍了比较器工作方式的效率的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在尝试使用比较器来帮助对对象列表进行排序。我有一个问题,关于比较器的确切工作原理以及它在以下示例中的作用:

I am trying to use a comparator to help sort a list of objects. I have a question about how exactly the comparator works and what it would be doing exactly in the following example:

private static Comparator<Student> comparator()
{
        return (Student a, Student b) ->
        {  
                return Integer.compare(complexOperation(a), complexOperation(b));
        }
}

如上所示,有必要根据 complexOperation()方法返回的整数排名对学生进行比较和排序。顾名思义,这是一项繁重的操作。上述方法是否最有效?或者最好基本上遍历我正在尝试排序的列表中的每个学生,对每个学生执行 complexOperation()并将结果存储在学生的字段中宾语。然后比较器只会执行:

As you can see above, there is a need to compare and sort students according to an integer rank returned by the complexOperation() method. As the name suggests, it is a heavy operation. Would the above approach be the most efficient? Or would it be better to essentially run through each student in the list I am trying to sort, perform the complexOperation() per student and store the result in a field in the Student object. Then the comparator would just do an:

Integer.compare(a.getRank(), b.getRank())

这两种方法是否具有可比性,或者由于比较器的工作方式(可能比同一个对象更多)一次与其他人一起因此在比较期间每个学生多次运行complexOperation()),在学生字段中预先计算complexOperation()结果会更快吗?

Would both these approaches be comparable or, due to the way the comparator works (perhaps compares the same object more than once with others hence running complexOperation() multiple times per Student during the compare), would it be faster to do the pre computation of the complexOperation() result in a student field?

上面会这样调用:

Collections.sort(students, comparator());

希望很清楚!

编辑:
可以说,为了它,不可能在Student对象中添加一个字段(对于更复杂的情况,这是一个玩具问题,我无法修改Student对象)。是否仍然可以更好地创建一个自定义对象,其中学生坐在里面添加另一个字段而不是在比较器中执行complexOperation()?或者还有另一种解决问题的方法吗?我可以考虑创建一个Hashmap,它将student id作为键,并将complexOperation()的结果作为值,并在比较器中创建/访问该记录?

Lets say, for the sake of it, it is not possible to add a field to the Student object (This is a toy problem for a more complex situation where I am not at liberty to modify the Student object). Would it still be better to perhaps create a custom Object with Student sitting inside with another field added rather than doing the complexOperation() right in the comparator? Or is there another way to approach the problem? I can think of creating a Hashmap that takes student id as key and the result of the complexOperation() as value and just creates/access that record within the comparator?

推荐答案

平均而言,排序算法将调用 complexOperation()方法关于log 2 N次为一个数组N名学生。如果操作非常慢,那么每个学生最好再运行一次。这可以为1,000名学生提供一个数量级的改进。

On average, your sort algorithm will call complexOperation() method about log2N times for an array of N students. If the operation is really slow, you may be better off running it once for each student. This could bring an order of magnitude improvement for an array of 1,000 students.

然而,你不必明确地做:你可以做 complexOperation(...)存储每个学生的结果,然后在后续请求中返回缓存值:

However, you do not have to do it explicitly: you could make complexOperation(...) store the result for each student, and then return the cached value on subsequent requests:

private Map<Student,Integer> cache = new HashMap<Student,Integer>();

private int complexOperation(Student s) {
    // See if we computed the rank of the student before
    Integer res = cache.get(s);
    if (res != null) {
        // We did! Just return the stored result:
        return res.intValue();
    }
    ... // do the real computation here
    // Save the result for future invocations
    cache.put(s, result);
    return result;
}

请注意,为了使这种方法有效,学生类需要实现 hashCode 等于

Note that in order for this approach to work, Student class needs to implement hashCode and equals.

这篇关于比较器工作方式的效率的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆