使用Java 8合并、排序和限制Map流

Question

我有两个地图 Map<String, Long>。我想合并这两个地图，按降序排序，并获取前5个。如果合并中存在重复键，则需要将值相加。以下是可以正常工作的代码：

Map<String, Long> topFive = (Stream.concat(map1.entrySet().stream(), 
                                           map2.entrySet().stream())
                                   .collect(Collectors.toMap(Map.Entry::getKey, 
                                                             Map.Entry::getValue,
                                                             Long::sum)))
                                   .entrySet()
                                   .stream()
                                   .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                                   .limit(5)
                                   .collect(Collectors.toMap(Map.Entry::getKey,
                                                             Map.Entry::getValue,
                                                            (v1, v2) -> v1,
                                                            LinkedHashMap::new));

但我想知道是否有更好的解决方案。

- nufar

---

如果你的代码已经能够正常运行，[codereview.se] 是一个更好的网站来发帖子提问。 - user202729

Answer 1

如果您所说的“更好”是指性能方面，并且您有大量的集合，只需要几个顶部元素，那么可以避免对整个映射进行排序，考虑到n * log(n)的复杂度。

如果您已经使用了Guava，可以使用MinMaxPriorityQueue仅存储最佳的N个结果。然后只需对这几个常数N元素进行排序即可。

Comparator<Entry<String, Long>> comparator = Entry.comparingByValue(reverseOrder());

Map<String, Long> merged = Stream.of(map1, map2)
        .map(Map::entrySet)
        .flatMap(Set::stream)
        .collect(Collectors.toMap(Map.Entry::getKey, 
                Map.Entry::getValue, 
                Long::sum));

MinMaxPriorityQueue<Entry<String, Long>> tops = MinMaxPriorityQueue.orderedBy(comparator)
        .maximumSize(5)
        .create(merged.entrySet());

Map<String, Long> sorted = tops.stream()
        .sorted(comparator)
        .collect(Collectors.toMap(Map.Entry::getKey, 
                Map.Entry::getValue,
                (m1, m2) -> m1,
                LinkedHashMap::new));

如果您没有/不想使用Guava，可以通过使用自定义的TreeMap来模拟MinMaxPriorityQueue（也可以创建一个在构造函数中接收最大大小的类，如果您不想使用匿名类[这是为了展示功能]）。

Set<Entry<String, Long>> sorted = new TreeSet<Entry<String, Long>>(comparator) {
    @Override
    public boolean add(Entry<String, Long> entry) {
        if (size() < 5) { // 5 can be constructor arg in custom class
            return super.add(entry);
        } else if (comparator().compare(last(), entry) > 0) {
            remove(last());
            return super.add(entry);
        } else {
            return false;
        }
    }
};

将所有元素添加到具有顶部的集合中。

sorted.addAll(merged);

你也可以更改合并函数，使用类似Federico提到的合并方式。

Map<String, Long> merged = new HashMap<>(map1);
map2.forEach((k, v) -> merged.merge(k, v, Long::sum));

这种方法比使用流更快，一旦你拥有了合并后的映射表，就可以使用MinMaxPriorityQueue或TreeSet选择前N个元素，避免再次对整个集合进行排序。请保留HTML标签。

- Jose Da Silva

---

在你的第一个例子中，你使用了flatMap。当我寻找答案时，我看到了一些博客说flatMap不适用于大型集合。这是真的吗？目前我对我的映射大小没有确切的了解，但有时可能会达到1000左右。 - nufar

流（Stream）速度稍慢，但对于仅有1000个元素的集合，差异可能不会被注意到。您可以使用map构造函数，然后使用merge函数生成合并的map，再使用MinMaxPriorityQueue或TreeSet来避免对整个集合进行不必要的排序。我将在答案中提到这一点。 - Jose Da Silva

Answer 2

我会专注于让代码更易读：

// Merge
Map<String, Long> merged = new HashMap<>(map1);
map2.forEach((k, v) -> merged.merge(k, v, Long::sum));

// Sort descending
List<Map.Entry<String, Long>> list = new ArrayList<>(merged.entrySet());
list.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

// Select top entries
Map<String, Long> top5 = new LinkedHashMap<>();
list.subList(0, Math.min(5, list.size()))
    .forEach(e -> e.put(e.getKey(), e.getValue()));

此外，不使用流的话，这个解决方案肯定会有更好的性能。

- fps

Answer 3

这里提供另一种使用Collector的解决方案。它使用TreeSet作为中间累加类型，并通过完成器将集合转换为映射。

private <K, V, E extends Map.Entry<K,V>> Collector<E, TreeSet<E>, Map<K,V>> 
        toMap(BinaryOperator<V> mergeFunction, Comparator<E> comparator, int limit) {
    Objects.requireNonNull(mergeFunction);
    Objects.requireNonNull(comparator);

    Supplier<TreeSet<E>> supplier = () -> new TreeSet<>(comparator);
    BiConsumer<TreeSet<E>, E> accumulator = (set, entry) -> accumulate(set, entry, mergeFunction);
    BinaryOperator<TreeSet<E>> combiner = (destination, source) -> {
            source.forEach(e -> accumulator.accept(destination, e)); return destination; };
    Function<TreeSet<E>, Map<K,V>> finisher = s -> s.stream()
            .limit(limit)
            .collect(Collectors.toMap(E::getKey, E::getValue, (v1, v2) -> v1, LinkedHashMap::new));

    return Collector.of(supplier, accumulator, combiner, finisher);
}

private <K, V, E extends Map.Entry<K,V>> void accumulate(
        TreeSet<E> set, E newEntry, BinaryOperator<V> mergeFunction) {
    Optional<E> entryFound = set.stream()
            .filter(e -> Objects.equals(e.getKey(), newEntry.getKey()))
            .findFirst();

    if (entryFound.isPresent()) {
        E existingEntry = entryFound.get();
        set.remove(existingEntry);
        existingEntry.setValue(mergeFunction.apply(existingEntry.getValue(), newEntry.getValue()));
        set.add(existingEntry);
    }
    else {
        set.add(newEntry);
    }
}

这是如何使用它的，通过值（反向）比较条目，并在条目冲突时使用Long::sum合并函数。

Comparator<Map.Entry<String,Long>> comparator = Map.Entry.comparingByValue(Comparator.reverseOrder());
Map<String, Long> topFive = Stream.of(map1, map2)
        .map(Map::entrySet)
        .flatMap(Collection::stream)
        .collect(toMap(Long::sum, comparator, 5));

- Renan Paul Blanco

Answer 4

一个更好的解决方案可能是使用一个累加器来保留前5个，而不是对整个流进行排序。现在你只需要进行大约 n * log(n) 次比较，而不是在 n 和 n * log(5) 之间。

- Paul Janssens