带有限制和自定义比较器的部分排序集合

Question

我想像这样对一个名为 imageList 的 ArrayList 进行排序：

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

    }
}

有谁知道如何实现？提前致谢！

Answer 1

我不知道此类问题的正式名称，但它确实经常发生，并且通常被称为“top- k”或“best- k”问题。

您当然必须处理输入中的所有元素，因为最后一个元素可能属于“top  k ”集合，并且在处理完每个最后一个元素之前您不知道。但是，您不必对整个输入进行排序。执行诸如排序然后获取子列表之类的操作，或者使用流，调用sorted()后跟limit()，可能会非常昂贵，因为对于 N 个输入元素，排序的时间复杂度为 O(N log N)。但是，只需跟踪在遍历列表时看到的最大k个元素，就可以将时间复杂度降低到 O(N)。

Guava 有一个收集器可以做到这一点：Comparators.greatest(k, comparator)。

如果您不想使用 Guava，那么构建您自己的或多或少等效的收集器并不太困难。APriorityQueue对于此目的非常有用。这是它的第一部分：

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

这使用 aPriorityQueue作为中间数据结构。添加元素时，当队列大小超过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}