Efficiency of the way comparator works

Question

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

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

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?

The above would be called like so:

Collections.sort(students, comparator());

Hope that was clear!

Edit: 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?

Answer 1

Basically, you want to compare students by comparing some values that each maps to. This is usually done by

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

However, since the function complexOperation is too expensive, we want to cache its results. We can have a general purpose utility method Function cache(Function)

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

In general, it is better that the caller can supply a Map as the cache

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

We can use IdentityHashMap as the default cache

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