时间戳

首页 > 解决方案 > Java 8 Stream，如何获得前 N 个计数？

java - Java 8 Stream，如何获得前 N 个计数？

问题描述

我需要您的建议来简化下面的代码。我有一个玩家列表，其中包含获胜游戏的 ID。我想从这个列表中提取 2 个最好的玩家（匹配 Id 数量更多的 2 个玩家） 提取后，我必须返回初始列表以进行其他操作。我认为可以在优化或阅读方面改进此代码。如果你能帮助我。

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

标签： javasortingjava-8java-streamcollect

解决方案

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

  1. 时间复杂度：您正在对整个数据集进行排序，其时间复杂度为O(mlogm)，与m初始玩家列表的大小相同。立即，您将使用列表中的顶级N元素N << m。

    下面我展示了一种将算法的时间复杂度提高到 的方法O(mlogN)，这意味着在您的特定情况下它会变成O(m)（这是因为N=2，所以logN=log2=1）。

  2. 您正在遍历数据集 3 次：首先您正在迭代玩家列表以创建计数地图，然后您正在迭代此地图以获得顶级N玩家的集合，最后您再次迭代玩家列表检查每个玩家是否属于顶级N玩家集合。

    这可以改进为仅对数据集执行 2 次遍历：第一次创建计数图（类似于您已经完成的），另一次创建仅保留顶部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（尽管我们将N+1元素相加）。首先我们将条目放入topN映射中，然后，如果映射有多个N条目，我们立即调用其pollLastEntry上的方法，该方法会删除优先级最低的条目（根据键的顺序TreeMap）。这保证了遍历时，topN地图将仅包含已排序的顶部N条目。

请注意，我使用的比较器首先TreeMap<Map.Entry<K, V>, K>按值V按降序排序，然后按键排序K。这是在函数的帮助下实现的，该Function<? super K, ? extends T> tieBreaker函数将每个键转换为必须K为 的值。所有这些都允许映射包含具有重复值的条目，而不需要键也是。TComparable<T>VKComparable<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);

推荐阅读