Java 8 Stream,如何获得前N个计数？

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

Answer 1

首先,让我们说明你的代码绝对正确.它做了需要做的事情,甚至通过使用集合进行优化.不过,它可以通过两种方式进一步改进:

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>by值V,然后按键排序K.这是在Function<? super K, ? extends T> tieBreaker函数的帮助下实现的,该函数将每个键K转换为T必须的值Comparable<T>.这一切都使地图包含有重复值的条目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);