Maximum of list with expensive custom key function

Question

In Java to find the maximum element of a sequence you write:

GameState bestGs = Collections.max(ns,
        Comparator.comparing(e -> minimax(e)));

Here minimax is a function returning a number and ns is a collection. The code works, but the key function will be evaluated more than once for each element of the collection. How do I make it so that it is evaluated only once per element? In Python you would just write max(seq, key = lambda e: minimax(e))There must be something similar in Java? Don't tell me to write the forloop myself, it is the 21st century I shouldn't have to!

The explicit looping code goes like this:

GameState best = null;
// Doesn't matter what scalar type is used.
int bestScore = Integer.MIN_VALUE;  
for (GameState n : ns) {
    int thisScore = minimax(n);
    if (thisScore > bestScore) {
        bestScore = thisScore;
        best = n;
    }
}

I want to write the above in a "functional" way in Java but also retain the high performance.

Answer 1

You could memoize the e -> minimax(e) function:

public static <T, S> Function<T, S> memoize(Function<T, S> function) {
    Map<T, S> cache = new HashMap<>();
    return argument -> cache.computeIfAbsent(argument, function);
}

Then, simply use the memoized function:

GameState bestGs = Collections.max(ns,
    Comparator.comparing(memoize(e -> minimax(e))));

---

EDIT: This approach requires that GameState implements hashCode and equals consistently. These methods should also run very fast (which is the usual case).

---

EDIT 2: As M. Justin tells in the comments below, this solution is not thread-safe. If you are to use the memoized function from more than one thread, you should use a ConcurrentHashMap instead of a HashMap.