使用Java 8 Stream API计算排名

两个问题一个接一个地解决

• 排名代表
• 排名程序

---

排名代表

如上所示，典型的排名是项目列表，其后是其相对排名值。

排名的返回值至少有两种可能的实现。

选项1： List<Rank>

排名的可能内部表示形式可以是包含排名值和项目的元素列表。例如，我们可以定义一个类：

public class Rank<T> {
  protected int ranking;
  protected T item;
  protected Rank(int r, T i) { ranking=t; item=i; }
  public int getRanking() { return ranking; }
  public T getItem() { return item; }
  static <T> Rank<T> factory(int ranking, T item) { 
      return new Rank<T>(ranking,item);
  }
}

或者，使用一些更加复杂的代码：

public interface Rank<T> {
      int getRanking();
      T getItem();
      static <T> Rank<T> factory(int ranking, T item) { 
          return new Rank<T>(){
               public int getRanking() { return ranking; }
               public T getItem() { return item; }
          };}
}

产生的排名将以形式返回List<Rank>。该列表必须按降序返回并按该顺序处理。

这种解决方案的潜在缺点是需要新的临时类或接口（即Rank）。

选项2： SortedMap<Integer,List<T>>

仅使用预定义标准类和接口的替代解决方案基于地图。

地图的键对应于排名值，而地图的值包含在包含共享该排名的项目的列表中。

排名的返回类型为SortedMap<T,List<T>>。排序后的映射将被隐式排序，并且可以根据键的自然顺序遍历。

后一种解决方案似乎是可取的，因为它不需要任何新类，并且可以更好地理解。

---

排名程序

排名计算过程可以以不同的方式实现。这里研究了两种方法。

在所有情况下，我们都需要一个函数来提取排名属性：

Function<String,Integer> propertyExtractor = String::length;

通常，属性类型应该是可比较的，尽管可以更一般地定义属性比较器（例如，以降序对字符串进行排序）：

Comparator<Integer> propertyComparator = reverseOrder();

结合上述案例研究，以words流为起点，说明了两种方法：

String paragraph = "A common problem when processing data is to build  a ranking of items based on some property";
Stream<String> words = Stream.of(paragraph.split(" "));

按排名属性排序

基本程序

可以使用支持的地图数据结构定义该过程的初始初始版本，流操作可通过以下副作用在其上进行工作：

SortedMap<Integer,List<String>> ranking = new TreeMap<>();

步骤如下：

1. 排序流中的元素

   words.sorted(comparing(propetyExtractor,propertyComparator))
   

2. 分配排名，从1该属性开始并在属性更改时递增。排名必须增加共享当前排名的项目数。

   .forEach( item -> {
       Integer property = propertyExtractor.apply(item);
       if(ranking.isEmpty()){
           ranking.put(1,new LinkedList<String>());
       }else{
           Integer rank = ranking.lastKey();
           List<String> items = ranking.get(rank);
           if(! property.equals(propertyExtractor.apply(items.get(0)))) {
               ranking.put(rank+items.size(), new LinkedList<String>());
           }
       }
       ranking.get(ranking.lastKey()).add(item);
   });
   

上面的代码如下：

• 项目的初始顺序是未排序的：

  {"DD","BBB","F","CCC","AAAA","EE"}

• 第1步使用propertyExtractor和相对值对项目进行排序propertyComparator，即按字符串长度：

  {"AAAA","BBB","CCC","DD","EE","F"}

• 那么对于每个元素（按顺序），只要新元素的长度与先前元素的长度不同，就会在映射中添加一个新条目

  • 当"AAAA"被处理（第一项）一个新条目被添加到地图密钥（即排名）= 1：

    ranking ： {1=["AAAA"]}

  • 在处理第二个项目时"BBB"，由于其长度（3）与最后一个元素长度（4的长度"AAAA"）不同，因此添加了具有未更新排名值的新条目：

    ranking ： {1=["AAAA"],2=["BBB"]}

  • 在处理第三个项目时"CCC"，由于其长度（3）等于最后一个元素的长度，因此该项目将添加到条目列表中

    ranking ： {1=["AAAA"],2=["BBB","CCC"]}

  • 等等

收集器的用法

可以通过使用收集器来定义更具功能性的版本，该收集器封装了累积结果的数据结构。实际上，我们可以编写单个流表达式来返回排名图：

SortedMap<Integer,List<String>> ranking = 
words.sorted(comparing(propertyExtractor,propertyComparator))
     .collect(TreeMap::new, // supplier

             (rank, item) -> {  // accumulator
                 Integer property = propertyExtractor.apply(item);
                 if(rank.isEmpty()){
                     rank.put(1,new LinkedList<String>());
                 }else{
                     Integer r = rank.lastKey();
                     List<String> items = rank.get(r);
                     Integer prevProp = propertyExtractor.apply(items.get(0))
                     if(! property.equals(prevProp)) {
                         rank.put(r+items.size(), new LinkedList<String>());
                     }
                 }
                 rank.get(rank.lastKey()).add(item);
             },

             (rank1,rank2) -> { // combiner
                 \\...
             }
     );

合并结果

上面的代码中未定义的组合器方法值得一些其他的反思。

并行执行收集时会涉及功能接口。它用于将累积的两个部分结果合并为一个结果。在这种情况下，它必须实现接口BiConsumer<R,R>，并且应该将两个累加的排名-rank1和rank2-合并到第一个。

供应商的可能实现是：

BiConsumer<SortedMap<Integer,List<String>>,
             SortedMap<Integer,List<String>>> combiner =  
(rank1,rank2) -> {
        int lastRanking = rank1.lastKey();
        int offset = lastRanking + rank1.get(lastRanking).size()-1;
        if( propertyExtractor.apply(rank1.get(lastRanking).get(0))
            == propertyExtractor.apply(rank2.get(rank2.firstKey()).get(0)) ){
            rank1.get(lastRanking).addAll(rank2.get(rank2.firstKey()));
            rank2.remove(rank2.firstKey());
        }
        rank2.forEach((r,items) -> {rank1.put(offset+r, items);} );
}

收集器没有声明的属性，因此将按顺序处理元素，然后按顺序组成。例如，将排序的项目列表分为两部分，然后通过收集器的一个副本处理第一部分，从而生成地图rank1；并行处理第二部分，结果为rank2。

让我们假设在收集操作的两个并发执行中并行处理流：

• 初始排序的流（运算结果sorted()分为两个流，保持顺序

  • 子流1： {"AAAA","BBB","CCC"}
  • 子流2： {"DD","EE","F"}

• 两个不同的收集器并行运行，在每个子流上的结果是两个包含每个子流的部分排名的地图：

  • rank1 = {1=["AAAA"],2=["BBB","CCC"]}
  • rank2 = {1=["DD","EE"],3=["F"]}

• 该组合操作应该合并rank2到rank1，在实践中的每一项rank2操作应该被添加到rank1其关键更新。通过添加等于最后一个条目的键加上最后一个条目值列表的长度减去一个的偏移量来更新它们的键：

  int lastRanking = rank1.lastKey();
  int offset = lastRanking + rank1.get(lastRanking).size()-1;
  

  在实践中，进入1=["DD","EE"]的rank2应该变成4=["DD","EE"]和加入rank1。

• 另外，应考虑一种特殊情况，即，当的最后一个条目中的项目与第一个条目rank1中的项目rank2共享相同的排名属性值时。例如字符串长度：

  • rank1 = {1=["AAAA"],2=["BBB","CCC"]}
  • rank2 = {1=["DDD"],2=["EE"],3=["F"]}

  发生这种情况时，rank2必须将第一个条目列表中的项目添加到最后一个rank1条目列表中，然后删除第一个条目。那就是上面的地图应该转换成：

  • rank1 = {1=["AAAA"],2=["BBB","CCC","DDD"]}
  • rank2= {~~ 1=["DDD"],~~2=["EE"],3=["F"]}

  然后，rank2可以rank1如上所述更新和添加的条目。

按属性分组

基本程序

对于排序列表版本，可以使用支持的映射数据结构来定义该过程的初始原始版本，流操作可以通过副作用在其上进行操作：

SortedMap<Integer,List<String>> ranking = new TreeMap<>();

天真的过程如下：

1. 在排序的地图中按项目的属性对项目进行分组

   words.collect(groupingBy(propertyExtractor,
                           ()->new TreeMap<>(propertyComparator),toList()))
   

2. 对于上面地图中的每个条目，计算排名

        .forEach(
           (property,items) -> 
               ranking.put(ranking.isEmpty()?1:ranking.lastKey()+
                                   ranking.get(ranking.lastKey()).size(),
                           items )
                );
   

上面的代码如下：

• 项目的初始顺序是未排序的：

  {"DD","BBB","F","CCC","AAAA","EE"}

• 步骤1按项目将项目分组，propertyExtractor然后将其存储到一个排序集中，其键通过进行排序propertyComparator，即按字符串长度排序：

  {4=["AAAA"],3=["BBB","CCC"],2=["DD","EE"],1=["F"]}

• 步骤2，为中间映射中的每个条目创建一个新的条目，结果映射中的新条目具有排名值作为关键字，并且具有与中间条目相同的值（即项目列表）。

  排名计算如下：

  • 1作为第一个条目（即，当结果映射仍然为空时），或者
  • 先前排名（ranking.lastKey()）加上共享先前排名（ranking.get(ranking.lastKey()).size()）的元素数。

  结果是最终的排名图：

  {1=["AAAA"],2=["BBB","CCC"],4=["DD","EE"],6=["F"]}

使用收集器

可以使用收集器重写以上过程，以避免操作的副作用。

由于第一步包含在集合中，因此我们可以使用预定义的收集器工厂方法collectingAndThen来将第一个收集器与应用于收集器结果的函数连接在一起。这样的功能将执行上述步骤2。

SortedMap<Integer,List<String>> ranking = 
words.collect(
       collectingAndThen(
            groupingBy(propertyExtractor, 
                         ()->new TreeMap<>(propertyComparator),
                         toList()),
            map -> map.entrySet().stream().collect(
                      TreeMap::new,
                      (rank,entry) -> 
                          rank.put(rank.isEmpty()?1:rank.lastKey()+ 
                                        rank.get(rank.lastKey()).size(),
                                 entry.getValue() ),
                      combiner 
                    )
        )
);

由于结果的结构（即累加器对象）与排序的流解决方案相同，因此可以使用相同的组合器。

通用解决方案

上面的讨论和解决方案适用于字符串流的特殊情况。但是该方法可以使用泛型进行概括。

排名排序功能

基于排序流的解决方案可以包含在一个函数中：

static <T,V> SortedMap<Integer,List<T>> 
rank(Stream<T> stream, 
     Function<T,V> propertyExtractor, 
     Comparator<V> propertyComparator){
  return
  stream.sorted(comparing(propertyExtractor,propertyComparator))
        .collect(TreeMap::new, 
                 (rank, item) -> {
                    V property = propertyExtractor.apply(item);
                    if(rank.isEmpty()){
                      rank.put(new Integer(1),new LinkedList<T>());
                    }else{
                      Integer r = rank.lastKey();
                      List<T> items = rank.get(r);
                      if(! property.equals(propertyExtractor.apply(items.get(0)))) {
                        rank.put(r+items.size(), new LinkedList<T>());
                      }
                    }
                    rank.get(rank.lastKey()).add(item);
                },
            (rank1,rank2) -> { 
                   int lastRanking = rank1.lastKey();
                   int offset = lastRanking + rank1.get(lastRanking).size()-1;
                   if( propertyExtractor.apply(rank1.get(lastRanking).get(0))
                       == propertyExtractor.apply(rank2.get(rank2.firstKey()).get(0))){
                     rank1.get(lastRanking).addAll(rank2.get(rank2.firstKey()));
                     rank2.remove(rank2.firstKey());
                   }
                   rank2.forEach((r,items) -> {rank1.put(offset+r, items);} );
            }
    );
}

上面的方法可以应用为：

SortedMap<Integer,List<String>> ranking =
            rank(words,String::length,reverseOrder());

排名分组收集器

基于属性值分组的方法可以封装在收集器中：

static <T,V> Collector<T,?,SortedMap<Integer,List<T>>> 
rankingCollector(Function<T,V> propertyExtractor, 
                 Comparator<V> propertyComparator){
  return 
  collectingAndThen(
    groupingBy(propertyExtractor,
               ()->new TreeMap<>(propertyComparator),
               toList()),
    map -> map.entrySet().stream().collect(
            TreeMap::new,
            (rank,entry) -> 
                  rank.put(rank.isEmpty()?1:rank.lastKey()+
                             rank.get(rank.lastKey()).size(),
                           entry.getValue() ),
            (rank1,rank2) -> { 
                   int lastRanking = rank1.lastKey();
                   int offset = lastRanking + rank1.get(lastRanking).size()-1;
                   if( propertyExtractor.apply(rank1.get(lastRanking).get(0))
                       == 

    propertyExtractor.apply(rank2.get(rank2.firstKey()).get(0))){
                         rank1.get(lastRanking).addAll(rank2.get(rank2.firstKey()));
                         rank2.remove(rank2.firstKey());
                       }
                       rank2.forEach((r,items) -> {rank1.put(offset+r, items);} );
                }
         )
      );
    }

此收集器工厂方法可以用作例如：

SortedMap<Integer,List<String>> ranking =
        words.collect(rankingCollector(String::length,reverseOrder()));

打印排名

一旦计算出排名并将其存储在地图中，就可以将其打印出来，通常用于调试目的。

这里是一些在控制台上打印排名的可能选项。

打印机 Consumer

使用进行排名的使用者对象，格式化条目并打印。以下代码报告了返回此类使用者的工厂方法：

static <T,V> Consumer<Map<Integer,List<T>>> 
rankPrinter(Function<T,V> propertyExtractor){
      return ranking ->
       ranking.entrySet().stream()
       .map( e -> e.getValue().stream().map( 
                   v -> e.getKey() + " - " + v 
                       + " (" + propertyExtractor.apply(v) + ")" ) )
        .flatMap(Function.identity())
        .forEach(System.out::println);
}

整理者 Function

使用将排名图转换为由项目串联组成的字符串的函数。

static <T,V> Function<Map<Integer,List<T>>,String> 
rankCollator(Function<T,V> propertyExtractor){
  return ranking ->         
        ranking.entrySet().stream()
                .map( e -> (Stream<String>)e.getValue().stream().
                        map( v -> (String)(e.getKey() + " : " + v + " (" + propertyExtractor.apply(v) + ")") ))
                        .flatMap(Function.identity())
                        .collect(joining("\n"));
    }

上述方法可以如下使用：

System.out.println(rankCollator(propertyExtractor).apply(ranking));

排名Map班

作为替代方案，可以TreeMap用扩展该类并覆盖该toString()方法的新类替换该类。

可以通过编写以下收集器累加器供应商来代替TreeMap::new：

()->new TreeMap<Integer,List<T>>(){
    public String toString(){
        return entrySet().stream()
                .map( e -> (Stream<String>)e.getValue().stream().map( 
                            v -> e.getKey().toString() + " - " + v.toString() 
                                    + " (" + propertyExtractor.apply(v) + ")" ) )
                .flatMap(Function.identity())
                .collect(joining("\n")); 
    }
}

泛型解决方案的完整代码可在我的github存储库中的StreamRanking类中找到。