我有一个Map< String,String>表示从A到B的链接.我想链接所有可能的路由.例如 ：
[A,B] [B,C] [C,D] [E,F] [F,G] [H,I]
将输出
[A,B,C,F,I]
我在这里找到了类似的问题(但没有完全满足我的要求)：https://stackoverflow.com/a/10176274/298430
这是我的解决方案：
public static <T> Set<List<T>> chainLinks(Map<T,T> map) {
Set<List<T>> resultSet = new HashSet<>();
map.forEach((from,to) -> {
if (!map.containsValue(from)) {
List<T> list = new ArrayList<>();
list.add(from);
list.addAll(inner(to,map));
resultSet.add(list);
}
});
return resultSet;
}
private static <T> List<T> inner(T from,Map<T,T> map) {
if (map.containsKey(from)) {
List<T> list = new ArrayList<>();
list.add(from);
list.addAll(inner(map.get(from),map));
return list;
} else {
List<T> end = new ArrayList<>();
end.add(from);
return end;
}
}
和测试用例：
@Test
public void testChainLinks() {
Map<String,String> map = new HashMap<String,String>() {{
put("A","B");
put("B","C");
put("C","D");
put("E","F");
put("F","G");
put("H","I");
}};
Utils.chainLinks(map).forEach(list -> {
logger.info("list = {}",list.stream().collect(Collectors.joining(" -> ")));
});
}
它确实正常工作：
list = H -> I list = E -> F -> G list = A -> B -> C -> D
但我不喜欢我的解决方案.因为我觉得它可以用更实用的方式解决.我可以在这里感受到stream.fold()的气味.我试过将我的代码转换为纯函数样式但是徒劳无功：这意味着没有中间对象创建…
可能吗 ？任何提示都很感激！
解决方法
使用自定义收集器的替代解决方案具有接近线性的复杂性.它确实比之前提出的解决方案更快,但看起来有点丑陋.
public static <T> Collector<Entry<T,T>,?,List<List<T>>> chaining() {
BiConsumer<Map<T,arraydeque<T>>,Entry<T,T>> accumulator = (
m,entry) -> {
arraydeque<T> k = m.remove(entry.getKey());
arraydeque<T> v = m.remove(entry.getValue());
if (k == null && v == null) {
// new pair does not connect to existing chains
// create a new chain with two elements
k = new arraydeque<>();
k.addLast(entry.getKey());
k.addLast(entry.getValue());
m.put(entry.getKey(),k);
m.put(entry.getValue(),k);
} else if (k == null) {
// new pair prepends an existing chain
v.addFirst(entry.getKey());
m.put(entry.getKey(),v);
} else if (v == null) {
// new pair appends an existing chain
k.addLast(entry.getValue());
m.put(entry.getValue(),k);
} else {
// new pair connects two existing chains together
// reuse the first chain and update the tail marker
// btw if k == v here,then we found a cycle
k.addAll(v);
m.put(k.getLast(),k);
}
};
BinaryOperator<Map<T,arraydeque<T>>> combiner = (m1,m2) -> {
throw new UnsupportedOperationException();
};
// our map contains every chain twice: mapped to head and to tail
// so in finisher we have to leave only half of them
// (for example ones connected to the head).
// The map step can be simplified to Entry::getValue if you fine with
// List<Collection<T>> result.
Function<Map<T,List<List<T>>> finisher = m -> m
.entrySet().stream()
.filter(e -> e.getValue().getFirst().equals(e.getKey()))
.map(e -> new ArrayList<>(e.getValue()))
.collect(Collectors.toList());
return Collector.of(HashMap::new,accumulator,combiner,finisher);
}
用法：
List<List<String>> res = map.entrySet().stream().collect(chaining());
(我没有实现组合器步骤,因此它不能用于并行流,但它也不是很难添加它).这个想法很简单：我们跟踪到目前为止在地图中找到的部分链,其中键指向链的开始和结束,值是包含到目前为止找到的链的arraydeque对象.每个新条目都会更新现有的deque(如果它附加/预先添加)或将两个deques合并在一起.
根据我的测试,这个版本比带有100个链的50000元件输入阵列的@ saka1029解决方案快1000倍.