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

标签 java collections comparator

我想像这样对一个名为 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);
        }

    }
}

有人知道如何实现吗? 提前致谢!

最佳答案

我不知道这类问题的正式名称,但它确实经常发生,并且通常被称为 top-k 或 greatest-k 问题。

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

Guava 有一个 Collector 可以做到这一点:Comparators.greatest(k, comparator) .

如果您不想使用 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 中的组合器方法更简单地创建 map 比较器。类(class)。例如,假设您的输入如下所示:

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

您可以像这样按时间戳轻松地对 map 进行排序:

    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}

关于java - 具有限制和自定义比较器的部分排序集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51764518/

相关文章:

java - java中Comparator中super的使用

java - 检查 Collection 值(value)

java - JDiagram 旧版本在 ExtendedArrayList.sort 中使用 JRE 8 抛出 StackOverflowError

java - 如何使用比较器对集合中的多个字段进行排序?

c++ - 这个比较是否不一致(还是存在另一个问题)?

java - Karate Spring 整合

java - 如何在 Apache Flink 中正确初始化任务状态?

java - 需要一种方法以黑/白方式获取图像中的文本

javascript - 主干显示集合(也许是集合的集合?)

java - 如何在java中获取比较器的倒数