How to efficiently compute the maximum value of a collection after applying some function

Question

Suppose you have a method like this that computes the maximum of a Collection for some ToIntFunction:

static <T> void foo1(Collection<? extends T> collection, ToIntFunction<? super T> function) {
    if (collection.isEmpty())
        throw new NoSuchElementException();
    int max = Integer.MIN_VALUE;
    T maxT = null;
    for (T t : collection) {
        int result = function.applyAsInt(t);
        if (result >= max) {
            max = result;
            maxT = t;
        }
    }
    // do something with maxT
}

With Java 8, this could be translated into

static <T> void foo2(Collection<? extends T> collection, ToIntFunction<? super T> function) {
    T maxT = collection.stream()
                       .max(Comparator.comparingInt(function))
                       .get();
    // do something with maxT
}

A disadvantage with the new version is that function.applyAsInt is invoked repeatedly for the same value of T. (Specifically if the collection has size n, foo1 invokes applyAsInt n times whereas foo2 invokes it 2n - 2 times).

Disadvantages of the first approach are that the code is less clear and you can't modify it to use parallelism.

Suppose you wanted to do this using parallel streams and only invoke applyAsInt once per element. Can this be written in a simple way?

Answer 1

You can use a custom collector that keeps running pair of the maximum value and the maximum element:

static <T> void foo3(Collection<? extends T> collection, ToIntFunction<? super T> function) {
    class Pair {
        int max = Integer.MIN_VALUE;
        T maxT = null;
    }
    T maxT = collection.stream().collect(Collector.of(
        Pair::new,
        (p, t) -> {
            int result = function.applyAsInt(t);
            if (result >= p.max) {
                p.max = result;
                p.maxT = t;
            }
        }, 
        (p1, p2) -> p2.max > p1.max ? p2 : p1,
        p -> p.maxT
    ));
    // do something with maxT
}

One advantage is that this creates a single Pair intermediate object that is used through-out the collecting process. Each time an element is accepted, this holder is updated with the new maximum. The finisher operation just returns the maximum element and disgards the maximum value.