从 List 对象创建一个 SortedMap，其 Value 表示为映射到特定 Key 的 N 个最低对象属性的列表

Question

我正在处理一个 CSV 文件，其中包含一些有关事故的信息。

我创建了 Accident 类型：

private Integer driverAge;
private Integer vehicleAge;

public Accident(Integer driverAge, Integer vehicleAge) {
    this.driverAge = driverAge;
    this.vehicleAge = vehicleAge;
}

我还创建了一个读取所有 CSV 文件的函数，将所有事故转换为 List<Accident> 并将其保存为这种类型 AccidentArchive:

private List<Accident> accidents;

public AccidentArchive(List<Accident> accidents) {
    this.accidents = accidents;
}

所以，我们正在使用我还不完全理解的流，​​我一直被困在这个练习中，我必须制作一个 returns 一个 SortedMap<K, V> 的函数其中 key 必须是 driverAge 值并且该值必须是 list 在 降序 n 最低 vehicleAge 值 具有相同的 driverAge 值：

public SortedMap<Integer, List<Integer>> getNMinVehicleAgesPerDriverAge(Integer n) {
    return getAccidents().stream().
...

我试过使用 Collectors.toMap() 和 Collectors.toList() 以某种方式让它工作，但我不知道该怎么做。

Answer 1

简化方法

此问题与通过部分排序找到 N 最大（或最小）值的算法问题相关。它的实现使用收集器可能看起来很难，因此我决定引入一个简化的解决方案。

我们可以使用 groupingBy() 的风格，它需要 三个参数:

• a classifier 函数,
• a 供应商 mapFactory（允许指定生成的地图类型）
• 和一个下游收集器。

作为 groupingBy() 的下游收集器，我们可以将 collectingAndThen 与收集器 mapping() 和 toList() 的组合以及 函数 [=71] 结合使用=] 将对映射到每个 key 的整个结果列表进行排序，然后将删除不必要的值，仅保留 n 最低的 vehicleAge:

public SortedMap<Integer, List<Integer>> getNMinVehicleAgesPerDriverAge(Integer n) {
    return getAccidents().stream()
        .collect(Collectors.groupingBy(Accident::getDriverAge,
            TreeMap::new,
            Collectors.collectingAndThen(
                Collectors.mapping(Accident::getVehicleAge, Collectors.toList()),
                list -> list.stream()
                    .sorted(Comparator.reverseOrder())
                    .limit(n)
                    .collect(Collectors.toList()))));
}

更高性能的版本

正如我之前所说，当我们只需要其中一些时，我们不需要对映射到每个 key 的所有值进行排序。当 n 与列表的总大小相比（例如每个键的 3 到 100,000）时，它会导致严重的性能损失。

我们可以使用PriorityQueue引入部分排序（这是JDK中堆数据结构built-in的实现）。

为了增强以前的解决方案，我们需要替换 groupingBy() 的下游收集器，您可以结合使用 mapping() 和 自定义收集器 支持PriorityQueue 仅保留与每个 driverAge:

关联的最低 vehicleAge 值

public SortedMap<Integer, List<Integer>> getNMinVehicleAgesPerDriverAge(Integer n) {
    return getAccidents().stream()
        .collect(Collectors.groupingBy(Accident::getDriverAge,
            TreeMap::new,
            Collectors.mapping(Accident::getVehicleAge, 
                getMaxN(n, Comparator.<Integer>reverseOrder()))));
}

下面提供的方法负责根据提供的结果列表的最大大小和比较器生成自定义收集器。 :

中详细解释了其背后的逻辑

public static <T> Collector<T, ?, List<T>> getMaxN(int size, Comparator<T> comparator) {
        
    return Collector.of(
        () -> new PriorityQueue<>(comparator),
        (Queue<T> queue, T next) -> tryAdd(queue, next, comparator, size),
        (Queue<T> left, Queue<T> right) -> {
            right.forEach(next -> tryAdd(left, next, comparator, size));
            return left;
        },
        (Queue<T> queue) -> queue.stream().toList(),
        Collector.Characteristics.UNORDERED);
}
    
public static <T> void tryAdd(Queue<T> queue, T next, Comparator<T> comparator, int size) {
    if (queue.size() == size && comparator.compare(next, queue.element()) < 0) queue.remove(); // if next value is less than the smallest element in the queue and max size has been exceeded the largest element needs to be removed from the queue
    if (queue.size() < size) queue.add(next);
}

顺便说一下，如果您的作业没有指定使用 SortedMap 作为 return 类型的要求。最好使用 NavigableMap 接口，它定义了更广泛的方法。