Raggruppa e riduce l'elenco degli oggetti

Question

Ho un elenco di oggetti con molti campi duplicati e alcuni che devono essere uniti. Voglio ridurlo a un elenco di oggetti unici utilizzando solo Java 8 Stream (so come farlo tramite old-skool significa, ma questo è un esperimento.)

Questo è quello che ho adesso. Non mi piace molto perché la creazione di mappe sembra estranea e la collezione values ​​() è una vista della mappa di supporto, e devi metterla in un nuovo ArrayList<>(...) per ottenere una collezione più specifica. Esiste un approccio migliore, magari utilizzando le operazioni di riduzione più generali?

@Test 
public void reduce() { 
    Collection<Foo> foos = Stream.of("foo", "bar", "baz") 
        .flatMap(this::getfoos) 
        .collect(Collectors.toMap(f -> f.name, f -> f, (l, r) -> { 
         l.ids.addAll(r.ids); 
         return l; 
        })).values(); 

    assertEquals(3, foos.size()); 
    foos.forEach(f -> assertEquals(10, f.ids.size())); 
} 

private Stream<Foo> getfoos(String n) { 
    return IntStream.range(0,10).mapToObj(i -> new Foo(n, i)); 
} 

public static class Foo { 
    private String name; 
    private List<Integer> ids = new ArrayList<>(); 

    public Foo(String n, int i) { 
     name = n; 
     ids.add(i); 
    } 
} 

Answer 1

Se si interrompe il raggruppamento e la riduzione gradini, si può ottenere qualcosa più pulito:

Stream<Foo> input = Stream.of("foo", "bar", "baz").flatMap(this::getfoos); 

Map<String, Optional<Foo>> collect = input.collect(Collectors.groupingBy(f -> f.name, Collectors.reducing(Foo::merge))); 

Collection<Optional<Foo>> collected = collect.values(); 

Ciò presuppone alcuni metodi di convenienza nella classe Foo:

public Foo(String n, List<Integer> ids) { 
    this.name = n; 
    this.ids.addAll(ids); 
} 

public static Foo merge(Foo src, Foo dest) { 
    List<Integer> merged = new ArrayList<>(); 
    merged.addAll(src.ids); 
    merged.addAll(dest.ids); 
    return new Foo(src.name, merged); 
} 

Answer 2

Come già sottolineato nei commenti, una mappa è una cosa molto naturale da utilizzare quando si desidera identificare oggetti unici. Se tutto ciò che dovevi fare era trovare gli oggetti unici, potresti usare il metodo Stream::distinct. Questo metodo nasconde il fatto che è coinvolta una mappa, ma a quanto pare usa una mappa internamente, come suggerito da this question che mostra che dovresti implementare un metodo hashCode o distinct potrebbe non funzionare correttamente.

Nel caso del metodo distinct, in cui non è necessario unire, è possibile restituire alcuni risultati prima che tutto l'input sia stato elaborato. Nel tuo caso, a meno che tu non possa fare ulteriori presupposti sull'input che non sono stati menzionati nella domanda, devi completare l'elaborazione di tutti gli input prima di restituire qualsiasi risultato. Quindi questa risposta usa una mappa.

È abbastanza semplice utilizzare gli stream per elaborare i valori della mappa e trasformarla in ArrayList. Lo mostro in questa risposta, oltre a fornire un modo per evitare l'aspetto di uno Optional<Foo>, che compare in una delle altre risposte.

public void reduce() { 
    ArrayList<Foo> foos = Stream.of("foo", "bar", "baz").flatMap(this::getfoos) 
      .collect(Collectors.collectingAndThen(Collectors.groupingBy(f -> f.name, 
      Collectors.reducing(Foo.identity(), Foo::merge)), 
      map -> map.values().stream(). 
       collect(Collectors.toCollection(ArrayList::new)))); 

    assertEquals(3, foos.size()); 
    foos.forEach(f -> assertEquals(10, f.ids.size())); 
} 

private Stream<Foo> getfoos(String n) { 
    return IntStream.range(0, 10).mapToObj(i -> new Foo(n, i)); 
} 

public static class Foo { 
    private String name; 
    private List<Integer> ids = new ArrayList<>(); 

    private static final Foo BASE_FOO = new Foo("", 0); 

    public static Foo identity() { 
     return BASE_FOO; 
    } 

    // use only if side effects to the argument objects are okay 
    public static Foo merge(Foo fooOne, Foo fooTwo) { 
     if (fooOne == BASE_FOO) { 
      return fooTwo; 
     } else if (fooTwo == BASE_FOO) { 
      return fooOne; 
     } 
     fooOne.ids.addAll(fooTwo.ids); 
     return fooOne; 
    } 

    public Foo(String n, int i) { 
     name = n; 
     ids.add(i); 
    } 
} 

Answer 3

Se gli elementi di input sono forniti in ordine casuale, quindi avere la mappa intermedio è probabilmente la soluzione migliore. Tuttavia, se sai in anticipo che tutte le le foos con lo stesso nome sono adiacenti (questa condizione è effettivamente soddisfatta nel test), l'algoritmo può essere notevolmente semplificato: devi solo confrontare l'elemento corrente con quello precedente e unire loro se il nome è lo stesso.

Sfortunatamente non esiste un metodo Stream API che ti consenta di farlo in modo facile ed efficace. Una soluzione possibile è quella di scrivere collezione personalizzata in questo modo:

public static List<Foo> withCollector(Stream<Foo> stream) { 
    return stream.collect(Collector.<Foo, List<Foo>>of(ArrayList::new, 
      (list, t) -> { 
       Foo f; 
       if(list.isEmpty() || !(f = list.get(list.size()-1)).name.equals(t.name)) 
        list.add(t); 
       else 
        f.ids.addAll(t.ids); 
      }, 
      (l1, l2) -> { 
       if(l1.isEmpty()) 
        return l2; 
       if(l2.isEmpty()) 
        return l1; 
       if(l1.get(l1.size()-1).name.equals(l2.get(0).name)) { 
        l1.get(l1.size()-1).ids.addAll(l2.get(0).ids); 
        l1.addAll(l2.subList(1, l2.size())); 
       } else { 
        l1.addAll(l2); 
       } 
       return l1; 
      })); 
} 

miei test mostrano che questo collettore è sempre più veloce di raccolta per mappare (fino a 2 volte a seconda del numero medio di nomi duplicati), sia in modo sequenziale e parallela .

Un altro approccio è quello di utilizzare la libreria StreamEx che fornisce una serie di metodi "riduzione parziale" compreso collapse:

public static List<Foo> withStreamEx(Stream<Foo> stream) { 
    return StreamEx.of(stream) 
      .collapse((l, r) -> l.name.equals(r.name), (l, r) -> { 
       l.ids.addAll(r.ids); 
       return l; 
      }).toList(); 
} 

Questo metodo accetta due argomenti: un BiPredicate che viene applicata per due elementi adiacenti e deve restituire true se gli elementi devono essere uniti e lo BinaryOperator che esegue l'unione. Questa soluzione è leggermente più lenta in modalità sequenziale rispetto al collector personalizzato (in parallelo i risultati sono molto simili), ma è ancora significativamente più veloce della soluzione toMap ed è più semplice e un po 'più flessibile come collapse è un'operazione intermedia, quindi è possibile raccogliere in un altro modo.

Anche in questo caso entrambe le soluzioni funzionano solo se è noto che le unità con lo stesso nome sono adiacenti. È una cattiva idea ordinare il flusso di input in base al nome foo, quindi utilizzare queste soluzioni, poiché l'ordinamento ridurrà drasticamente le prestazioni rendendolo più lento della soluzione toMap.

Answer 4

Come già sottolineato da altri, un intermedio Map è inevitabile, in quanto è il modo di trovare gli oggetti da unire. Inoltre, non è necessario modificare i dati di origine durante la riduzione.

Tuttavia, è possibile ottenere sia senza creare multipla Foo casi:

List<Foo> foos = Stream.of("foo", "bar", "baz") 
       .flatMap(n->IntStream.range(0,10).mapToObj(i -> new Foo(n, i))) 

       .collect(collectingAndThen(groupingBy(f -> f.name), 
        m->m.entrySet().stream().map(e->new Foo(e.getKey(), 
         e.getValue().stream().flatMap(f->f.ids.stream()).collect(toList()))) 
        .collect(toList()))); 

Questo presuppone che si aggiungere un costruttore

public Foo(String n, List<Integer> l) { 
     name = n; 
     ids=l; 
    } 

alla classe Foo, come avrebbe dovuto se Foo è davvero dovrebbe essere in grado di contenere un elenco di ID. Come nota a margine, avere un tipo che funge da singolo elemento e un contenitore per i risultati uniti mi sembra innaturale. Questo è esattamente il motivo per cui il codice risulta essere così complicato.

Se gli elementi di origine avevano un unico id, usando qualcosa come groupingBy(f -> f.name, mapping(f -> id, toList()), seguita mappando le voci di (String, List<Integer>) alle voci unite era sufficiente.

Poiché questo non è il caso e Java 8 non ha il collettore flatMapping, il passaggio di flatmapping viene spostato al secondo passaggio, rendendolo molto più complicato.

Ma in entrambi i casi, il secondo passaggio non è obsoleto poiché è dove vengono effettivamente create le voci di risultato e la conversione della mappa nel tipo di elenco desiderato è gratuita.