Коллекция частичной сортировки с ограничением и настраиваемым компаратором

Я хочу отсортировать ArrayList с именем imageList следующим образом:

Collections.sort(imageList, new MapComparator(Function.KEY_TIMESTAMP, "dsc"));

Это работает нормально, но теперь я хочу иметь возможность установить предел (показывать только 100 новейших изображений, в которых ArrayList не отсортирован, поэтому простое создание подсписка не сработает) по соображениям производительности.

Мой класс MapComparator выглядит так:

class MapComparator implements Comparator<HashMap<String, String>>
{
    private final String key;
    private final String order;

    public MapComparator(String key, String order)
    {
        this.key = key;
        this.order = order;
    }

    public int compare(HashMap<String, String> first,
                       HashMap<String, String> second)
    {
        String firstValue = first.get(key);
        String secondValue = second.get(key);
        if (this.order.toLowerCase().contentEquals("asc"))
        {
            return firstValue.compareTo(secondValue);
        }else{
            return secondValue.compareTo(firstValue);
        }

    }
}

Кто-нибудь знает, как это реализовать? Заранее спасибо!

Вы хотите отсортировать только последние 100 элементов в списке массивов?

Mạnh Quyết Nguyễn 09.08.2018 12:27

Как общее замечание, не встраивайте такие вещи, как изменение порядка в вашем компараторе. Просто используйте метод reversed() на интерфейсе компаратора, чтобы изменить порядок следования.

Andy Turner 09.08.2018 12:27

@AndrewTobilko вы непременно должны посмотреть всю коллекцию; однако вам не обязательно использовать Сортировать для всей коллекции.

Andy Turner 09.08.2018 12:29
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
5
3
1 221
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Используйте отсортированный Stream:

List<HashMap<String, String>> newestImages = 
    imageList.stream()
             .sorted(new MapComparator(Function.KEY_TIMESTAMP, "dsc"))
             .limit(100)
             .collect(Collectors.toList());

Однако для этого потребуется обработка всех элементов в вашем List. Вы не можете избежать этого, если хотите отсортированный вывод.

Так все еще сортирует всю коллекцию или «останавливается» после того, как будут найдены 100 лучших результатов?

frizzle 09.08.2018 14:23

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

Eran 09.08.2018 14:26
Ответ принят как подходящий

Я не знаю официального названия этой проблемы, но она действительно возникает достаточно часто, и ее часто называют чем-то вроде проблемы top-k или величайшей k.

Вы определенно должны обработать все элементы во входных данных, потому что последний элемент может принадлежать набору «top k», и вы не узнаете об этом, пока не обработаете каждый последний элемент. Однако вам не нужно сортировать весь ввод. Выполнение чего-то вроде сортировки с последующим взятием подсписка или с потоком с вызовом sorted(), за которым следует limit(), потенциально может быть очень дорогостоящим, поскольку с N входными элементами сортировка выполняется O (N log N). Однако можно уменьшить временную сложность до O (N), просто отслеживая самые большие элементы k, наблюдаемые до тех пор, пока вы просматриваете список.

У Guava есть Коллекционер, который делает именно это: Comparators.greatest (k, компаратор).

Если вы не хотите использовать Guava, не так уж сложно создать собственный сборщик, который более или менее эквивалентен. PriorityQueue очень пригодится для этой цели. Вот первый пример:

static <T> Collector<T,PriorityQueue<T>,List<T>> topK(int k, Comparator<? super T> comp) {
    return Collector.of(
        () -> new PriorityQueue<>(k+1, comp),
        (pq, t) -> {
            pq.add(t);
            if (pq.size() > k)
                pq.poll();
        },
        (pq1, pq2) -> {
            pq1.addAll(pq2);
            while (pq1.size() > k)
                pq1.poll();
            return pq1;
        },
        pq -> {
            int n = pq.size();
            @SuppressWarnings("unchecked")
            T[] a = (T[])new Object[n];
            while (--n >= 0)
                a[n] = pq.poll();
            return Arrays.asList(a);
        },
        Collector.Characteristics.UNORDERED);
}

Здесь в качестве промежуточной структуры данных используется PriorityQueue. По мере добавления элементов самый маленький элемент обрезается, когда очередь превышает размер k. В конце элементы извлекаются из очереди и помещаются в список в обратном порядке, поэтому результирующий список сортируется от самого высокого до самого низкого.

Например, учитывая List<Integer>, содержащий

[920, 203, 880, 321, 181, 623, 496, 576, 854, 323,
 339, 100, 795, 165, 857, 935, 555, 648, 837, 975]

можно сделать

List<Integer> out = input.stream()
                         .collect(topK(5, Comparator.naturalOrder()));

в результате чего

[979, 936, 890, 875, 831]

Кроме того, можно гораздо проще создать компаратор карт, используя методы комбинатора в классе Comparator. Например, предположим, что ваш ввод выглядит так:

    List<Map<String, String>> input =
        List.of(Map.of("name", "map1", "timestamp", "00017"),
                Map.of("name", "map2", "timestamp", "00192"),
                Map.of("name", "map3", "timestamp", "00001"),
                Map.of("name", "map4", "timestamp", "00072"),
                Map.of("name", "map5", "timestamp", "04037"));

Вы можете легко отсортировать карты по отметкам времени следующим образом:

    input.stream()
         .sorted(Comparator.comparing(map -> map.get("timestamp")))
         .forEach(System.out::println);

Или соберите их в список, или отсортируйте на месте, используя sort(comparator), или что-то еще. Вы можете отменить сортировку, выполнив:

    input.stream()
         .sorted(Comparator.comparing(map -> map.get("timestamp"), Comparator.reverseOrder()))
         .forEach(System.out::println);

Результатом последнего будет:

{name=map5, timestamp=04037}
{name=map2, timestamp=00192}
{name=map4, timestamp=00072}
{name=map1, timestamp=00017}
{name=map3, timestamp=00001}

Большое спасибо за подробный ответ!

frizzle 16.08.2018 09:38

@StuartMarks, это хорошо, 1+, но несколько замечаний, если вы не против ... 1) почему финишер не такой простой, как ArrayList::new 2) должен ли он также сообщать о SORTED, если бы использовался Comparator.naturalOrder() (интересно если это доступно для обнаружения, хотя или еще хуже Comparator.naturalOrder().reserved().reversed() - но здесь, вероятно, за рамками) ...

Eugene 21.08.2018 21:27

@Eugene Конечно, без проблем. 1) Конструктор копирования ArrayList будет повторять по предоставленной коллекции, чтобы получить элементы, а PriorityQueue не выполняет итерацию в отсортированном порядке. PQ может сортировать только деструктивно, многократно удаляя или опрашивая заголовок PQ. 2) SORTED - это характеристика сплитератора, а не характеристика коллектора. Я указал UNORDERED, потому что промежуточное хранилище (PQ) не гарантирует сохранение порядка сравниваемых элементов.

Stuart Marks 22.08.2018 01:03

Другие вопросы по теме