java 8 kiểu chức năng của chuỗi liên kết

Question

Tôi có một số Map<String , String> cho biết liên kết từ A đến B. Tôi muốn kết nối tất cả các tuyến đường có thể. ví dụ:

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

chí đầu ra

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

tôi thấy câu hỏi tương tự ở đây (nhưng không đáp ứng đầy đủ yêu cầu của tôi): https://stackoverflow.com/a/10176274/298430

Và đây là giải pháp của tôi:

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

và trường hợp kiểm tra:

@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(" -> "))); 
    }); 
    } 

Nó hoạt động chính xác:

list = H -> I 
list = E -> F -> G 
list = A -> B -> C -> D 

Nhưng tôi không thích giải pháp của tôi. Bởi vì tôi cảm thấy nó có thể được giải quyết theo một phong cách chức năng hơn. Tôi có thể cảm thấy mùi của stream.fold() ở đây. Tôi đã cố gắng nhưng vô ích để chuyển đổi mã của tôi thành một phong cách chức năng thuần túy: có nghĩa là không tạo đối tượng trung gian ...

Có thể không? Mọi gợi ý đều biết ơn!

Answer 1

Có một giải pháp thay thế bằng cách sử dụng nhà sưu tập tùy chỉnh với gần độ phức tạp tuyến tính. Nó thực sự nhanh hơn so với các giải pháp được đề xuất trước đây, mặc dù trông hơi xấu hơn.

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

Cách sử dụng:

List<List<String>> res = map.entrySet().stream().collect(chaining()); 

(Tôi đã không thực hiện bước combiner, do đó nó không thể được sử dụng cho các dòng song song, nhưng nó không phải là rất khó để thêm nó cũng). Ý tưởng rất đơn giản: chúng tôi theo dõi các chuỗi một phần được tìm thấy từ trước đến nay trong bản đồ nơi các khóa trỏ đến chuỗi bắt đầu và kết thúc và các giá trị là ArrayDeque các đối tượng chứa chuỗi được tìm thấy từ trước tới nay. Mỗi mục mới cập nhật deque hiện có (nếu nó gắn thêm/prepends nó) hoặc kết hợp hai deques với nhau.

Theo thử nghiệm của tôi, phiên bản này hoạt động nhanh hơn 1000 lần so với giải pháp @ saka1029 cho mảng đầu vào phần tử 50000 với 100 chuỗi.

Answer 2

CHỈNH SỬA: bộ lọc được bao gồm từ nhận xét của David Pérez Cabrera để xóa danh sách trung gian.

Vâng, bạn có thể dễ dàng đệ quy:

private static Set<List<String>> chainLinks(Map<String, String> map) { 
    return map.keySet().stream().filter(k -> !map.containsValue(k)).map( (key) -> 
       calc(key, map, new LinkedList<>()) 

    ).collect(Collectors.toSet()); 

} 
private static List<String> calc(String key,Map<String, String> map,List<String> list){ 
    list.add(key); 
    if (map.containsKey(key)) 
     return calc(map.get(key),map,list); 
    else 
     return list; 
} 

Answer 3

Non-recursive giải pháp:

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