Можно ли сгруппировать и найти верхние N ровно за одну итерацию - PullRequest
Новая
       75

Можно ли сгруппировать и найти верхние N ровно за одну итерацию

1 голос
/ 14 июля 2020

Это зависит от этого Как применить к сортировке и ограничению после groupBy с использованием Java потоков , потому что я хочу решить эту проблему ровно за одну итерацию. Представьте, что у меня есть следующий объект: 

@Getter
@Setter
@AllArgsConstructor
public static class Hospital {
    private AREA area;
    private int patients;
}

public enum AREA {
    AREA1, AREA2, AREA3
}

Теперь, учитывая список больниц, я хочу найти районы с большинством пациентов в них, вот что я сделал до сих пор: 

public static void main(String[] args) {
    List<Hospital> list = Arrays.asList(
            new Hospital(AREA.AREA1, 20),
            new Hospital(AREA.AREA2, 10),
            new Hospital(AREA.AREA1, 10),
            new Hospital(AREA.AREA3, 40),
            new Hospital(AREA.AREA2, 10));
    Map<AREA, Integer> map = findTopTen(list);
    for (AREA area : map.keySet())
        System.out.println(area);

}

public static Map<AREA, Integer> findTopTen(Iterable<Hospital> iterable) {
    Map<AREA, Integer> iterationOneResult = StreamSupport.stream(iterable.spliterator(), false)
            .collect(Collectors.groupingBy(Hospital::getArea,
                    Collectors.summingInt(Hospital::getPatients)));
    return iterationOneResult.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
            .limit(10)
            .collect(Collectors.toMap(Map.Entry::getKey,
                    Map.Entry::getValue, (o, o2) -> o,
                    LinkedHashMap::new));

}

Ясно, что я повторил два раза, чтобы найти десять областей с наибольшим количеством пациентов (один раз для группировки больниц по областям и вычисления суммы для этой группы и еще раз для поиска десяти областей с наибольшим числом пациентов).

Теперь я хочу знать:

  1. Есть ли лучший подход для решения этой проблемы в одном потоке и, следовательно, в одной итерации?

  2. Является ли есть ли какое-либо преимущество в производительности для выполнения этого за одну итерацию, как лучше всего решить эту проблему? (С моей точки зрения, с одной стороны, когда я вызываю collect, который является операцией терминала в первый раз, когда он выполняет итерацию моей итерации и сохраняет промежуточный результат в другом объекте, в моем коде я назвал этот объект iterationOneResult, поэтому, используя один поток и вызывая collect one time пропустит этот промежуточный результат, который является основным преимуществом использования потока в java, с другой стороны, решение этой проблемы за одну итерацию сделает его намного быстрее).

1 Ответ

0 голосов
/ 14 июля 2020

Позвольте мне попытаться ответить на ваши вопросы и пояснить, почему они, возможно, не те:

  1. Есть ли лучший подход для решения этой проблемы в одном потоке и, следовательно, одна итерация?

Основная проблема здесь в том, что ваша цель - найти группы с максимальными значениями, начиная только с необработанных членов этих групп , несортированный. Поэтому, прежде чем вы сможете найти максимум чего-либо, вам нужно будет распределить участников по группам. Проблема в том, какие участники находятся в группе, определяет ценность этой группы - это приводит к логическому выводу, что вы не можете принимать решения типа «какие десять групп» до сортировки всех своих членов по группам.

Это одна из причин того, что groupingBy является Коллектором - коллектор выполняет терминальную операцию , что является причудливым способом сказать, что он потребляет весь поток и не возвращает поток, но разрешенный что-то - он «завершает» поток.

Причина, по которой ему необходимо завершить поток (т.е. дождаться последнего элемента перед возвратом его групп), заключается в том, что он не может дайте вам группу A до того, как увидите последний элемент, потому что последний элемент может принадлежать группе A. Группировка - это операция, которая в несортированном наборе данных не может быть обработана конвейером.

Это означает, что независимо от того, что вы делаете, существует жесткое логическое требование: сначала вам нужно как-то сгруппировать свои элементы, а затем найти максимум. Этот порядок first, then подразумевает две итерации: одну по элементам, вторую по группам.

Есть ли какое-то преимущество в производительности при выполнении этого за одну итерацию, как лучше всего решить эту проблему? (С моей точки зрения, с одной стороны, когда я вызываю сбор, который является операцией терминала в первый раз, когда он выполняет итерацию моей итерации и сохраняет промежуточный результат в другом объекте, в моем коде я назвал этот объект итерациейOneResult, поэтому, используя один поток и вызывая сбор одного time пропустит этот промежуточный результат, который является основным преимуществом использования потока в java, с другой стороны, решение этой проблемы за одну итерацию делает его намного быстрее).

Re -прочитайте выше: «две итерации: одна по элементам, вторая по группам» . Это всегда будет происходить. Однако обратите внимание, что это две итерации над двумя разными вещами. Учитывая, что у вас, вероятно, меньше групп, чем участников, последняя итерация будет короче. Ваше время выполнения будет не O(2n) = O(n), а O(f(n, m)), где f(n,m) будет «стоимостью сортировки n членов в m групп плюс стоимость поиска максимальных k групп».

Есть ли какое-то преимущество в производительности при выполнении этого за одну итерацию

Ну ... нет, поскольку, как уже говорилось, вы не можете.

Как лучше всего решить эту проблему?

Я не могу этого подчеркнуть: чистый код .

99.9% случаев, вы потратите больше времени на оптимизацию с пользовательскими классами, чем они вернут вам производительность, если они вообще могут принести вам что-нибудь. Легкая выгода, которую можно получить здесь, - это минимизировать количество строк кода и максимизировать их понятность для будущих программистов.

...