java 8链接链接的功能样式

Question

我有一个Map<String , String>表示从A到B的链接.我想链接所有可能的路线.例如 :

[A , B]
[B , C]
[C , D]
[E , F]
[F , G]
[H , I]

将输出

[A , B , C , D]
[E , F , G]
[H , 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()这里的气味.我试过将我的代码转换为纯函数样式但是徒劳无功:这意味着没有中间对象创建...

可能吗 ？任何提示都很感激!

Answer 1

非递归解决方案:

    Set<List<String>> result = map.keySet().stream()
        .filter(k -> !map.containsValue(k))
        .map(e -> new ArrayList<String>() {{
            String x = e;
            add(x);
            while (map.containsKey(x))
                add(x = map.get(x));
        }})
        .collect(Collectors.toSet());

Answer 2

有一种替代解决方案，使用具有接近线性复杂度的自定义收集器。它确实比之前提出的解决方案更快，尽管看起来有点难看。

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, ArrayDeque<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());

（我没有实现该combiner步骤，因此它不能用于并行流，但添加它也不是很难）。这个想法很简单：我们跟踪到目前为止在映射中找到的部分链，其中键指向链的开始和结束，值是ArrayDeque包含到目前为止找到的链的对象。每个新条目都会更新现有的双端队列（如果它附加/前置它）或将两个双端队列合并在一起。

根据我的测试，对于具有 100 个链的 50000 个元素输入数组，此版本的工作速度比 @saka1029 解决方案快 1000 倍。