java 8 stile funzionale dei collegamenti di concatenamento

Question

Ho un Map<String , String> che indica i collegamenti da A a B. Voglio concatenare tutti i percorsi possibili. per esempio:

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

uscita volontà

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

ho trovato domanda simile qui (ma non adempie pienamente la mia richiesta): https://stackoverflow.com/a/10176274/298430

E qui è la mia soluzione:

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

e il test case:

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

funziona correttamente:

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

Ma non mi piace la mia soluzione. Perché sento che può essere risolto in uno stile più funzionale. Posso sentire l'odore di stream.fold() qui. Ho provato, ma invano, a convertire il mio codice in uno stile puramente funzionale: il che significa nessuna creazione di oggetti intermedi ...

È possibile? Ogni suggerimento è riconoscente!

Answer 1

C'è una soluzione alternativa utilizzando il collettore personalizzato con vicino alla complessità lineare. È molto più veloce delle soluzioni proposte prima, anche se sembra un po 'più brutto.

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

Usage:

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

(non ho implementare il passo combiner, quindi non può essere utilizzato per flussi paralleli, ma non è molto difficile per aggiungerlo come bene). L'idea è semplice: monitoriamo le catene parziali trovate finora nella mappa in cui le chiavi puntano alla catena inizia e finisce ei valori sono ArrayDeque oggetti contenenti le catene trovate finora. Ogni nuova voce aggiorna il deque esistente (se lo aggiunge/lo anticipa) o unisce due deques insieme.

Secondo i miei test questa versione funziona 1000 volte più velocemente della soluzione @ saka1029 per l'array di input 50000 elementi con 100 catene.

Answer 2

MODIFICA: filtro incluso da David Pérez Il commento di Cabrera per rimuovere le liste intermedie.

Ebbene si può facilmente ricorsione:

soluzione

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 ricorsivo:

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