Максимум списка с дорогой пользовательской ключевой функцией

Question

В Java для поиска максимального элемента последовательности, которую вы пишете:

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

Здесь minimax - это функция, возвращающая число, а ns - это коллекция.Код работает, но ключевая функция будет оцениваться более одного раза для каждого элемента коллекции.Как мне сделать так, чтобы он оценивался только один раз для каждого элемента?В Python вы просто пишете max(seq, key = lambda e: minimax(e)) Должно быть что-то подобное в Java?Не говорите мне, чтобы я написал forloop сам, это 21-й век, который мне не нужно было!

Явный код зацикливания выглядит так:

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

Я хочу написатьвышеупомянутое "функционально" в Java, но также сохраняет высокую производительность.

Answer 1

Вы можете запомнить функцию e -> minimax(e):

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

Затем просто используйте запомненную функцию:

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

---

РЕДАКТИРОВАТЬ: Этот подход требует, чтобы GameState последовательно hashCode и equals последовательно .Эти методы также должны работать очень быстро (что является обычным случаем).

Answer 2

import java.util.ArrayList;
import java.util.List;

import static java.lang.Integer.MIN_VALUE;
import static java.util.AbstractMap.SimpleEntry;

...

var bestEntry = ns.stream()
                  .map(i -> new SimpleEntry<>(i, minimax(i)))
                  .max(Map.Entry.comparingByValue())
                  .orElse(new SimpleEntry<>(null, MIN_VALUE));

var bestGameState = bestEntry.getKey();
var bestScore = bestEntry.getValue();

После уменьшения вы получите Optional<Pair<GameState, Integer>>, который может содержать самый высокий результат minimax и соответствующий GameState.Если игровых состояний нет, мы возвращаем запись по умолчанию new SimpleEntry<>(null, MIN_VALUE).

Answer 3

Хорошо, как насчет первого вычисления minimax для каждого первого ключа, сохранить его в TreeMap и просто получить последнюю запись после вычисления?конечно вы платите за дополнительное хранение.

int max = col.stream()
            .collect(Collectors.collectingAndThen(
                    Collectors.toMap(
                            e -> minimax(e),
                            Function.identity(),
                            (left, right) -> left,
                            TreeMap::new
                    ),
                    m -> m.lastEntry().getValue()));

Это может быть сделано даже менее многословно:

// Integer, Integer for simplicity
TreeMap<Integer, Integer> tm = new TreeMap<>();
col.forEach(x-> { 
            tm.putIfAbsent(minimax(x), x); 
            if(tm.size() > 1) {
                tm.remove(tm.firstKey()); 
            }
});
int max = m.lastEntry().getValue();

Answer 4

GameState max = ns.stream()
                 .collect(Collectors.toMap(str -> minimax(str), Function.identity(), (gs1, gs2) -> gs1,
                         (Supplier<Map<Integer, GameState>>)() -> new TreeMap<>(Comparator.reverseOrder())
                 )).values().iterator().next();