比较器工作方式的效率

一尘不染

比较器工作方式的效率

javascript

我正在尝试使用比较器来帮助对对象列表进行排序。在以下示例中，我对比较器的工作原理以及确切的工作方式有疑问：

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

从上面可以看到，有必要根据complexOperation()方法返回的整数排名对学生进行比较和排序。顾名思义，这是一项繁重的操作。以上方法会是最有效的吗？或者基本上遍历我要排序的列表中的complexOperation()每个学生，执行每个学生，然后将结果存储在Student对象的字段中会更好。然后，比较器将执行以下操作：

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

这两种方法是否具有可比性，或者由于比较器的工作方式（可能将同一对象与其他对象进行多次比较，因此在比较期间每个Student多次运行complexOperation（）），会更快地进行complexOperation（）导致学生领域？

上面将这样称呼：

Collections.sort(students, comparator());

希望那是清楚的！

编辑：可以说，就此而言，不可能将字段添加到Student对象中（对于更复杂的情况，这是一个玩具问题，在这种情况下，我无权修改Student对象。）也许最好创建一个自定义对象，让Student坐在里面并添加另一个字段，而不是在比较器中直接进行complexOperation（）？还是有解决该问题的另一种方法？我可以考虑创建一个将学生ID作为键并将complexOperation（）的结果作为值的Hashmap，然后在比较器中创建/访问该记录吗？

阅读 301

2020-09-29

共1个答案

一尘不染

平均而言，您的排序算法将针对N个学生的数组调用complexOperation()大约2 N次日志的方法。如果操作真的很慢，最好为每个学生运行一次。这可以为1000名学生带来数量级的提高。

但是，您不必显式地执行此操作：您可以complexOperation(...)存储每个学生的结果，然后在后续请求中返回缓存的值：

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;
}

请注意，为了使这种方法起作用，Student类需要实现hashCode和equals。

2020-09-29