比较器工作方式的效率

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对象).是否仍然可以更好地创建一个自定义对象,其中学生坐在里面添加另一个字段而不是在比较器中执行complexOperation()？或者还有另一种解决问题的方法吗？我可以考虑创建一个Hashmap,它将student id作为键,并将complexOperation()的结果作为值,并在比较器中创建/访问该记录？

Answer 1

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

但是，您不必显式执行此操作：您可以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。

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