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