这里有两个问题需要依次回答:
排名表示
典型的排名是一个项目列表,前面带有它们的相对排名值。
至少有两种可能的实现方式来返回排名的值:
选项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<>();
以下是步骤:
具体步骤如下:
Sort the elements of the stream
words.sorted(comparing(propetyExtractor,propertyComparator))
Assign the ranking, starting with 1
and incrementing it
any time the property changes. The ranking has to be incremented
by the number of items that shared the current ranking.
.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和relative 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,
(rank, item) -> {
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
。
假设流在并行处理中,在两个并发执行的收集操作中进行处理:
the initial sorted stream (result of the sorted()
operation is
divided into two stream, maintaining the orded
- sub-stream 1:
{"AAAA","BBB","CCC"}
- sub-stream 2:
{"DD","EE","F"}
two distinct collectors operate in parallel, on each sub-stream
the result are two maps contain the partial ranking of each sub-stream:
rank1
= {1=["AAAA"],2=["BBB","CCC"]}
rank2
= {1=["DD","EE"],3=["F"]}
The combiner operation should merge rank2
into rank1
, in practice
each entry of the rank2
operation should be added to rank1
with its
key updated. They keys are updated by adding an offset that is equal to
the key of the last entry plus the lenght of the last entry value list
minus one:
int lastRanking = rank1.lastKey();
int offset = lastRanking + rank1.get(lastRanking).size()-1;
In practice the entry 1=["DD","EE"]
of rank2
should be turned into
4=["DD","EE"]
and added to rank1
.
In addition, a special case should be considered, i.e. when the items
in the last entry of rank1
and those in the first entry of rank2
share the same ranking property value. E.g. for string length:
rank1
= {1=["AAAA"],2=["BBB","CCC"]}
rank2
= {1=["DDD"],2=["EE"],3=["F"]}
When this case occurs, the items in the rank2
first entry list
must be added to this in the last rank1
entry list, and then the
first entry removed.
That is the above maps should be transformed into:
rank1
= {1=["AAAA"],2=["BBB","CCC"
,"DDD"
]}
rank2
= {
~~1=["DDD"],
~~2=["EE"],3=["F"]}
Then the entries of rank2
can be updated and added to rank1
as
described above.
按排名属性进行分组
基本流程
对于已排序的列表版本,可以使用支持映射数据结构来定义初始的朴素版本程序,通过副作用进行流操作:
SortedMap<Integer,List<String>> ranking = new TreeMap<>();
天真的步骤如下:
group the items by their property in a sorted map
words.collect(groupingBy(propertyExtractor,
()->new TreeMap<>(propertyComparator),toList()))
for each entry in the above map compute the ranking
.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
使用一个接收排名的 consumer 对象,格式化条目并打印它们。下面的代码报告了一个返回这样的 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);
}
排序器 函数
使用将排名映射转换为由项目串联而成的字符串的函数。
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类中找到。