比较器工作方式的效率

Question

我正在尝试使用比较器来帮助对对象列表进行排序。我有一个关于比较器究竟是如何工作的以及它在下面的例子中会做什么的问题：

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())

这两种方法是否具有可比性，或者由于比较器的工作方式（可能将同一个对象与其他对象进行多次比较，因此运行在比较期间每个学生多次使用 complexOperation()），在学生领域对 complexOperation() 结果进行预计算会更快吗？

上面会这样调用：

Collections.sort(students, comparator());

希望已经清楚了！

编辑：可以说，为此，不可能向 Student 对象添加一个字段（对于更复杂的情况，我不能随意修改 Student 对象，这是一个玩具问题）。也许创建一个自定义对象，让 Student 坐在里面并添加另一个字段，而不是在比较器中直接执行 complexOperation() 会更好吗？还是有另一种方法来解决这个问题？我可以考虑创建一个 Hashmap，它将学生 ID 作为键，将 complexOperation() 的结果作为值，并且只是 creates/access 比较器中的记录？

Answer 1

平均而言，您的排序算法将为 N 个学生的数组调用 complexOperation() 方法 log₂N 次。如果操作真的很慢，你最好运行每个学生一次。这可以为 1,000 名学生的阵列带来一个数量级的改进。

但是，您不必明确地这样做：您可以 complexOperation(...) 存储每个学生的结果，然后 return 在后续请求中缓存值：

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 class 需要实施 hashCode 和 equals。

Answer 2

基本上，您想通过比较每个映射到的一些值来比较学生。这通常由

完成

    static Comparator<Student> comparator()
    {
        return Comparator.comparing( Foo::complexOperation );
    }

但是，由于函数 complexOperation 太昂贵了，我们想缓存它的结果。我们可以有一个通用的实用方法 Function cache(Function)

    static Comparator<Student> comparator()
    {
        return Comparator.comparing( cache(Foo::complexOperation) );
    }

一般来说，调用者最好能提供一个Map作为缓存

public static <K,V> Function<K,V> cache(Function<K,V> f, Map<K,V> cache)
{
    return k->cache.computeIfAbsent(k, f);
}

我们可以使用IdentityHashMap作为默认缓存

public static <K,V> Function<K,V> cache(Function<K,V> f)
{
    return cache(f, new IdentityHashMap<>());
}

比较器工作方式的效率

Efficiency of the way comparator works

java

sorting

performance

comparator