Как эффективно вычислить максимальное значение коллекции после применения некоторой функции
Предположим, что у вас есть такой метод, который вычисляет максимум Collection для некоторого 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
}
С Java 8 это можно перевести в
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
}
Недостатком новой версии является то, что function.applyAsInt вызывается повторно для одного и того же значения T. (В частности, если коллекция имеет размер n, foo1 вызывает applyAsInt n раз, тогда как foo2 вызывает его 2n - 2 раз).
Недостатки первого подхода заключаются в том, что код менее ясен, и вы не можете его модифицировать для использования parallelism.
Предположим, вы хотели сделать это, используя параллельные потоки и только для вызова applyAsInt один раз для каждого элемента. Может ли это быть написано простым способом?
Ответы
Ответ 1
Вы можете использовать пользовательский коллекционер, который будет поддерживать пару максимального значения и максимального элемента:
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
}
Одно из преимуществ заключается в том, что это создает отдельный промежуточный объект Pair, который используется в процессе сбора данных. Каждый раз, когда элемент принимается, этот держатель обновляется с новым максимумом. Операция финишера возвращает максимальный элемент и отбрасывает максимальное значение.
Ответ 2
Как я уже говорил в комментариях, я предлагаю ввести промежуточную структуру данных, например:
static <T> void foo2(Collection<? extends T> collection, ToIntFunction<? super T> function) {
if (collection.isEmpty()) {
throw new IllegalArgumentException();
}
class Pair {
final T value;
final int result;
public Pair(T value, int result) {
this.value = value;
this.result = result;
}
public T getValue() {
return value;
}
public int getResult() {
return result;
}
}
T maxT = collection.stream().map(t -> new Pair(t, function.applyAsInt(t)))
.max(Comparator.comparingInt(Pair::getResult)).get().getValue();
// do something with maxT
}
Ответ 3
Другим способом было бы использовать memoized версию function:
static <T> void foo2(Collection<? extends T> collection,
ToIntFunction<? super T> function, T defaultValue) {
T maxT = collection.parallelStream()
.max(Comparator.comparingInt(ToIntMemoizer.memoize(function)))
.orElse(defaultValue);
// do something with maxT
}
Где ToIntMemoizer.memoize(function) код будет выглядеть следующим образом:
public class ToIntMemoizer<T> {
private final Map<T, Integer> cache = new ConcurrentHashMap<>();
private ToIntMemoizer() {
}
private ToIntFunction<T> doMemoize(ToIntFunction<T> function) {
return input -> cache.computeIfAbsent(input, function::apply);
}
public static <T> ToIntFunction<T> memoize(ToIntFunction<T> function) {
return new ToIntMemoizer<T>().doMemoize(function);
}
}
Это использует ConcurrentHashMap для кэширования уже вычисленных результатов. Если вам не нужно поддерживать parallelism, вы можете отлично использовать HashMap.
Одним из недостатков является то, что результат функции должен быть помещен в коробку/распакован. С другой стороны, поскольку функция запоминается, результат будет вычисляться только один раз для каждого повторяющегося элемента коллекции. Затем, если функция вызывается с повторным входным значением, результат будет возвращен из кеша.
Ответ 4
Если вы не возражаете против использования сторонней библиотеки, StreamEx оптимизирует все эти случаи в специальных методах, таких как maxByInt и так далее. Поэтому вы можете просто использовать:
static <T> void foo3(Collection<? extends T> collection, ToIntFunction<? super T> function) {
T maxT = StreamEx.of(collection).parallel()
.maxByInt(function)
.get();
// do something with maxT
}
В реализации используется reduce с изменяемым контейнером. Это, вероятно, немного нарушает API, но отлично работает для последовательных и параллельных потоков и в отличие от решения collect откладывает выделение контейнера на первый накопленный элемент (таким образом, никакой контейнер не выделяется, если параллельная подзадача не покрывает элементы, которые встречаются довольно часто, если у вас есть фильтрация вверх по течению).
