Как получить список максимальных значений коллекции, используя Stream API

Рейтинг: 0Ответов: 2Опубликовано: 22.04.2023

Недавно был задан вопрос, который сводился к тому, что для заданной хэш-таблицы Map<Person, AtomicInteger> нужно было найти имя из ключа Person с максимальным значением AtomicInteger / Integer.

В решении были показаны примеры для нахождения одного максимального значения с использованием Stream::max(Comparator<? super T> cmp), и для нахождения списка имён, у которых могут быть одинаковые максимальные значения с использованием обычной итерации по содержимому хэш-таблицы:

record Result(Integer max, List<String> names) {}

public static Result getNamesWithMaxValue(Map<Person, AtomicInteger> map) {
    int max = Integer.MIN_VALUE;
    List<String> names = new ArrayList<>();
    for (Map.Entry<Person, AtomicInteger> e : map.entrySet()) {
        int curr = e.getValue().get();
        if (curr >= max) {
            if (curr > max) {
                max = curr;
                names.clear();
            }
            names.add(e.getKey().getName());
        }
    }
    return new Result(max, names);
}

Возник вопрос, каким образом можно было бы получить список всех максимальных (или минимальных) значений с использованием Stream API, и насколько такое решение было бы эффективным по сравнению с обычным циклом? Желательно, чтобы решение было обобщённое, а не для конкретного случая из вышеупомянутого вопроса.

java коллекции java-stream arraylist max
Источник: Stack Overflow на русском

Ответы

▲ 3

Возможны несколько вариантов решения:

  1. Сначала определяется максимальный элемент, а затем на втором проходе отфильтровываются значения, равные максимуму:
public static<T,R> List<R> maxList(Collection<T> data, Comparator<? super T> cmp, Function<T, R> converter) {
    return data.stream().max(cmp)   // определить максимум
        .map(max -> data.stream()   // второй проход
            .filter(x -> cmp.compare(x, max) == 0)  // фильтр максимумов
            .map(converter::apply)  // преобразование в нужный тип результата
            .collect(Collectors.toList())
        ).orElseGet(Collections::emptyList);
}
  1. Использовать кастомный коллектор Collector.of(Supplier<A> supplier, BiConsumer<A,T> accumulator, BinaryOperator<A> combiner, Function<A,R> finisher)
    Здесь Supplier<A> создаст списки, accumulator отфильтрует максимумы, combiner объединит несколько списков (в случае использования параллельных стримов), finisher преобразует список List<T> в список List<R> при помощи функции-конвертера.
public static<T,R> List<R> maxList(Collection<T> data, Comparator<? super T> cmp, Function<T, R> converter) {
    return data.stream()
        .collect(Collector.of(
            ArrayList::new,
            (List<T> list, T i) -> {
                if (list.isEmpty()) {
                    list.add(i);
                } else {
                    int c = cmp.compare(i, list.get(0));
                    if (c >= 0) {
                        if (c > 0) list.clear();
                        list.add(i);
                    }
                }
            },
            (lst1, lst2) -> {
                if (lst1.isEmpty()) return lst2;
                else if (lst2.isEmpty()) return lst1;
                int c = cmp.compare(lst1.get(0), lst2.get(0));
                if (c == 0) {
                    lst1.addAll(lst2);
                    return lst1;
                }
                return c > 0 ? lst1 : lst2;
            },
            lst -> lst.stream().map(converter::apply).collect(Collectors.toList())
        ));
}
  1. Сгруппировать по некоему ключу, получив хэш-таблицу, затем найти максимальное значение ключа.
    В данном случае получится двойной проход (в худшем случае) -- сначала по входной коллекции, затем по сету групп,-- и генерация промежуточных списков для групп.
public static<T,M extends Comparable,R> List<R> maxListGroup(
    Collection<T> data, Function<T, R> converter, Function<T, M> maxConverter
) {
    Optional<Map.Entry<M, List<R>>> max = data.stream()
        .collect(Collectors.groupingBy(
            maxConverter,
            Collectors.mapping(converter, Collectors.toList())
        )) // Map<M, List<R>>
        .entrySet()
        .stream()
        .max(Map.Entry.comparingByKey());
    return max
        .map(Map.Entry::getValue)
        .orElseGet(Collections::emptyList);
}

Для поиска минимумов следует использовать Stream::min в первом варианте, а во втором изменить знак в сравнениях с "больше" на "меньше".

Аналогично, если в дополнение к списку результатов нужно получить значение максимума, как в исходном вопросе, можно реализовать класс-обертку и добавить ещё одну функцию-конвертер для преобразования данных во входной коллекции в желаемый результат:

record Result<M, R>(M max, List<R> data){}

public static<T,M,R> Result<M, List<R>> maxResultTwoPass(
    Collection<T> data, Comparator<? super T> cmp, 
    Function<T, R> converter, Function<T, M> maxConverter
) {    
    return data.stream().max(cmp)
        .map(max -> new Result(
                maxConverter.apply(max),
                data.stream()
                .filter(x -> cmp.compare(x, max) == 0)
                .map(converter::apply)
                .collect(Collectors.toList())
            )
        ).orElse(null);
}

В варианте с кастомным коллектором слегка модифицируется finisher:

public static<T,M,R> Result<M, List<R>> maxResult(
    Collection<T> data, Comparator<? super T> cmp, 
    Function<T, R> converter, Function<T, M> maxConverter
) {    
    return data.stream()
        .collect(Collector.of(
            ArrayList::new,
            (List<T> list, T i) -> {
                if (list.isEmpty()) {
                    list.add(i);
                } else {
                    int c = cmp.compare(i, list.get(0));
                    if (c >= 0) {
                        if (c > 0) list.clear();
                        list.add(i);
                    }
                }
            },
            (lst1, lst2) -> {
                if (lst1.isEmpty()) return lst2;
                else if (lst2.isEmpty()) return lst1;
                int c = cmp.compare(lst1.get(0), lst2.get(0));
                if (c == 0) {
                    lst1.addAll(lst2);
                    return lst1;
                }
                return c > 0 ? lst1 : lst2;
            },
            lst -> lst.isEmpty() 
                    ? null 
                    : new Result(
                        maxConverter.apply(lst.get(0)), 
                        lst.stream().map(converter::apply).collect(Collectors.toList())
                    )
        ));
}

В варианте с группировкой модифицируется получение результата (или же можно вернуть Map.Entry):

public static<T,M extends Comparable,R> Map.Entry<M, List<R>> maxEntryGroup(
    Collection<T> data, Function<T, R> converter, Function<T,M> maxConverter
) {
    Optional<Map.Entry<M, List<R>>> max = data.stream()
        .collect(Collectors.groupingBy(
            maxConverter,
            Collectors.mapping(converter, Collectors.toList())
        )) // Map<M, List<R>>
        .entrySet()
        .stream()
        .max(Map.Entry.comparingByKey());
    return max.orElse(null);
}

public static<T,M extends Comparable,R> Result<M, List<R>> maxResultGroup(
    Collection<T> data, Function<T, R> converter, Function<T,M> maxConverter
) {
    Optional<Map.Entry<M, List<R>>> max = data.stream()
        .collect(Collectors.groupingBy(
            maxConverter,
            Collectors.mapping(converter, Collectors.toList())
        )) // Map<M, List<R>>
        .entrySet()
        .stream()
        .max(Map.Entry.comparingByKey());
    return max
        .map(e -> new Result(e.getKey(), e.getValue()))
        .orElse(null);
}

Тесты:

record Person(String name, int age) {}

public static void main(String args[]) {
    Map<Person, AtomicInteger> map = Map.of(
        new Person("John", 33), new AtomicInteger(1000),
        new Person("Joan", 27), new AtomicInteger(4000),
        new Person("Jane", 24), new AtomicInteger(7500),
        new Person("Jack", 29), new AtomicInteger(7500),
        new Person("Jeff", 31), new AtomicInteger(1000),
        new Person("Jess", 28), new AtomicInteger(7500)
    );
    
    Function<Map.Entry<Person, AtomicInteger>, String> fun = e -> e.getKey().name();
    Function<Map.Entry<Person, AtomicInteger>, Integer> res = e -> e.getValue().get();
    
    System.out.println(maxList(
        map.entrySet(),
        Map.Entry.<Person, AtomicInteger>comparingByValue(Comparator.comparingInt(AtomicInteger::get)), 
        fun
    ));

    System.out.println(maxResult(
        map.entrySet(),
        Map.Entry.<Person, AtomicInteger>comparingByValue(Comparator.comparingInt(AtomicInteger::get)), 
        fun,
        res
    ));

    System.out.println(maxEntryGroup(
        map.entrySet(),
        fun,
        res
    ));
}


[Jess, Jack, Jane]
Result[max=7500, data=[Jess, Jack, Jane]]
7500=[Jess, Jack, Jane]

Для пустой входной коллекции:

[]
null
null

Похожий вопрос на основном SO:

▲ 2

Вдогонку к ответу @NowhereMan.

Можно сделать кастомный аккумулятор для Stream.reduce:

public class MaxKeyAccumulator<K, V> {
    public V max;
    public List<K> keys;
    public final Comparator<V> cmp;

    public MaxKeyAccumulator(Comparator<V> cmp, V min) {
        super();
        keys = new LinkedList<>();
        max = min;
        this.cmp = cmp;
    }
    public <K1 extends K, V1 extends V> void accept(K1 key, V1 value) {
        if (cmp.compare(value, max) < 0) {
            return;
        }
        if (cmp.compare(value, max) == 0) {
            keys.add(key);
            return ;
        }
        max = value;
        keys.clear();
        keys.add(key);
    }
    public MaxKeyAccumulator<K,V> merge(MaxKeyAccumulator<K,V> other) {
        if (this.cmp.compare(other.max, this.max) < 0) {
            return this;
        }
        if (this.cmp.compare(other.max, this.max) > 0) {
            return other;
        }
        this.keys.addAll(other.keys);
        return this;
    }
}

Тогда пример с мапом персон в целые можно написать вот так:

    public static void main(String[] args) {
        Map<Person, Integer> map = Map.of(
            new Person("John", 33), 1000,
            new Person("Joan", 27), 4000,
            new Person("Jane", 24), 7500,
            new Person("Jack", 29), 7500,
            new Person("Jeff", 31), 1000,
            new Person("Jess", 28), 7500
        );
        
        var result = map.entrySet()
            .stream()
            .reduce(
                new MaxKeyAccumulator<Person, Integer>(Integer::compare, Integer.MIN_VALUE), 
                (acc, entry) -> { acc.accept(entry.getKey(), entry.getValue()); return acc; }, 
                (acc1, acc2) -> acc1.merge(acc2)
            );
        System.out.println(""+result.max +":"+ result.keys);
    }

Результат:

7500:[Person("Jack",29), Person("Jess",28), Person("Jane",24)]