Java 8 Stream，如何获取前N个计数？

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想要改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

2年前关闭。



Improve this question




我需要您的建议来简化以下代码。我有一个球员名单，上面有赢得比赛的ID。我想从此列表中提取2个最佳球员(2个具有较高比赛ID的球员)
提取后，我必须返回初始列表以执行其他操作。
我认为可以通过优化或阅读来改进此代码。如果你能帮助我。

public class PlayerStatistics {
    int id
    String name;
    int idMatchWon; // key from Match

    // getter , setter
}

public static void main(String[] args) throws Exception {

    List<PlayerStatistics> _players = new ArrayList<PlayerStatistics>();

    _players.add(initialize(1,'John',4));
    _players.add(initialize(2,'Teddy',2));
    _players.add(initialize(3,'Kevin',3));

    // How to get Top 2
    List<PlayerStatistics> _top2Players = extractTop2Players(_players);
}

private List<PlayerStatistics> extractTop2Players (List<PlayerStatistics> _list) {

    List<PlayerStatistics> _topPlayers = new ArrayList<PlayerStatistics>();

    // 1. Group and count
    Map<String, Long> _players = _list
            .stream()
            .filter(x -> (!"".equals(x.getName()) && x.getName()!= null) )
            .collect(
                    Collectors.groupingBy(
                            PlayerStatistics::getName, Collectors.counting()
                    )
            );
    ;

    // 2 Best Palyers
    Set<String> _sortedPlayers = _players.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(Collections.reverseOrder()))
            .limit(2)
            .map(Entry::getKey)
            .collect(Collectors.toSet())
    ;

    // 3. Rebuild list
    _topPlayers = _list
            .stream()
            .filter(x -> _sortedPlayers.contains(x.getName()))
            .collect(Collectors.toList())
    ;

    return _topPlayers;
}


private PlayerStatistics initialize (int id, String name, int year, int month, int won, int lost) {
    return
        new PlayerStatistics()
            .withId(id)
            .withName(name)
            .withIdMatchWon(won)
        );
}

最佳答案

首先，让我们声明您的代码绝对正确。它可以完成需要做的事情，甚至可以通过使用集合进行优化。但是，可以通过两种方式进一步改进它:

时间复杂度:您正在对整个数据集进行排序，时间复杂度为O(mlogm)，m是初始玩家列表的大小。立即，您将列表中最重要的N元素与N << m一起使用。
下面，我展示了一种将算法的时间复杂度提高到O(mlogN)的方法，这意味着在您的特定情况下它将变成O(m)(这是因为N=2，所以是logN=log2=1)。

您遍历数据集3次:首先迭代播放器列表以创建计数图，然后迭代该图以获取具有顶部N播放器的集合，最后迭代列表再次检查每个玩家是否属于顶级N玩家集合。
可以改进此方法，以仅对数据集执行两次传递:第一个传递来创建计数图(类似于您已经完成的操作)，第二个传递来创建仅保留最上面的N元素的结构按计数递减，遍历完成后可以返回结果。

重要:以下解决方案要求您的PlayerStatistics类一致地实现hashCode和equals方法。
首先，我们有一个通用的topN方法(毫不奇怪)，它从任何给定的映射中提取顶部的N元素。它通过按值将其条目按降序进行比较来实现此目的(在此版本中，V值必须为Comparable<V>，但是通过提供自定义Comparable<V>，可以轻松地将此算法扩展为支持不实现Comparator<V>的值):

public static
<K, V extends Comparable<? super V>, T extends Comparable<? super T>>
Collection<K>
topN(
        Map<K, V> map,
        int N,
        Function<? super K, ? extends T> tieBreaker) {

    TreeMap<Map.Entry<K, V>, K> topN = new TreeMap<>(
        Map.Entry.<K, V>comparingByValue()      // by value descending, then by key
            .reversed()                         // to allow entries with duplicate values
            .thenComparing(e -> tieBreaker.apply(e.getKey())));

    map.entrySet().forEach(e -> {
      topN.put(e, e.getKey());
      if (topN.size() > N) topN.pollLastEntry();
    });

    return topN.values();
}

此处topN TreeMap 的行为相当于N大小的priority queue(尽管我们将N+1元素加起来)。首先，我们将条目放入topN映射中，然后，如果映射中包含的条目不止N条目，我们立即在其上调用 pollLastEntry 方法，该方法将删除优先级最低的条目(根据TreeMap的键顺序) 。这保证了遍历时，topN映射将仅包含已排序的顶部N条目。
请注意，我正在使用一个比较器，该比较器首先按TreeMap<Map.Entry<K, V>, K>值的降序对V进行排序，然后再按K键进行排序。这是通过Function<? super K, ? extends T> tieBreaker函数实现的，该函数将每个键K转换为必须是T的值Comparable<T>。所有这些使 map 可以包含具有V重复值的条目，而无需将键K也设置为Comparable<K>。
最后，您将使用上述方法，如下所示:

Map<PlayerStatistics, Long> counts = yourInitialListOfPlayers.stream()
    .filter(x -> !"".equals(x.getName()) && x.getName() != null)
    .collect(Collectors.groupingBy(x -> x, Collectors.counting()));

Collection<PlayerStatistics> top2 = topN(counts, 2, PlayerStatistics::getName);